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 private definitions 28 */ 29 30 #ifndef _HASHLIB_H 31 #define _HASHLIB_H 32 33 #include <ast.h> 34 35 #define hash_info _hash_info_ 36 37 typedef void* (*Hash_alloc_f)(size_t); 38 typedef int (*Hash_compare_f)(const char*, const char*, ...); 39 typedef unsigned int (*Hash_hash_f)(const char*, ...); 40 typedef void (*Hash_free_f)(void*); 41 typedef void* (*Hash_region_f)(void*, void*, size_t, int); 42 43 typedef struct /* root local pointers */ 44 { 45 Hash_hash_f hash; /* name hash routine */ 46 Hash_compare_f compare; /* name comparision routine */ 47 Hash_alloc_f alloc; /* value allocation routine */ 48 Hash_free_f free; /* value free routine */ 49 Hash_region_f region; /* region alloc/free routine */ 50 void* handle; /* region handle arg */ 51 } Hash_local_t; 52 53 #define _HASH_POSITION_PRIVATE_ \ 54 Hash_table_t* tab; /* table pointer */ \ 55 int flags; /* scan flags */ \ 56 Hash_bucket_t** slot; /* table slot */ \ 57 Hash_bucket_t** limit; /* slot limit */ 58 59 #define _HASH_LAST_PRIVATE_ \ 60 const char* name; /* last lookup name */ \ 61 unsigned int hash; /* last lookup hash */ 62 63 #define _HASH_ROOT_PRIVATE_ \ 64 int namesize; /* fixed name size: 0 => string */ \ 65 int meanchain; /* resize mean chain length */ \ 66 Hash_local_t* local; /* root local pointers */ \ 67 Hash_root_t* next; /* next in list of all roots */ \ 68 Hash_table_t* references; /* referencing table list */ 69 70 #define _HASH_TABLE_PRIVATE_ \ 71 unsigned char frozen; /* table freeze nesting */ \ 72 unsigned char bucketsize; /* min bucket size in char*'s */ \ 73 Hash_bucket_t** table; /* hash slot table */ \ 74 Hash_table_t* next; /* root reference list link */ 75 76 #include <hash.h> 77 78 #define HASHMINSIZE (1<<4) /* min table slots (power of 2) */ 79 #define HASHMEANCHAIN 2 /* def resize mean chain len */ 80 81 #define HASHMOD(t,h) (h &= (t->size - 1)) 82 #define HASHVAL(x) ((x)&~HASH_FLAGS) 83 84 #define HASH(r,n,h) if (r->local->hash) h = r->namesize ? (*r->local->hash)(n, r->namesize) : (*r->local->hash)(n);\ 85 else\ 86 {\ 87 register const char* _hash_s1 = n;\ 88 h = 0;\ 89 if (r->namesize)\ 90 {\ 91 register const char* _hash_s2 = _hash_s1 + r->namesize;\ 92 while (_hash_s1 < _hash_s2) HASHPART(h, *_hash_s1++);\ 93 }\ 94 else while (*_hash_s1) HASHPART(h, *_hash_s1++);\ 95 } 96 97 typedef struct /* library private info */ 98 { 99 Hash_root_t* list; /* root table list */ 100 } Hash_info_t; 101 102 extern Hash_info_t hash_info; 103 104 #endif 105