1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/*-------------------------------------------------------------------------
*
* hsearch.h
* for hash tables, particularly hash tables in shared memory
*
*
* Portions Copyright (c) 1996-2000, PostgreSQL, Inc
* Portions Copyright (c) 1994, Regents of the University of California
*
* $Id: hsearch.h,v 1.17 2001/01/02 04:33:24 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#ifndef HSEARCH_H
#define HSEARCH_H
/*
* Constants
*
* A hash table has a top-level "directory", each of whose entries points
* to a "segment" of ssize bucket headers. The maximum number of hash
* buckets is thus dsize * ssize (but dsize may be expansible). Of course,
* the number of records in the table can be larger, but we don't want a
* whole lot of records per bucket or performance goes down.
*
* In a hash table allocated in shared memory, the directory cannot be
* expanded because it must stay at a fixed address. The directory size
* should be selected using hash_select_dirsize (and you'd better have
* a good idea of the maximum number of entries!). For non-shared hash
* tables, the initial directory size can be left at the default.
*/
#define DEF_SEGSIZE 256
#define DEF_SEGSIZE_SHIFT 8/* must be log2(DEF_SEGSIZE) */
#define DEF_DIRSIZE 256
#define DEF_FFACTOR 1/* default fill factor */
#define PRIME1 37 /* for the hash function */
#define PRIME2 1048583
/*
* Hash bucket is actually bigger than this. Key field can have
* variable length and a variable length data field follows it.
*/
typedef struct element
{
unsigned long next; /* secret from user */
long key;
} ELEMENT;
typedef unsigned long BUCKET_INDEX;
/* segment is an array of bucket pointers */
typedef BUCKET_INDEX *SEGMENT;
typedef unsigned long SEG_OFFSET;
typedef struct hashhdr
{
long dsize; /* Directory Size */
long ssize; /* Segment Size --- must be power of 2 */
long sshift; /* Segment shift */
long max_bucket; /* ID of Maximum bucket in use */
long high_mask; /* Mask to modulo into entire table */
long low_mask; /* Mask to modulo into lower half of table */
long ffactor; /* Fill factor */
long nkeys; /* Number of keys in hash table */
long nsegs; /* Number of allocated segments */
long keysize; /* hash key length in bytes */
long datasize; /* elem data length in bytes */
long max_dsize; /* 'dsize' limit if directory is fixed
* size */
BUCKET_INDEX freeBucketIndex; /* index of first free bucket */
#ifdef HASH_STATISTICS
long accesses;
long collisions;
#endif
} HHDR;
typedef struct htab
{
HHDR *hctl; /* shared control information */
long (*hash) (); /* Hash Function */
char *segbase; /* segment base address for calculating
* pointer values */
SEG_OFFSET *dir; /* 'directory' of segm starts */
void *(*alloc) (Size); /* memory allocator */
} HTAB;
typedef struct hashctl
{
long ssize; /* Segment Size */
long dsize; /* Dirsize Size */
long ffactor; /* Fill factor */
long (*hash) (); /* Hash Function */
long keysize; /* hash key length in bytes */
long datasize; /* elem data length in bytes */
long max_dsize; /* limit to dsize if directory size is
* limited */
long *segbase; /* base for calculating bucket + seg ptrs */
void *(*alloc) (Size); /* memory allocation function */
long *dir; /* directory if allocated already */
long *hctl; /* location of header information in shd
* mem */
} HASHCTL;
/* Flags to indicate action for hctl */
#define HASH_SEGMENT 0x002 /* Setting segment size */
#define HASH_DIRSIZE 0x004 /* Setting directory size */
#define HASH_FFACTOR 0x008 /* Setting fill factor */
#define HASH_FUNCTION 0x010 /* Set user defined hash function */
#define HASH_ELEM 0x020 /* Setting key/data size */
#define HASH_SHARED_MEM 0x040 /* Setting shared mem const */
#define HASH_ATTACH 0x080 /* Do not initialize hctl */
#define HASH_ALLOC 0x100 /* Setting memory allocator */
/* seg_alloc assumes that INVALID_INDEX is 0 */
#define INVALID_INDEX (0)
#define NO_MAX_DSIZE (-1)
/* number of hash buckets allocated at once */
#define BUCKET_ALLOC_INCR (30)
/* hash_search operations */
typedef enum
{
HASH_FIND,
HASH_ENTER,
HASH_REMOVE,
HASH_FIND_SAVE,
HASH_REMOVE_SAVED
} HASHACTION;
/* hash_seq status (should be considered an opaque type by callers) */
typedef struct
{
HTAB *hashp;
long curBucket;
BUCKET_INDEX curIndex;
} HASH_SEQ_STATUS;
/*
* prototypes from functions in dynahash.c
*/
extern HTAB *hash_create(int nelem, HASHCTL *info, int flags);
extern void hash_destroy(HTAB *hashp);
extern void hash_stats(char *where, HTAB *hashp);
extern long *hash_search(HTAB *hashp, char *keyPtr, HASHACTION action,
bool *foundPtr);
extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
extern long *hash_seq_search(HASH_SEQ_STATUS *status);
extern long hash_estimate_size(long num_entries, long keysize, long datasize);
extern long hash_select_dirsize(long num_entries);
/*
* prototypes from functions in hashfn.c
*/
extern long string_hash(char *key, int keysize);
extern long tag_hash(int *key, int keysize);
#endif /* HSEARCH_H */
|
