usr/src/lib/libast/common/include/hash.h

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
   5 *                      and is licensed under the                       *
   6 *                  Common Public License, Version 1.0                  *
   7 *                    by AT&T Intellectual Property                     *
   8 *                                                                      *
   9 *                A copy of the License is available at                 *
  10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
  11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
  12 *                                                                      *
  13 *              Information and Software Systems Research               *
  14 *                            AT&T Research                             *
  15 *                           Florham Park NJ                            *
  16 *                                                                      *
  17 *                 Glenn Fowler <gsf@research.att.com>                  *
  18 *                  David Korn <dgk@research.att.com>                   *
  19 *                   Phong Vo <kpv@research.att.com>                    *
  20 *                                                                      *
  21 ***********************************************************************/
  22 #pragma prototyped
  23 /*
  24  * Glenn Fowler
  25  * AT&T Research
  26  *
  27  * hash table library interface definitions
  28  *
  29  * NOTE: new code should use the more general <cdt.h>
  30  */
  31
  32 #ifndef _HASH_H
  33 #define _HASH_H
  34
  35 #define HASH_ALLOCATE   (1L<<0)         /* allocate new key names       */
  36 #define HASH_FIXED      (1L<<1)         /* fixed table size             */
  37 #define HASH_HASHED     (1L<<6)         /* key names already hashed     */
  38 #define HASH_RESIZE     (1L<<2)         /* table has been resized       */
  39 #define HASH_SCANNING   (1L<<3)         /* currently scanning scope     */
  40 #define HASH_SCOPE      (1L<<4)         /* push scope / create in bot   */
  41 #define HASH_STATIC     (1L<<5)         /* static table allocation      */
  42
  43 #define HASH_CREATE     (1L<<8)         /* create bucket if not found   */
  44 #define HASH_DELETE     (1L<<9)         /* delete bucket if found       */
  45 #define HASH_LOOKUP     0               /* default op                   */
  46 #define HASH_RENAME     (1L<<7)         /* rename bucket if found       */
  47
  48 #define HASH_BUCKET     (1L<<11)        /* name is installed bucket     */
  49 #define HASH_INSTALL    (1L<<12)        /* install allocated bucket     */
  50 #define HASH_NOSCOPE    (1L<<13)        /* top scope only               */
  51 #define HASH_OPAQUE     (1L<<14)        /* opaque bucket                */
  52 #define HASH_VALUE      (1L<<15)        /* value bucket field used      */
  53
  54 #define HASH_SIZE(n)    (((long)(n))<<16)  /* fixed bucket size         */
  55 #define HASH_SIZEOF(f)  ((((long)(f))>>16)&0xffff) /* extract size      */
  56
  57 #define HASH_DELETED    ((unsigned long)1<<(8*sizeof(int)-1)) /* deleted placeholder    */
  58 #define HASH_KEEP       (1L<<(8*sizeof(int)-2)) /* no free on bucket    */
  59 #define HASH_HIDDEN     (1L<<(8*sizeof(int)-3)) /* hidden by scope      */
  60 #define HASH_HIDES      (1L<<(8*sizeof(int)-4)) /* hides lower scope    */
  61 #define HASH_OPAQUED    (1L<<(8*sizeof(int)-5)) /* opaqued placeholder  */
  62 #define HASH_FREENAME   (1L<<(8*sizeof(int)-6)) /* free bucket name     */
  63
  64 #define HASH_RESET      (HASH_RESIZE|HASH_SCOPE|HASH_STATIC|HASH_VALUE)
  65 #define HASH_INTERNAL   (HASH_BUCKET|HASH_RESIZE|HASH_SCANNING|HASH_STATIC)
  66 #define HASH_FLAGS      (HASH_DELETED|HASH_FREENAME|HASH_HIDDEN|HASH_HIDES|HASH_KEEP|HASH_OPAQUED)
  67
  68 #define HASH_alloc              1
  69 #define HASH_clear              2
  70 #define HASH_compare            3
  71 #define HASH_free               4
  72 #define HASH_hash               5
  73 #define HASH_meanchain          6
  74 #define HASH_name               7
  75 #define HASH_namesize           8
  76 #define HASH_set                9
  77 #define HASH_size               10
  78 #define HASH_table              11
  79 #define HASH_va_list            12
  80
  81 #define HASH_bucketsize         13
  82
  83 #define HASH_region             14
  84
  85 #include <hashpart.h>
  86
  87 #define hashclear(t,f)          ((t)->flags &= ~((f) & ~HASH_INTERNAL))
  88 #define hashcover(b)            (((b)->hash&HASH_HIDES)?(Hash_bucket_t*)((b)->name):(Hash_bucket_t*)0)
  89 #define hashdel(t,n)            hashlook(t, (char*)(n), HASH_DELETE, (char*)0)
  90 #define hashget(t,n)            hashlook(t, (char*)(n), HASH_LOOKUP|HASH_VALUE, (char*)0)
  91 #define hashgetbucket(s)        ((Hash_bucket_t*)((s)-((sizeof(Hash_bucket_t)+sizeof(char*)-1)/sizeof(char*))*sizeof(char*)))
  92 #define hashkeep(b)             ((b)->hash|=HASH_KEEP)
  93 #define hashname(b)             ((((b)->hash&HASH_HIDES)?((Hash_bucket_t*)((b)->name)):(b))->name)
  94 #define hashput(t,n,v)          hashlook(t, (char*)(n), HASH_CREATE|HASH_VALUE, (char*)(v))
  95 #define hashref(t,n)            hashlook(t, (char*)(n), HASH_LOOKUP|HASH_INTERNAL|HASH_VALUE, (char*)0)
  96 #define hashscope(t)            ((t)->scope)
  97 #define hashset(t,f)            ((t)->flags |= ((f) & ~HASH_INTERNAL))
  98
  99 /*
 100  * DEPRECATED renames for compatibility
 101  */
 102
 103 #define Hashbin_t               Hash_bucket_t
 104 #define HASHBUCKET              Hash_bucket_t
 105 #define Hashhdr_t               Hash_header_t
 106 #define HASHHEADER              Hash_header_t
 107 #define Hashpos_t               Hash_position_t
 108 #define HASHPOSITION            Hash_position_t
 109 #define Hashtab_t               Hash_table_t
 110 #define HASHTABLE               Hash_table_t
 111
 112 #define vhashalloc              hashvalloc
 113 #define hashvalloc(t,a)         hashalloc(t,HASH_va_list,a,0)
 114
 115 /*
 116  * the #define's avoid union tags
 117  */
 118
 119 typedef struct Hash_bucket Hash_bucket_t;
 120 typedef struct Hash_root Hash_root_t;
 121 typedef struct Hash_table Hash_table_t;
 122
 123 #define HASH_HEADER                     /* common bucket header         */ \
 124         Hash_bucket_t*  next;           /* next in collision chain      */ \
 125         unsigned int    hash;           /* hash flags and value         */ \
 126         char*           name            /* key name                     */
 127
 128 #define HASH_DEFAULT                    /* HASH_VALUE bucket elements   */ \
 129         char*           value           /* key value                    */
 130
 131 typedef struct                          /* bucket header                */
 132 {
 133         HASH_HEADER;
 134 } Hash_header_t;
 135
 136 struct Hash_bucket                      /* prototype bucket             */
 137 {
 138         HASH_HEADER;
 139         HASH_DEFAULT;
 140 };
 141
 142 typedef struct                          /* hash scan bucket position    */
 143 {
 144         Hash_bucket_t*  bucket;         /* bucket                       */
 145 #ifdef _HASH_POSITION_PRIVATE_
 146         _HASH_POSITION_PRIVATE_
 147 #endif
 148 } Hash_position_t;
 149
 150 typedef struct                          /* last lookup cache            */
 151 {
 152         Hash_table_t*   table;          /* last lookup table            */
 153         Hash_bucket_t*  bucket;         /* last lookup bucket           */
 154 #ifdef _HASH_LAST_PRIVATE_
 155         _HASH_LAST_PRIVATE_
 156 #endif
 157 } Hash_last_t;
 158
 159 struct Hash_root                        /* root hash table information  */
 160 {
 161         int             accesses;       /* number of accesses           */
 162         int             collisions;     /* number of collisions         */
 163         int             flags;          /* flags: see HASH_[A-Z]*       */
 164         Hash_last_t     last;           /* last lookup cache            */
 165         void*           context;        /* user defined context         */
 166 #ifdef _HASH_ROOT_PRIVATE_
 167         _HASH_ROOT_PRIVATE_
 168 #endif
 169 };
 170
 171 struct Hash_table                       /* hash table information       */
 172 {
 173         Hash_root_t*    root;           /* root hash table information  */
 174         int             size;           /* table size                   */
 175         int             buckets;        /* active bucket count          */
 176         char*           name;           /* table name                   */
 177         Hash_table_t*   scope;          /* scope covered table          */
 178         short           flags;          /* flags: see HASH_[A-Z]*       */
 179 #ifdef _HASH_TABLE_PRIVATE_
 180         _HASH_TABLE_PRIVATE_
 181 #endif
 182 };
 183
 184 #if _BLD_ast && defined(__EXPORT__)
 185 #define extern          __EXPORT__
 186 #endif
 187
 188 extern Hash_table_t*    hashalloc(Hash_table_t*, ...);
 189 extern void             hashdone(Hash_position_t*);
 190 extern void             hashdump(Hash_table_t*, int);
 191 extern Hash_table_t*    hashfree(Hash_table_t*);
 192 extern Hash_bucket_t*   hashlast(Hash_table_t*);
 193 extern char*            hashlook(Hash_table_t*, const char*, long, const char*);
 194 extern Hash_bucket_t*   hashnext(Hash_position_t*);
 195 extern Hash_position_t* hashscan(Hash_table_t*, int);
 196 extern void             hashsize(Hash_table_t*, int);
 197 extern Hash_table_t*    hashview(Hash_table_t*, Hash_table_t*);
 198 extern int              hashwalk(Hash_table_t*, int, int (*)(const char*, char*, void*), void*);
 199
 200 #undef  extern
 201
 202 #endif