X-Git-Url: https://granicus.if.org/sourcecode?a=blobdiff_plain;f=src%2Finclude%2Futils%2Fhsearch.h;h=dfdf658ddf0dcacbca98885073798eb4be0da03b;hb=4a14f13a0abfbf7e7d44a3d2689444d1806aa9dc;hp=9773dc733f3be4c4ed3a6ae621a35f09d25b7d3b;hpb=2ff501590b323bde14f7e662fd89ad12a4d2f4e0;p=postgresql diff --git a/src/include/utils/hsearch.h b/src/include/utils/hsearch.h index 9773dc733f..dfdf658ddf 100644 --- a/src/include/utils/hsearch.h +++ b/src/include/utils/hsearch.h @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------- * * hsearch.h - * for hash tables, particularly hash tables in shared memory + * exported definitions for utils/hash/dynahash.c; see notes therein * * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/utils/hsearch.h,v 1.34 2004/12/31 22:03:46 pgsql Exp $ + * src/include/utils/hsearch.h * *------------------------------------------------------------------------- */ @@ -16,15 +16,26 @@ /* - * Hash and comparison functions must have these signatures. Comparison - * functions return zero for match, nonzero for no match. (The comparison - * function definition is designed to allow memcmp() and strncmp() to be - * used directly as key comparison functions.) + * Hash functions must have this signature. */ typedef uint32 (*HashValueFunc) (const void *key, Size keysize); + +/* + * Key comparison functions must have this signature. Comparison functions + * return zero for match, nonzero for no match. (The comparison function + * definition is designed to allow memcmp() and strncmp() to be used directly + * as key comparison functions.) + */ typedef int (*HashCompareFunc) (const void *key1, const void *key2, Size keysize); +/* + * Key copying functions must have this signature. The return value is not + * used. (The definition is set up to allow memcpy() and strlcpy() to be + * used directly.) + */ +typedef void *(*HashCopyFunc) (void *dest, const void *src, Size keysize); + /* * Space allocation function for a hashtable --- designed to match malloc(). * Note: there is no free function API; can't destroy a hashtable unless you @@ -32,27 +43,6 @@ typedef int (*HashCompareFunc) (const void *key1, const void *key2, */ typedef void *(*HashAllocFunc) (Size request); -/* - * 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 @@ -64,88 +54,50 @@ typedef struct HASHELEMENT uint32 hashvalue; /* hash function result for this entry */ } HASHELEMENT; -/* A hash bucket is a linked list of HASHELEMENTs */ -typedef HASHELEMENT *HASHBUCKET; +/* Hash table header struct is an opaque type known only within dynahash.c */ +typedef struct HASHHDR HASHHDR; -/* 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 */ - Size keysize; /* hash key length in bytes */ - Size 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 */ - HashValueFunc hash; /* hash function */ - HashCompareFunc match; /* key comparison function */ - HashAllocFunc alloc; /* 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 */ -} HTAB; +/* Hash table control struct is an opaque type known only within dynahash.c */ +typedef struct HTAB 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 max_dsize; /* limit to dsize if directory size is - * limited */ - long ffactor; /* Fill factor */ + long num_partitions; /* # partitions (must be power of 2) */ + long ssize; /* segment size */ + long dsize; /* (initial) directory size */ + long max_dsize; /* limit to dsize if dir size is limited */ + long ffactor; /* fill factor */ Size keysize; /* hash key length in bytes */ Size entrysize; /* total user element size in bytes */ HashValueFunc hash; /* hash function */ HashCompareFunc match; /* key comparison function */ + HashCopyFunc keycopy; /* key copying function */ HashAllocFunc alloc; /* memory allocator */ - HASHSEGMENT *dir; /* directory of segment starts */ - HASHHDR *hctl; /* location of header in shared mem */ MemoryContext hcxt; /* memory context to use for allocations */ + HASHHDR *hctl; /* location of header in shared mem */ } HASHCTL; /* Flags to indicate which parameters are supplied */ -#define HASH_SEGMENT 0x002 /* Set segment size */ -#define HASH_DIRSIZE 0x004 /* Set directory size */ -#define HASH_FFACTOR 0x008 /* Set fill factor */ -#define HASH_FUNCTION 0x010 /* Set user defined hash function */ -#define HASH_ELEM 0x020 /* Set key/entry size */ -#define HASH_SHARED_MEM 0x040 /* Hashtable is in shared memory */ -#define HASH_ATTACH 0x080 /* Do not initialize hctl */ -#define HASH_ALLOC 0x100 /* Set memory allocator */ -#define HASH_CONTEXT 0x200 /* Set explicit memory context */ -#define HASH_COMPARE 0x400 /* Set user defined comparison function */ +#define HASH_PARTITION 0x0001 /* Hashtable is used w/partitioned locking */ +#define HASH_SEGMENT 0x0002 /* Set segment size */ +#define HASH_DIRSIZE 0x0004 /* Set directory size (initial and max) */ +#define HASH_FFACTOR 0x0008 /* Set fill factor */ +#define HASH_ELEM 0x0010 /* Set keysize and entrysize */ +#define HASH_BLOBS 0x0020 /* Select support functions for binary keys */ +#define HASH_FUNCTION 0x0040 /* Set user defined hash function */ +#define HASH_COMPARE 0x0080 /* Set user defined comparison function */ +#define HASH_KEYCOPY 0x0100 /* Set user defined key-copying function */ +#define HASH_ALLOC 0x0200 /* Set memory allocator */ +#define HASH_CONTEXT 0x0400 /* Set memory allocation context */ +#define HASH_SHARED_MEM 0x0800 /* Hashtable is in shared memory */ +#define HASH_ATTACH 0x1000 /* Do not initialize hctl */ +#define HASH_FIXED_SIZE 0x2000 /* Initial size is a hard limit */ /* 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 @@ -153,8 +105,7 @@ typedef enum HASH_FIND, HASH_ENTER, HASH_REMOVE, - HASH_FIND_SAVE, - HASH_REMOVE_SAVED + HASH_ENTER_NULL } HASHACTION; /* hash_seq status (should be considered an opaque type by callers) */ @@ -174,15 +125,36 @@ extern void hash_destroy(HTAB *hashp); extern void hash_stats(const char *where, HTAB *hashp); extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr); +extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr); +extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, + uint32 hashvalue, HASHACTION action, + bool *foundPtr); +extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry, + const void *newKeyPtr); +extern long hash_get_num_entries(HTAB *hashp); extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp); extern void *hash_seq_search(HASH_SEQ_STATUS *status); -extern long hash_estimate_size(long num_entries, Size entrysize); +extern void hash_seq_term(HASH_SEQ_STATUS *status); +extern void hash_freeze(HTAB *hashp); +extern Size hash_estimate_size(long num_entries, Size entrysize); extern long hash_select_dirsize(long num_entries); +extern Size hash_get_shared_size(HASHCTL *info, int flags); +extern void AtEOXact_HashTables(bool isCommit); +extern void AtEOSubXact_HashTables(bool isCommit, int nestDepth); /* * prototypes for functions in hashfn.c + * + * Note: It is deprecated for callers of hash_create to explicitly specify + * string_hash, tag_hash, uint32_hash, or oid_hash. Just set HASH_BLOBS or + * not. Use HASH_FUNCTION only when you want something other than those. */ extern uint32 string_hash(const void *key, Size keysize); extern uint32 tag_hash(const void *key, Size keysize); +extern uint32 uint32_hash(const void *key, Size keysize); +extern uint32 bitmap_hash(const void *key, Size keysize); +extern int bitmap_match(const void *key1, const void *key2, Size keysize); + +#define oid_hash uint32_hash /* Remove me eventually */ #endif /* HSEARCH_H */