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
162
163
164
165
166
167
168
169
170
171
172
|
/*-------------------------------------------------------------------------
*
* hsearch.h
* for hash tables, particularly hash tables in shared memory
*
*
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* $Id: hsearch.h,v 1.27.2.1 2007/04/26 23:25:48 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 */
/*
* HASHELEMENT is the private part of a hashtable entry. The caller's data
* follows the HASHELEMENT structure (on a MAXALIGN'd boundary). The hash key
* is expected to be at the start of the caller's hash entry data structure.
*/
typedef struct HASHELEMENT
{
struct HASHELEMENT *link; /* link to next entry in same bucket */
} HASHELEMENT;
/* A hash bucket is a linked list of HASHELEMENTs */
typedef HASHELEMENT *HASHBUCKET;
/* A hash segment is an array of bucket headers */
typedef HASHBUCKET *HASHSEGMENT;
/* Header structure for a hash table --- contains all changeable info */
typedef struct HASHHDR
{
long dsize; /* Directory Size */
long ssize; /* Segment Size --- must be power of 2 */
int sshift; /* Segment shift = log2(ssize) */
uint32 max_bucket; /* ID of Maximum bucket in use */
uint32 high_mask; /* Mask to modulo into entire table */
uint32 low_mask; /* Mask to modulo into lower half of table */
long ffactor; /* Fill factor */
long nentries; /* Number of entries in hash table */
long nsegs; /* Number of allocated segments */
long keysize; /* hash key length in bytes */
long entrysize; /* total user element size in bytes */
long max_dsize; /* 'dsize' limit if directory is fixed
* size */
HASHELEMENT *freeList; /* linked list of free elements */
#ifdef HASH_STATISTICS
long accesses;
long collisions;
#endif
} HASHHDR;
/*
* Top control structure for a hashtable --- need not be shared, since
* no fields change at runtime
*/
typedef struct HTAB
{
HASHHDR *hctl; /* shared control information */
HASHSEGMENT *dir; /* directory of segment starts */
uint32 (*hash) (void *key, int keysize); /* Hash Function */
void *(*alloc) (Size); /* memory allocator */
MemoryContext hcxt; /* memory context if default allocator
* used */
char *tabname; /* table name (for error messages) */
bool isshared; /* true if table is in shared memory */
/* freezing a shared table isn't allowed, so we can keep state here */
bool frozen; /* true = no more inserts allowed */
} HTAB;
/* Parameter data structure for hash_create */
/* Only those fields indicated by hash_flags need be set */
typedef struct HASHCTL
{
long ssize; /* Segment Size */
long dsize; /* (initial) Directory Size */
long ffactor; /* Fill factor */
uint32 (*hash) (void *key, int keysize); /* Hash Function */
long keysize; /* hash key length in bytes */
long entrysize; /* total user element size in bytes */
long max_dsize; /* limit to dsize if directory size is
* limited */
void *(*alloc) (Size); /* memory allocation function */
HASHSEGMENT *dir; /* directory of segment starts */
HASHHDR *hctl; /* location of header in shared mem */
MemoryContext hcxt; /* memory context to use for allocations */
} HASHCTL;
/* Flags to indicate which parameters are supplied */
#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/entry 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 */
#define HASH_CONTEXT 0x200 /* Setting explicit memory context */
/* max_dsize value to indicate expansible directory */
#define NO_MAX_DSIZE (-1)
/* number of hash elements allocated at once */
#define HASHELEMENT_ALLOC_INCR (32)
/* 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;
uint32 curBucket; /* index of current bucket */
HASHELEMENT *curEntry; /* current entry in bucket */
} HASH_SEQ_STATUS;
/*
* prototypes for functions in dynahash.c
*/
extern HTAB *hash_create(const char *tabname, long nelem,
HASHCTL *info, int flags);
extern void hash_destroy(HTAB *hashp);
extern void hash_stats(const char *where, HTAB *hashp);
extern void *hash_search(HTAB *hashp, void *keyPtr, HASHACTION action,
bool *foundPtr);
extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
extern void *hash_seq_search(HASH_SEQ_STATUS *status);
extern void hash_seq_term(HASH_SEQ_STATUS *status);
extern void hash_freeze(HTAB *hashp);
extern long hash_estimate_size(long num_entries, long entrysize);
extern long hash_select_dirsize(long num_entries);
extern void AtEOXact_HashTables(bool isCommit);
/*
* prototypes for functions in hashfn.c
*/
extern uint32 string_hash(void *key, int keysize);
extern uint32 tag_hash(void *key, int keysize);
#endif /* HSEARCH_H */
|
