![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / odist / pax / include|
Return to hash.h CVS log | Up to [Research Unix] / researchv10no / cmd / odist / pax / include |
1.1 root 1: /*
2: * G. S. Fowler
3: * AT&T Bell Laboratories
4: *
5: * hash table library interface definitions
6: */
7:
8: #ifndef HASH_ALLOCATE
9:
10: #define hash_info _hash_info_
11: #define vhashalloc hashvalloc
12:
13: #ifndef VOID
14: #define VOID char
15: #endif
16:
17: #define HASH_ALLOCATE (1<<0) /* allocate new key names */
18: #define HASH_FIXED (1<<1) /* fixed bucket/table size */
19: #define HASH_HASHED (1<<6) /* key names already hashed */
20: #define HASH_RESIZE (1<<2) /* table has been resized */
21: #define HASH_SCANNING (1<<3) /* currently scanning scope */
22: #define HASH_SCOPE (1<<4) /* push scope / create in bot */
23: #define HASH_STATIC (1<<5) /* static table allocation */
24:
25: #define HASH_CREATE (1<<8) /* create bucket if not found */
26: #define HASH_DELETE (1<<9) /* delete bucket if found */
27: #define HASH_LOOKUP 0 /* default op */
28:
29: #define HASH_BUCKET (1<<11) /* name is installed bucket */
30: #define HASH_INSTALL (1<<12) /* install allocated bucket */
31: #define HASH_NOSCOPE (1<<13) /* top scope only */
32: #define HASH_OPAQUE (1<<14) /* opaque bucket */
33: #define HASH_VALUE (1<<15) /* value bucket field used */
34:
35: #define HASH_GET (HASH_LOOKUP|HASH_VALUE)
36: #define HASH_NEW (HASH_CREATE|HASH_FIXED)
37: #define HASH_PUT (HASH_CREATE|HASH_VALUE)
38:
39: #define HASH_DELETED (1<<(8*sizeof(int)-1)) /* deleted placeholder */
40: #define HASH_KEEP (1<<(8*sizeof(int)-2)) /* no free on bucket */
41: #define HASH_HIDDEN (1<<(8*sizeof(int)-3)) /* hidden by scope */
42: #define HASH_HIDES (1<<(8*sizeof(int)-4)) /* hides lower scope */
43: #define HASH_OPAQUED (1<<(8*sizeof(int)-5)) /* opaqued placeholder */
44:
45: #define HASH_RESET (HASH_RESIZE|HASH_SCOPE|HASH_STATIC)
46: #define HASH_INTERNAL (HASH_BUCKET|HASH_RESIZE|HASH_SCANNING|HASH_STATIC)
47: #define HASH_FLAGS (HASH_DELETED|HASH_HIDDEN|HASH_HIDES|HASH_KEEP|HASH_OPAQUED)
48:
49: #define HASH_alloc 1
50: #define HASH_clear 2
51: #define HASH_compare 3
52: #define HASH_free 4
53: #define HASH_hash 5
54: #define HASH_meanchain 6
55: #define HASH_name 7
56: #define HASH_namesize 8
57: #define HASH_set 9
58: #define HASH_size 10
59: #define HASH_table 11
60:
61: #include <hashpart.h>
62:
63: #define hashclear(t,f) ((t)->flags &= ~((f) & ~HASH_INTERNAL))
64: #define hashdel(t,n) hashlook(t, (char*)(n), HASH_DELETE, (char*)0)
65: #define hashget(t,n) hashlook(t, (char*)(n), HASH_LOOKUP|HASH_VALUE, (char*)0)
66: #define hashlast(t) (hash_info.last)
67: #define hashname(b) ((((b)->hash&HASH_HIDES)?((HASHBUCKET*)((b)->name)):(b))->name)
68: #define hashput(t,n,v) (char*)hashlook(t, (char*)(n), HASH_CREATE|HASH_VALUE, (char*)(v))
69: #define hashscope(t) ((t)->scope)
70: #define hashset(t,f) ((t)->flags |= ((f) & ~HASH_INTERNAL))
71:
72: #define Hashbin_t HASHBUCKET
73: #define Hashhdr_t HASHHEADER
74: #define Hashpos_t HASHPOSITION
75: #define Hashtab_t HASHTABLE
76:
77: typedef struct hashbucket HASHBUCKET;
78: typedef struct hashheader HASHHEADER;
79: typedef struct hashposition HASHPOSITION;
80: typedef struct hashroot HASHROOT;
81: typedef struct hashtable HASHTABLE;
82: typedef unsigned int (*HASHFUN)();
83: typedef int (*HASHINT)();
84: typedef char* (*HASHPTR)();
85:
86: /*
87: * the #define's avoid union tags
88: */
89:
90: #define HASH_HEADER /* common bucket header */ \
91: HASHBUCKET* next; /* next in collision chain */ \
92: unsigned int hash; /* hash flags and value */ \
93: char* name /* key name */
94:
95: #define HASH_DEFAULT /* HASH_VALUE bucket elements */ \
96: char* value /* key value */
97:
98: struct hashheader /* bucket header */
99: {
100: HASH_HEADER;
101: };
102:
103: struct hashbucket /* prototype bucket */
104: {
105: HASH_HEADER;
106: HASH_DEFAULT;
107: };
108:
109: struct hashposition /* hash scan bucket position */
110: {
111: HASHTABLE* tab; /* table pointer */
112: HASHTABLE* top; /* top scope table pointer */
113: int flags; /* scan flags */
114: HASHBUCKET* bucket; /* bucket */
115: HASHBUCKET** slot; /* table slot */
116: HASHBUCKET** limit; /* slot limit */
117: };
118:
119: struct hashroot /* root hash table information */
120: {
121: int flags; /* flags: see HASH_[A-Z]* */
122: int namesize; /* fixed name size: 0 => string */
123: int meanchain; /* resize mean chain length */
124: HASHFUN hash; /* name hash routine */
125: HASHINT compare; /* name comparision routine */
126: HASHPTR alloc; /* value allocation routine */
127: HASHINT free; /* value free routine */
128: int accesses; /* number of accesses */
129: int collisions; /* number of collisions */
130: HASHROOT* next; /* next in list of all roots */
131: HASHTABLE* references; /* referencing table list */
132: };
133:
134: struct hashtable /* hash table information */
135: {
136: HASHROOT* root; /* root hash table information */
137: HASHTABLE* scope; /* scope covered table */
138: short flags; /* flags: see HASH_[A-Z]* */
139: short frozen; /* table freeze nesting */
140: HASHBUCKET** table; /* hash slot table */
141: int size; /* table size */
142: int buckets; /* active bucket count */
143: char* name; /* table name */
144: HASHTABLE* next; /* root reference list link */
145: };
146:
147: struct hashinfo /* library hash info */
148: {
149: HASHBUCKET* last; /* most recent lookup bucket */
150: HASHTABLE* table; /* most recent lookup table */
151: HASHROOT* list; /* root table list */
152: };
153:
154: #if __cplusplus
155: extern "C" {
156: #endif
157:
158: extern struct hashinfo hash_info;
159:
160: #if __cplusplus
161: }
162: #endif
163:
164: #if __STDC__ || __cplusplus || c_plusplus
165:
166: #include <stdarg.h>
167: #include <stdio.h>
168:
169: #if __cplusplus
170: extern "C" {
171: #endif
172: extern HASHTABLE* hashalloc(HASHTABLE*, ...);
173: extern HASHTABLE* hashvalloc(HASHTABLE*, va_list);
174: extern void hashdone(HASHPOSITION*);
175: extern void hashdump(FILE*, HASHTABLE*, int);
176: extern HASHTABLE* hashfree(HASHTABLE*);
177: extern char* hashlook(HASHTABLE*, const char*, int, const char*);
178: extern HASHBUCKET* hashnext(HASHPOSITION*);
179: extern void hashscan(HASHTABLE*, int, HASHPOSITION*);
180: extern void hashsize(HASHTABLE*, int);
181: extern int hashwalk(HASHTABLE*, int, HASHINT);
182:
183: extern unsigned int memhash(const char*, int);
184: extern unsigned long memsum(const char*, int, unsigned long);
185: extern unsigned int strhash(const char*);
186: extern unsigned long strsum(const char*, unsigned long);
187: #if __cplusplus
188: }
189: #endif
190: #else
191: extern HASHTABLE* hashalloc();
192: extern HASHTABLE* hashvalloc();
193: extern void hashdone();
194: extern void hashdump();
195: extern HASHTABLE* hashfree();
196: extern char* hashlook();
197: extern HASHBUCKET* hashnext();
198: extern void hashscan();
199: extern void hashsize();
200: extern int hashwalk();
201:
202: extern unsigned int memhash();
203: extern unsigned long memsum();
204: extern unsigned int strhash();
205: extern unsigned long strsum();
206: #endif
207:
208: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.