usr/src/lib/libast/i386/include/ast/hash.h

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