1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2009 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 203