1 2 /* : : generated by proto : : */ 3 /*********************************************************************** 4 * * 5 * This software is part of the ast package * 6 * Copyright (c) 1985-2009 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 214