1 /*-------------------------------------------------------------------------
4 * for hash tables, particularly hash tables in shared memory
7 * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
10 * $Id: hsearch.h,v 1.18 2001/01/24 19:43:28 momjian Exp $
12 *-------------------------------------------------------------------------
21 * A hash table has a top-level "directory", each of whose entries points
22 * to a "segment" of ssize bucket headers. The maximum number of hash
23 * buckets is thus dsize * ssize (but dsize may be expansible). Of course,
24 * the number of records in the table can be larger, but we don't want a
25 * whole lot of records per bucket or performance goes down.
27 * In a hash table allocated in shared memory, the directory cannot be
28 * expanded because it must stay at a fixed address. The directory size
29 * should be selected using hash_select_dirsize (and you'd better have
30 * a good idea of the maximum number of entries!). For non-shared hash
31 * tables, the initial directory size can be left at the default.
33 #define DEF_SEGSIZE 256
34 #define DEF_SEGSIZE_SHIFT 8/* must be log2(DEF_SEGSIZE) */
35 #define DEF_DIRSIZE 256
36 #define DEF_FFACTOR 1/* default fill factor */
38 #define PRIME1 37 /* for the hash function */
39 #define PRIME2 1048583
43 * Hash bucket is actually bigger than this. Key field can have
44 * variable length and a variable length data field follows it.
46 typedef struct element
48 unsigned long next; /* secret from user */
52 typedef unsigned long BUCKET_INDEX;
54 /* segment is an array of bucket pointers */
55 typedef BUCKET_INDEX *SEGMENT;
56 typedef unsigned long SEG_OFFSET;
58 typedef struct hashhdr
60 long dsize; /* Directory Size */
61 long ssize; /* Segment Size --- must be power of 2 */
62 long sshift; /* Segment shift */
63 long max_bucket; /* ID of Maximum bucket in use */
64 long high_mask; /* Mask to modulo into entire table */
65 long low_mask; /* Mask to modulo into lower half of table */
66 long ffactor; /* Fill factor */
67 long nkeys; /* Number of keys in hash table */
68 long nsegs; /* Number of allocated segments */
69 long keysize; /* hash key length in bytes */
70 long datasize; /* elem data length in bytes */
71 long max_dsize; /* 'dsize' limit if directory is fixed
73 BUCKET_INDEX freeBucketIndex; /* index of first free bucket */
74 #ifdef HASH_STATISTICS
82 HHDR *hctl; /* shared control information */
83 long (*hash) (); /* Hash Function */
84 char *segbase; /* segment base address for calculating
86 SEG_OFFSET *dir; /* 'directory' of segm starts */
87 void *(*alloc) (Size); /* memory allocator */
90 typedef struct hashctl
92 long ssize; /* Segment Size */
93 long dsize; /* Dirsize Size */
94 long ffactor; /* Fill factor */
95 long (*hash) (); /* Hash Function */
96 long keysize; /* hash key length in bytes */
97 long datasize; /* elem data length in bytes */
98 long max_dsize; /* limit to dsize if directory size is
100 long *segbase; /* base for calculating bucket + seg ptrs */
101 void *(*alloc) (Size); /* memory allocation function */
102 long *dir; /* directory if allocated already */
103 long *hctl; /* location of header information in shd
107 /* Flags to indicate action for hctl */
108 #define HASH_SEGMENT 0x002 /* Setting segment size */
109 #define HASH_DIRSIZE 0x004 /* Setting directory size */
110 #define HASH_FFACTOR 0x008 /* Setting fill factor */
111 #define HASH_FUNCTION 0x010 /* Set user defined hash function */
112 #define HASH_ELEM 0x020 /* Setting key/data size */
113 #define HASH_SHARED_MEM 0x040 /* Setting shared mem const */
114 #define HASH_ATTACH 0x080 /* Do not initialize hctl */
115 #define HASH_ALLOC 0x100 /* Setting memory allocator */
118 /* seg_alloc assumes that INVALID_INDEX is 0 */
119 #define INVALID_INDEX (0)
120 #define NO_MAX_DSIZE (-1)
121 /* number of hash buckets allocated at once */
122 #define BUCKET_ALLOC_INCR (30)
124 /* hash_search operations */
134 /* hash_seq status (should be considered an opaque type by callers) */
139 BUCKET_INDEX curIndex;
143 * prototypes from functions in dynahash.c
145 extern HTAB *hash_create(int nelem, HASHCTL *info, int flags);
146 extern void hash_destroy(HTAB *hashp);
147 extern void hash_stats(char *where, HTAB *hashp);
148 extern long *hash_search(HTAB *hashp, char *keyPtr, HASHACTION action,
150 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
151 extern long *hash_seq_search(HASH_SEQ_STATUS *status);
152 extern long hash_estimate_size(long num_entries, long keysize, long datasize);
153 extern long hash_select_dirsize(long num_entries);
156 * prototypes from functions in hashfn.c
158 extern long string_hash(char *key, int keysize);
159 extern long tag_hash(int *key, int keysize);
161 #endif /* HSEARCH_H */