PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
hsearch.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  HASHELEMENT
 
struct  HASHCTL
 
struct  HASH_SEQ_STATUS
 

Macros

#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_ELEM   0x0008 /* Set keysize and entrysize (now required!) */
 
#define HASH_STRINGS   0x0010 /* Select support functions for string keys */
 
#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 */
 
#define NO_MAX_DSIZE   (-1)
 

Typedefs

typedef uint32(* HashValueFunc) (const void *key, Size keysize)
 
typedef int(* HashCompareFunc) (const void *key1, const void *key2, Size keysize)
 
typedef void *(* HashCopyFunc) (void *dest, const void *src, Size keysize)
 
typedef void *(* HashAllocFunc) (Size request)
 
typedef struct HASHELEMENT HASHELEMENT
 
typedef struct HASHHDR HASHHDR
 
typedef struct HTAB HTAB
 
typedef struct HASHCTL HASHCTL
 

Enumerations

enum  HASHACTION { HASH_FIND , HASH_ENTER , HASH_REMOVE , HASH_ENTER_NULL }
 

Functions

HTABhash_create (const char *tabname, long nelem, const HASHCTL *info, int flags)
 
void hash_destroy (HTAB *hashp)
 
void hash_stats (const char *where, HTAB *hashp)
 
void * hash_search (HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
 
uint32 get_hash_value (HTAB *hashp, const void *keyPtr)
 
void * hash_search_with_hash_value (HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
 
bool hash_update_hash_key (HTAB *hashp, void *existingEntry, const void *newKeyPtr)
 
long hash_get_num_entries (HTAB *hashp)
 
void hash_seq_init (HASH_SEQ_STATUS *status, HTAB *hashp)
 
void hash_seq_init_with_hash_value (HASH_SEQ_STATUS *status, HTAB *hashp, uint32 hashvalue)
 
void * hash_seq_search (HASH_SEQ_STATUS *status)
 
void hash_seq_term (HASH_SEQ_STATUS *status)
 
void hash_freeze (HTAB *hashp)
 
Size hash_estimate_size (long num_entries, Size entrysize)
 
long hash_select_dirsize (long num_entries)
 
Size hash_get_shared_size (HASHCTL *info, int flags)
 
void AtEOXact_HashTables (bool isCommit)
 
void AtEOSubXact_HashTables (bool isCommit, int nestDepth)
 

Macro Definition Documentation

◆ HASH_ALLOC

#define HASH_ALLOC   0x0200 /* Set memory allocator */

Definition at line 101 of file hsearch.h.

◆ HASH_ATTACH

#define HASH_ATTACH   0x1000 /* Do not initialize hctl */

Definition at line 104 of file hsearch.h.

◆ HASH_BLOBS

#define HASH_BLOBS   0x0020 /* Select support functions for binary keys */

Definition at line 97 of file hsearch.h.

◆ HASH_COMPARE

#define HASH_COMPARE   0x0080 /* Set user defined comparison function */

Definition at line 99 of file hsearch.h.

◆ HASH_CONTEXT

#define HASH_CONTEXT   0x0400 /* Set memory allocation context */

Definition at line 102 of file hsearch.h.

◆ HASH_DIRSIZE

#define HASH_DIRSIZE   0x0004 /* Set directory size (initial and max) */

Definition at line 94 of file hsearch.h.

◆ HASH_ELEM

#define HASH_ELEM   0x0008 /* Set keysize and entrysize (now required!) */

Definition at line 95 of file hsearch.h.

◆ HASH_FIXED_SIZE

#define HASH_FIXED_SIZE   0x2000 /* Initial size is a hard limit */

Definition at line 105 of file hsearch.h.

◆ HASH_FUNCTION

#define HASH_FUNCTION   0x0040 /* Set user defined hash function */

Definition at line 98 of file hsearch.h.

◆ HASH_KEYCOPY

#define HASH_KEYCOPY   0x0100 /* Set user defined key-copying function */

Definition at line 100 of file hsearch.h.

◆ HASH_PARTITION

#define HASH_PARTITION   0x0001 /* Hashtable is used w/partitioned locking */

Definition at line 92 of file hsearch.h.

◆ HASH_SEGMENT

#define HASH_SEGMENT   0x0002 /* Set segment size */

Definition at line 93 of file hsearch.h.

◆ HASH_SHARED_MEM

#define HASH_SHARED_MEM   0x0800 /* Hashtable is in shared memory */

Definition at line 103 of file hsearch.h.

◆ HASH_STRINGS

#define HASH_STRINGS   0x0010 /* Select support functions for string keys */

Definition at line 96 of file hsearch.h.

◆ NO_MAX_DSIZE

#define NO_MAX_DSIZE   (-1)

Definition at line 108 of file hsearch.h.

Typedef Documentation

◆ HashAllocFunc

typedef void *(* HashAllocFunc) (Size request)

Definition at line 44 of file hsearch.h.

◆ HashCompareFunc

typedef int(* HashCompareFunc) (const void *key1, const void *key2, Size keysize)

Definition at line 29 of file hsearch.h.

◆ HashCopyFunc

typedef void *(* HashCopyFunc) (void *dest, const void *src, Size keysize)

Definition at line 37 of file hsearch.h.

◆ HASHCTL

typedef struct HASHCTL HASHCTL

◆ HASHELEMENT

typedef struct HASHELEMENT HASHELEMENT

◆ HASHHDR

typedef struct HASHHDR HASHHDR

Definition at line 58 of file hsearch.h.

◆ HashValueFunc

typedef uint32(* HashValueFunc) (const void *key, Size keysize)

Definition at line 21 of file hsearch.h.

◆ HTAB

typedef struct HTAB HTAB

Definition at line 61 of file hsearch.h.

Enumeration Type Documentation

◆ HASHACTION

enum HASHACTION
Enumerator
HASH_FIND 
HASH_ENTER 
HASH_REMOVE 
HASH_ENTER_NULL 

Definition at line 111 of file hsearch.h.

112{
113 HASH_FIND,
117} HASHACTION;
HASHACTION
Definition: hsearch.h:112
@ HASH_FIND
Definition: hsearch.h:113
@ HASH_REMOVE
Definition: hsearch.h:115
@ HASH_ENTER
Definition: hsearch.h:114
@ HASH_ENTER_NULL
Definition: hsearch.h:116

Function Documentation

◆ AtEOSubXact_HashTables()

void AtEOSubXact_HashTables ( bool  isCommit,
int  nestDepth 
)

Definition at line 1938 of file dynahash.c.

1939{
1940 int i;
1941
1942 /*
1943 * Search backward to make cleanup easy. Note we must check all entries,
1944 * not only those at the end of the array, because deletion technique
1945 * doesn't keep them in order.
1946 */
1947 for (i = num_seq_scans - 1; i >= 0; i--)
1948 {
1949 if (seq_scan_level[i] >= nestDepth)
1950 {
1951 if (isCommit)
1952 elog(WARNING, "leaked hash_seq_search scan for hash table %p",
1956 num_seq_scans--;
1957 }
1958 }
1959}
static HTAB * seq_scan_tables[MAX_SEQ_SCANS]
Definition: dynahash.c:1858
static int seq_scan_level[MAX_SEQ_SCANS]
Definition: dynahash.c:1859
static int num_seq_scans
Definition: dynahash.c:1860
#define WARNING
Definition: elog.h:36
#define elog(elevel,...)
Definition: elog.h:226
int i
Definition: isn.c:77

References elog, i, num_seq_scans, seq_scan_level, seq_scan_tables, and WARNING.

Referenced by AbortSubTransaction(), and CommitSubTransaction().

◆ AtEOXact_HashTables()

void AtEOXact_HashTables ( bool  isCommit)

Definition at line 1912 of file dynahash.c.

1913{
1914 /*
1915 * During abort cleanup, open scans are expected; just silently clean 'em
1916 * out. An open scan at commit means someone forgot a hash_seq_term()
1917 * call, so complain.
1918 *
1919 * Note: it's tempting to try to print the tabname here, but refrain for
1920 * fear of touching deallocated memory. This isn't a user-facing message
1921 * anyway, so it needn't be pretty.
1922 */
1923 if (isCommit)
1924 {
1925 int i;
1926
1927 for (i = 0; i < num_seq_scans; i++)
1928 {
1929 elog(WARNING, "leaked hash_seq_search scan for hash table %p",
1931 }
1932 }
1933 num_seq_scans = 0;
1934}

References elog, i, num_seq_scans, seq_scan_tables, and WARNING.

Referenced by AbortTransaction(), AutoVacLauncherMain(), BackgroundWriterMain(), CheckpointerMain(), CommitTransaction(), pgarch_archiveXlog(), PrepareTransaction(), WalSummarizerMain(), and WalWriterMain().

◆ get_hash_value()

uint32 get_hash_value ( HTAB hashp,
const void *  keyPtr 
)

Definition at line 911 of file dynahash.c.

912{
913 return hashp->hash(keyPtr, hashp->keysize);
914}
HashValueFunc hash
Definition: dynahash.c:223
Size keysize
Definition: dynahash.c:236

References HTAB::hash, and HTAB::keysize.

Referenced by BufTableHashCode(), LockTagHashCode(), and lookup_type_cache().

◆ hash_create()

HTAB * hash_create ( const char *  tabname,
long  nelem,
const HASHCTL info,
int  flags 
)

Definition at line 352 of file dynahash.c.

353{
354 HTAB *hashp;
355 HASHHDR *hctl;
356
357 /*
358 * Hash tables now allocate space for key and data, but you have to say
359 * how much space to allocate.
360 */
361 Assert(flags & HASH_ELEM);
362 Assert(info->keysize > 0);
363 Assert(info->entrysize >= info->keysize);
364
365 /*
366 * For shared hash tables, we have a local hash header (HTAB struct) that
367 * we allocate in TopMemoryContext; all else is in shared memory.
368 *
369 * For non-shared hash tables, everything including the hash header is in
370 * a memory context created specially for the hash table --- this makes
371 * hash_destroy very simple. The memory context is made a child of either
372 * a context specified by the caller, or TopMemoryContext if nothing is
373 * specified.
374 */
375 if (flags & HASH_SHARED_MEM)
376 {
377 /* Set up to allocate the hash header */
379 }
380 else
381 {
382 /* Create the hash table's private memory context */
383 if (flags & HASH_CONTEXT)
384 CurrentDynaHashCxt = info->hcxt;
385 else
388 "dynahash",
390 }
391
392 /* Initialize the hash header, plus a copy of the table name */
393 hashp = (HTAB *) DynaHashAlloc(sizeof(HTAB) + strlen(tabname) + 1);
394 MemSet(hashp, 0, sizeof(HTAB));
395
396 hashp->tabname = (char *) (hashp + 1);
397 strcpy(hashp->tabname, tabname);
398
399 /* If we have a private context, label it with hashtable's name */
400 if (!(flags & HASH_SHARED_MEM))
402
403 /*
404 * Select the appropriate hash function (see comments at head of file).
405 */
406 if (flags & HASH_FUNCTION)
407 {
408 Assert(!(flags & (HASH_BLOBS | HASH_STRINGS)));
409 hashp->hash = info->hash;
410 }
411 else if (flags & HASH_BLOBS)
412 {
413 Assert(!(flags & HASH_STRINGS));
414 /* We can optimize hashing for common key sizes */
415 if (info->keysize == sizeof(uint32))
416 hashp->hash = uint32_hash;
417 else
418 hashp->hash = tag_hash;
419 }
420 else
421 {
422 /*
423 * string_hash used to be considered the default hash method, and in a
424 * non-assert build it effectively still is. But we now consider it
425 * an assertion error to not say HASH_STRINGS explicitly. To help
426 * catch mistaken usage of HASH_STRINGS, we also insist on a
427 * reasonably long string length: if the keysize is only 4 or 8 bytes,
428 * it's almost certainly an integer or pointer not a string.
429 */
430 Assert(flags & HASH_STRINGS);
431 Assert(info->keysize > 8);
432
433 hashp->hash = string_hash;
434 }
435
436 /*
437 * If you don't specify a match function, it defaults to string_compare if
438 * you used string_hash, and to memcmp otherwise.
439 *
440 * Note: explicitly specifying string_hash is deprecated, because this
441 * might not work for callers in loadable modules on some platforms due to
442 * referencing a trampoline instead of the string_hash function proper.
443 * Specify HASH_STRINGS instead.
444 */
445 if (flags & HASH_COMPARE)
446 hashp->match = info->match;
447 else if (hashp->hash == string_hash)
449 else
450 hashp->match = memcmp;
451
452 /*
453 * Similarly, the key-copying function defaults to strlcpy or memcpy.
454 */
455 if (flags & HASH_KEYCOPY)
456 hashp->keycopy = info->keycopy;
457 else if (hashp->hash == string_hash)
458 {
459 /*
460 * The signature of keycopy is meant for memcpy(), which returns
461 * void*, but strlcpy() returns size_t. Since we never use the return
462 * value of keycopy, and size_t is pretty much always the same size as
463 * void *, this should be safe. The extra cast in the middle is to
464 * avoid warnings from -Wcast-function-type.
465 */
467 }
468 else
469 hashp->keycopy = memcpy;
470
471 /* And select the entry allocation function, too. */
472 if (flags & HASH_ALLOC)
473 hashp->alloc = info->alloc;
474 else
475 hashp->alloc = DynaHashAlloc;
476
477 if (flags & HASH_SHARED_MEM)
478 {
479 /*
480 * ctl structure and directory are preallocated for shared memory
481 * tables. Note that HASH_DIRSIZE and HASH_ALLOC had better be set as
482 * well.
483 */
484 hashp->hctl = info->hctl;
485 hashp->dir = (HASHSEGMENT *) (((char *) info->hctl) + sizeof(HASHHDR));
486 hashp->hcxt = NULL;
487 hashp->isshared = true;
488
489 /* hash table already exists, we're just attaching to it */
490 if (flags & HASH_ATTACH)
491 {
492 /* make local copies of some heavily-used values */
493 hctl = hashp->hctl;
494 hashp->keysize = hctl->keysize;
495 hashp->ssize = hctl->ssize;
496 hashp->sshift = hctl->sshift;
497
498 return hashp;
499 }
500 }
501 else
502 {
503 /* setup hash table defaults */
504 hashp->hctl = NULL;
505 hashp->dir = NULL;
506 hashp->hcxt = CurrentDynaHashCxt;
507 hashp->isshared = false;
508 }
509
510 if (!hashp->hctl)
511 {
512 hashp->hctl = (HASHHDR *) hashp->alloc(sizeof(HASHHDR));
513 if (!hashp->hctl)
515 (errcode(ERRCODE_OUT_OF_MEMORY),
516 errmsg("out of memory")));
517 }
518
519 hashp->frozen = false;
520
521 hdefault(hashp);
522
523 hctl = hashp->hctl;
524
525 if (flags & HASH_PARTITION)
526 {
527 /* Doesn't make sense to partition a local hash table */
528 Assert(flags & HASH_SHARED_MEM);
529
530 /*
531 * The number of partitions had better be a power of 2. Also, it must
532 * be less than INT_MAX (see init_htab()), so call the int version of
533 * next_pow2.
534 */
536
537 hctl->num_partitions = info->num_partitions;
538 }
539
540 if (flags & HASH_SEGMENT)
541 {
542 hctl->ssize = info->ssize;
543 hctl->sshift = my_log2(info->ssize);
544 /* ssize had better be a power of 2 */
545 Assert(hctl->ssize == (1L << hctl->sshift));
546 }
547
548 /*
549 * SHM hash tables have fixed directory size passed by the caller.
550 */
551 if (flags & HASH_DIRSIZE)
552 {
553 hctl->max_dsize = info->max_dsize;
554 hctl->dsize = info->dsize;
555 }
556
557 /* remember the entry sizes, too */
558 hctl->keysize = info->keysize;
559 hctl->entrysize = info->entrysize;
560
561 /* make local copies of heavily-used constant fields */
562 hashp->keysize = hctl->keysize;
563 hashp->ssize = hctl->ssize;
564 hashp->sshift = hctl->sshift;
565
566 /* Build the hash directory structure */
567 if (!init_htab(hashp, nelem))
568 elog(ERROR, "failed to initialize hash table \"%s\"", hashp->tabname);
569
570 /*
571 * For a shared hash table, preallocate the requested number of elements.
572 * This reduces problems with run-time out-of-shared-memory conditions.
573 *
574 * For a non-shared hash table, preallocate the requested number of
575 * elements if it's less than our chosen nelem_alloc. This avoids wasting
576 * space if the caller correctly estimates a small table size.
577 */
578 if ((flags & HASH_SHARED_MEM) ||
579 nelem < hctl->nelem_alloc)
580 {
581 int i,
582 freelist_partitions,
583 nelem_alloc,
584 nelem_alloc_first;
585
586 /*
587 * If hash table is partitioned, give each freelist an equal share of
588 * the initial allocation. Otherwise only freeList[0] is used.
589 */
590 if (IS_PARTITIONED(hashp->hctl))
591 freelist_partitions = NUM_FREELISTS;
592 else
593 freelist_partitions = 1;
594
595 nelem_alloc = nelem / freelist_partitions;
596 if (nelem_alloc <= 0)
597 nelem_alloc = 1;
598
599 /*
600 * Make sure we'll allocate all the requested elements; freeList[0]
601 * gets the excess if the request isn't divisible by NUM_FREELISTS.
602 */
603 if (nelem_alloc * freelist_partitions < nelem)
604 nelem_alloc_first =
605 nelem - nelem_alloc * (freelist_partitions - 1);
606 else
607 nelem_alloc_first = nelem_alloc;
608
609 for (i = 0; i < freelist_partitions; i++)
610 {
611 int temp = (i == 0) ? nelem_alloc_first : nelem_alloc;
612
613 if (!element_alloc(hashp, temp, i))
615 (errcode(ERRCODE_OUT_OF_MEMORY),
616 errmsg("out of memory")));
617 }
618 }
619
620 if (flags & HASH_FIXED_SIZE)
621 hashp->isfixed = true;
622 return hashp;
623}
uint32_t uint32
Definition: c.h:502
#define MemSet(start, val, len)
Definition: c.h:991
void(* pg_funcptr_t)(void)
Definition: c.h:424
static void * DynaHashAlloc(Size size)
Definition: dynahash.c:291
static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx)
Definition: dynahash.c:1706
static bool init_htab(HTAB *hashp, long nelem)
Definition: dynahash.c:689
static MemoryContext CurrentDynaHashCxt
Definition: dynahash.c:288
static int next_pow2_int(long num)
Definition: dynahash.c:1820
#define IS_PARTITIONED(hctl)
Definition: dynahash.c:210
#define NUM_FREELISTS
Definition: dynahash.c:128
static int string_compare(const char *key1, const char *key2, Size keysize)
Definition: dynahash.c:307
static void hdefault(HTAB *hashp)
Definition: dynahash.c:629
int my_log2(long num)
Definition: dynahash.c:1794
int errcode(int sqlerrcode)
Definition: elog.c:854
int errmsg(const char *fmt,...)
Definition: elog.c:1071
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:677
uint32 uint32_hash(const void *key, Size keysize)
Definition: hashfn.c:688
uint32 string_hash(const void *key, Size keysize)
Definition: hashfn.c:660
Assert(PointerIsAligned(start, uint64))
#define HASH_KEYCOPY
Definition: hsearch.h:100
#define HASH_STRINGS
Definition: hsearch.h:96
int(* HashCompareFunc)(const void *key1, const void *key2, Size keysize)
Definition: hsearch.h:29
#define HASH_CONTEXT
Definition: hsearch.h:102
#define HASH_ELEM
Definition: hsearch.h:95
#define HASH_ALLOC
Definition: hsearch.h:101
#define HASH_DIRSIZE
Definition: hsearch.h:94
#define HASH_SEGMENT
Definition: hsearch.h:93
#define HASH_ATTACH
Definition: hsearch.h:104
#define HASH_COMPARE
Definition: hsearch.h:99
#define HASH_FUNCTION
Definition: hsearch.h:98
#define HASH_BLOBS
Definition: hsearch.h:97
#define HASH_SHARED_MEM
Definition: hsearch.h:103
#define HASH_FIXED_SIZE
Definition: hsearch.h:105
#define HASH_PARTITION
Definition: hsearch.h:92
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
Definition: hsearch.h:37
MemoryContext TopMemoryContext
Definition: mcxt.c:165
void MemoryContextSetIdentifier(MemoryContext context, const char *id)
Definition: mcxt.c:643
#define AllocSetContextCreate
Definition: memutils.h:149
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:180
size_t strlcpy(char *dst, const char *src, size_t siz)
Definition: strlcpy.c:45
long ssize
Definition: hsearch.h:70
HashAllocFunc alloc
Definition: hsearch.h:84
Size keysize
Definition: hsearch.h:75
HashValueFunc hash
Definition: hsearch.h:78
Size entrysize
Definition: hsearch.h:76
long dsize
Definition: hsearch.h:72
HashCompareFunc match
Definition: hsearch.h:80
HASHHDR * hctl
Definition: hsearch.h:88
MemoryContext hcxt
Definition: hsearch.h:86
long num_partitions
Definition: hsearch.h:68
HashCopyFunc keycopy
Definition: hsearch.h:82
long max_dsize
Definition: hsearch.h:73
long max_dsize
Definition: dynahash.c:194
long num_partitions
Definition: dynahash.c:193
Size entrysize
Definition: dynahash.c:192
Size keysize
Definition: dynahash.c:191
int sshift
Definition: dynahash.c:196
long ssize
Definition: dynahash.c:195
long dsize
Definition: dynahash.c:184
Definition: dynahash.c:220
bool isfixed
Definition: dynahash.c:230
bool isshared
Definition: dynahash.c:229
HashCompareFunc match
Definition: dynahash.c:224
char * tabname
Definition: dynahash.c:228
HASHHDR * hctl
Definition: dynahash.c:221
MemoryContext hcxt
Definition: dynahash.c:227
HashAllocFunc alloc
Definition: dynahash.c:226
long ssize
Definition: dynahash.c:237
HASHSEGMENT * dir
Definition: dynahash.c:222
int sshift
Definition: dynahash.c:238
HashCopyFunc keycopy
Definition: dynahash.c:225
bool frozen
Definition: dynahash.c:233

References HTAB::alloc, HASHCTL::alloc, ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), CurrentDynaHashCxt, HTAB::dir, HASHHDR::dsize, HASHCTL::dsize, DynaHashAlloc(), element_alloc(), elog, HASHHDR::entrysize, HASHCTL::entrysize, ereport, errcode(), errmsg(), ERROR, HTAB::frozen, HTAB::hash, HASHCTL::hash, HASH_ALLOC, HASH_ATTACH, HASH_BLOBS, HASH_COMPARE, HASH_CONTEXT, HASH_DIRSIZE, HASH_ELEM, HASH_FIXED_SIZE, HASH_FUNCTION, HASH_KEYCOPY, HASH_PARTITION, HASH_SEGMENT, HASH_SHARED_MEM, HASH_STRINGS, HTAB::hctl, HASHCTL::hctl, HTAB::hcxt, HASHCTL::hcxt, hdefault(), i, init_htab(), IS_PARTITIONED, HTAB::isfixed, HTAB::isshared, HTAB::keycopy, HASHCTL::keycopy, HASHHDR::keysize, HTAB::keysize, HASHCTL::keysize, HTAB::match, HASHCTL::match, HASHHDR::max_dsize, HASHCTL::max_dsize, MemoryContextSetIdentifier(), MemSet, my_log2(), next_pow2_int(), NUM_FREELISTS, HASHHDR::num_partitions, HASHCTL::num_partitions, HASHHDR::sshift, HTAB::sshift, HASHHDR::ssize, HTAB::ssize, HASHCTL::ssize, string_compare(), string_hash(), strlcpy(), HTAB::tabname, tag_hash(), TopMemoryContext, and uint32_hash().

Referenced by _hash_finish_split(), _PG_init(), AddEventToPendingNotifies(), AddPendingSync(), assign_record_type_typmod(), begin_heap_rewrite(), build_colinfo_names_hash(), build_guc_variables(), build_join_rel_hash(), BuildEventTriggerCache(), cfunc_hashtable_init(), CheckForSessionAndXactLocks(), CompactCheckpointerRequestQueue(), compute_array_stats(), compute_tsvector_stats(), create_seq_hashtable(), createConnHash(), CreateLocalPredicateLockHash(), CreatePartitionDirectory(), do_autovacuum(), EnablePortalManager(), ExecInitModifyTable(), ExecuteTruncateGuts(), find_all_inheritors(), find_oper_cache_entry(), find_rendezvous_variable(), get_json_object_as_hash(), GetComboCommandId(), GetConnection(), gistInitBuildBuffers(), gistInitParentMap(), init_missing_cache(), init_procedure_caches(), init_rel_sync_cache(), init_timezone_hashtable(), init_ts_config_cache(), init_uncommitted_enum_types(), init_uncommitted_enum_values(), InitBufferManagerAccess(), InitializeAttoptCache(), InitializeRelfilenumberMap(), InitializeShippableCache(), InitializeTableSpaceCache(), InitLocalBuffers(), InitLockManagerAccess(), InitQueryHashTable(), InitRecoveryTransactionEnvironment(), InitSync(), json_unique_check_init(), load_categories_hash(), log_invalid_page(), logical_begin_heap_rewrite(), logicalrep_partmap_init(), logicalrep_relmap_init(), lookup_proof_cache(), lookup_ts_dictionary_cache(), lookup_ts_parser_cache(), lookup_type_cache(), LookupOpclassInfo(), pa_allocate_worker(), pg_get_backend_memory_contexts(), plpgsql_estate_setup(), PLy_add_exceptions(), populate_recordset_object_start(), process_syncing_tables_for_apply(), ProcessGetMemoryContextInterrupt(), rebuild_database_list(), record_C_func(), RegisterExtensibleNodeEntry(), RelationCacheInitialize(), ReorderBufferAllocate(), ReorderBufferBuildTupleCidHash(), ReorderBufferToastInitHash(), ResetUnloggedRelationsInDbspaceDir(), ri_InitHashTables(), select_perl_context(), SerializePendingSyncs(), set_rtable_names(), ShmemInitHash(), smgropen(), transformGraph(), and XLogPrefetcherAllocate().

◆ hash_destroy()

void hash_destroy ( HTAB hashp)

Definition at line 865 of file dynahash.c.

866{
867 if (hashp != NULL)
868 {
869 /* allocation method must be one we know how to free, too */
870 Assert(hashp->alloc == DynaHashAlloc);
871 /* so this hashtable must have its own context */
872 Assert(hashp->hcxt != NULL);
873
874 hash_stats("destroy", hashp);
875
876 /*
877 * Free everything by destroying the hash table's memory context.
878 */
880 }
881}
void hash_stats(const char *where, HTAB *hashp)
Definition: dynahash.c:884
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:485

References HTAB::alloc, Assert(), DynaHashAlloc(), hash_stats(), HTAB::hcxt, and MemoryContextDelete().

Referenced by _hash_finish_split(), CheckForSessionAndXactLocks(), CompactCheckpointerRequestQueue(), destroy_colinfo_names_hash(), ExecuteTruncateGuts(), find_all_inheritors(), get_json_object_as_hash(), pg_get_backend_memory_contexts(), pgoutput_shutdown(), populate_recordset_object_end(), PostPrepare_PredicateLocks(), process_syncing_tables_for_apply(), ProcessGetMemoryContextInterrupt(), ReleasePredicateLocksLocal(), ReorderBufferFreeTXN(), ReorderBufferToastReset(), ReorderBufferTruncateTXN(), ResetSequenceCaches(), ResetUnloggedRelationsInDbspaceDir(), SerializePendingSyncs(), set_rtable_names(), ShutdownRecoveryTransactionEnvironment(), XLogCheckInvalidPages(), and XLogPrefetcherFree().

◆ hash_estimate_size()

Size hash_estimate_size ( long  num_entries,
Size  entrysize 
)

Definition at line 783 of file dynahash.c.

784{
785 Size size;
786 long nBuckets,
787 nSegments,
788 nDirEntries,
789 nElementAllocs,
790 elementSize,
791 elementAllocCnt;
792
793 /* estimate number of buckets wanted */
794 nBuckets = next_pow2_long(num_entries);
795 /* # of segments needed for nBuckets */
796 nSegments = next_pow2_long((nBuckets - 1) / DEF_SEGSIZE + 1);
797 /* directory entries */
798 nDirEntries = DEF_DIRSIZE;
799 while (nDirEntries < nSegments)
800 nDirEntries <<= 1; /* dir_alloc doubles dsize at each call */
801
802 /* fixed control info */
803 size = MAXALIGN(sizeof(HASHHDR)); /* but not HTAB, per above */
804 /* directory */
805 size = add_size(size, mul_size(nDirEntries, sizeof(HASHSEGMENT)));
806 /* segments */
807 size = add_size(size, mul_size(nSegments,
808 MAXALIGN(DEF_SEGSIZE * sizeof(HASHBUCKET))));
809 /* elements --- allocated in groups of choose_nelem_alloc() entries */
810 elementAllocCnt = choose_nelem_alloc(entrysize);
811 nElementAllocs = (num_entries - 1) / elementAllocCnt + 1;
812 elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(entrysize);
813 size = add_size(size,
814 mul_size(nElementAllocs,
815 mul_size(elementAllocCnt, elementSize)));
816
817 return size;
818}
#define MAXALIGN(LEN)
Definition: c.h:782
size_t Size
Definition: c.h:576
#define DEF_DIRSIZE
Definition: dynahash.c:125
static int choose_nelem_alloc(Size entrysize)
Definition: dynahash.c:656
#define DEF_SEGSIZE
Definition: dynahash.c:123
static long next_pow2_long(long num)
Definition: dynahash.c:1812
Size add_size(Size s1, Size s2)
Definition: shmem.c:493
Size mul_size(Size s1, Size s2)
Definition: shmem.c:510

References add_size(), choose_nelem_alloc(), DEF_DIRSIZE, DEF_SEGSIZE, MAXALIGN, mul_size(), and next_pow2_long().

Referenced by BufTableShmemSize(), CalculateShmemSize(), LockManagerShmemSize(), pgss_memsize(), PredicateLockShmemSize(), and WaitEventCustomShmemSize().

◆ hash_freeze()

void hash_freeze ( HTAB hashp)

Definition at line 1534 of file dynahash.c.

1535{
1536 if (hashp->isshared)
1537 elog(ERROR, "cannot freeze shared hashtable \"%s\"", hashp->tabname);
1538 if (!hashp->frozen && has_seq_scans(hashp))
1539 elog(ERROR, "cannot freeze hashtable \"%s\" because it has active scans",
1540 hashp->tabname);
1541 hashp->frozen = true;
1542}
static bool has_seq_scans(HTAB *hashp)
Definition: dynahash.c:1898

References elog, ERROR, HTAB::frozen, has_seq_scans(), HTAB::isshared, and HTAB::tabname.

◆ hash_get_num_entries()

long hash_get_num_entries ( HTAB hashp)

Definition at line 1341 of file dynahash.c.

1342{
1343 int i;
1344 long sum = hashp->hctl->freeList[0].nentries;
1345
1346 /*
1347 * We currently don't bother with acquiring the mutexes; it's only
1348 * sensible to call this function if you've got lock on all partitions of
1349 * the table.
1350 */
1351 if (IS_PARTITIONED(hashp->hctl))
1352 {
1353 for (i = 1; i < NUM_FREELISTS; i++)
1354 sum += hashp->hctl->freeList[i].nentries;
1355 }
1356
1357 return sum;
1358}
long nentries
Definition: dynahash.c:156
FreeListData freeList[NUM_FREELISTS]
Definition: dynahash.c:180

References HASHHDR::freeList, HTAB::hctl, i, IS_PARTITIONED, FreeListData::nentries, and NUM_FREELISTS.

Referenced by build_guc_variables(), compute_array_stats(), compute_tsvector_stats(), entry_alloc(), entry_dealloc(), entry_reset(), EstimatePendingSyncsSpace(), EstimateUncommittedEnumsSpace(), get_crosstab_tuplestore(), get_explain_guc_options(), get_guc_variables(), GetLockStatusData(), GetPredicateLockStatusData(), GetRunningTransactionLocks(), GetWaitEventCustomNames(), hash_stats(), pgss_shmem_shutdown(), ResetUnloggedRelationsInDbspaceDir(), SerializePendingSyncs(), transformGraph(), and XLogHaveInvalidPages().

◆ hash_get_shared_size()

Size hash_get_shared_size ( HASHCTL info,
int  flags 
)

Definition at line 854 of file dynahash.c.

855{
856 Assert(flags & HASH_DIRSIZE);
857 Assert(info->dsize == info->max_dsize);
858 return sizeof(HASHHDR) + info->dsize * sizeof(HASHSEGMENT);
859}
struct HASHHDR HASHHDR
Definition: hsearch.h:58

References Assert(), HASHCTL::dsize, HASH_DIRSIZE, and HASHCTL::max_dsize.

Referenced by ShmemInitHash().

◆ hash_search()

void * hash_search ( HTAB hashp,
const void *  keyPtr,
HASHACTION  action,
bool *  foundPtr 
)

Definition at line 955 of file dynahash.c.

959{
960 return hash_search_with_hash_value(hashp,
961 keyPtr,
962 hashp->hash(keyPtr, hashp->keysize),
963 action,
964 foundPtr);
965}
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:968

References generate_unaccent_rules::action, HTAB::hash, hash_search_with_hash_value(), and HTAB::keysize.

Referenced by _hash_finish_split(), _hash_splitbucket(), add_guc_variable(), add_join_rel(), add_to_names_hash(), AddEnumLabel(), AddEventToPendingNotifies(), AddPendingSync(), ApplyLogicalMappingFile(), assign_record_type_typmod(), AsyncExistsPendingNotify(), AtEOSubXact_RelationCache(), AtEOXact_RelationCache(), build_guc_variables(), build_join_rel_hash(), BuildEventTriggerCache(), cfunc_hashtable_delete(), cfunc_hashtable_insert(), cfunc_hashtable_lookup(), CheckAndPromotePredicateLockRequest(), CheckForSerializableConflictOut(), CheckForSessionAndXactLocks(), colname_is_unique(), CompactCheckpointerRequestQueue(), compile_plperl_function(), compile_pltcl_function(), compute_array_stats(), compute_context_path(), compute_contexts_count_and_ids(), compute_tsvector_stats(), createNewConnection(), define_custom_variable(), delete_rel_type_cache_if_needed(), deleteConnection(), do_autovacuum(), DropAllPredicateLocksFromTable(), DropAllPreparedStatements(), DropPreparedStatement(), entry_alloc(), entry_dealloc(), entry_reset(), EnumTypeUncommitted(), EnumUncommitted(), EnumValuesCreate(), EventCacheLookup(), ExecInitModifyTable(), ExecLookupResultRelByOid(), ExecuteTruncateGuts(), ExtendBufferedRelLocal(), FetchPreparedStatement(), finalize_in_progress_typentries(), find_all_inheritors(), find_join_rel(), find_oper_cache_entry(), find_option(), find_rendezvous_variable(), forget_invalid_pages(), forget_invalid_pages_db(), ForgetPrivateRefCountEntry(), get_attribute_options(), get_cast_hashentry(), get_rel_sync_entry(), get_tablespace(), GetComboCommandId(), GetConnection(), getConnectionByName(), GetExtensibleNodeEntry(), getmissingattr(), GetPrivateRefCountEntry(), getState(), GetWaitEventCustomIdentifier(), gistGetNodeBuffer(), gistGetParent(), gistMemorizeParent(), gistRelocateBuildBuffersOnSplit(), hash_object_field_end(), init_sequence(), insert_rel_type_cache_if_needed(), InvalidateAttoptCacheCallback(), InvalidateLocalBuffer(), InvalidateOprCacheCallBack(), InvalidateShippableCacheCallback(), InvalidateTableSpaceCacheCallback(), is_shippable(), JsObjectGetField(), json_unique_check_key(), LocalBufferAlloc(), LockAcquireExtended(), LockHasWaiters(), LockHeldByMe(), LockRelease(), log_invalid_page(), logical_rewrite_log_mapping(), logicalrep_partition_open(), logicalrep_rel_open(), logicalrep_relmap_update(), lookup_C_func(), lookup_proof_cache(), lookup_ts_config_cache(), lookup_ts_dictionary_cache(), lookup_ts_parser_cache(), lookup_type_cache(), LookupOpclassInfo(), make_oper_cache_entry(), MarkGUCPrefixReserved(), pa_allocate_worker(), pa_find_worker(), pa_free_worker(), PartitionDirectoryLookup(), pg_get_backend_memory_contexts(), pg_tzset(), pgss_store(), plperl_spi_exec_prepared(), plperl_spi_freeplan(), plperl_spi_prepare(), plperl_spi_query_prepared(), pltcl_fetch_interp(), PLy_commit(), PLy_generate_spi_exceptions(), PLy_procedure_get(), PLy_rollback(), PLy_spi_subtransaction_abort(), populate_recordset_object_field_end(), predicatelock_twophase_recover(), PredicateLockExists(), PredicateLockShmemInit(), PredicateLockTwoPhaseFinish(), PrefetchLocalBuffer(), process_syncing_tables_for_apply(), ProcessSyncRequests(), prune_element_hashtable(), prune_lexemes_hashtable(), PutMemoryContextsStatsTupleStore(), rebuild_database_list(), record_C_func(), RegisterExtensibleNodeEntry(), RegisterPredicateLockingXid(), rel_sync_cache_relation_cb(), RelationPreTruncate(), ReleaseOneSerializableXact(), RelFileLocatorSkippingWAL(), RelfilenumberMapInvalidateCallback(), RelidByRelfilenumber(), RememberSyncRequest(), RemoveLocalLock(), ReorderBufferBuildTupleCidHash(), ReorderBufferCleanupTXN(), ReorderBufferToastAppendChunk(), ReorderBufferToastReplace(), ReorderBufferTXNByXid(), ReservePrivateRefCountEntry(), ResetUnloggedRelationsInDbspaceDir(), ResolveCminCmaxDuringDecoding(), RestoreUncommittedEnums(), rewrite_heap_dead_tuple(), rewrite_heap_tuple(), ri_FetchPreparedPlan(), ri_HashCompareOp(), ri_HashPreparedPlan(), ri_LoadConstraintInfo(), select_perl_context(), SerializePendingSyncs(), set_rtable_names(), ShmemInitStruct(), smgrdestroy(), smgrDoPendingSyncs(), smgropen(), smgrreleaserellocator(), StandbyAcquireAccessExclusiveLock(), StandbyReleaseAllLocks(), StandbyReleaseLocks(), StandbyReleaseOldLocks(), StandbyReleaseXidEntryLocks(), StorePreparedStatement(), table_recheck_autovac(), TypeCacheRelCallback(), WaitEventCustomNew(), XLogPrefetcherAddFilter(), XLogPrefetcherCompleteFilters(), and XLogPrefetcherIsFiltered().

◆ hash_search_with_hash_value()

void * hash_search_with_hash_value ( HTAB hashp,
const void *  keyPtr,
uint32  hashvalue,
HASHACTION  action,
bool *  foundPtr 
)

Definition at line 968 of file dynahash.c.

973{
974 HASHHDR *hctl = hashp->hctl;
975 int freelist_idx = FREELIST_IDX(hctl, hashvalue);
976 Size keysize;
977 HASHBUCKET currBucket;
978 HASHBUCKET *prevBucketPtr;
979 HashCompareFunc match;
980
981#ifdef HASH_STATISTICS
982 hash_accesses++;
983 hctl->accesses++;
984#endif
985
986 /*
987 * If inserting, check if it is time to split a bucket.
988 *
989 * NOTE: failure to expand table is not a fatal error, it just means we
990 * have to run at higher fill factor than we wanted. However, if we're
991 * using the palloc allocator then it will throw error anyway on
992 * out-of-memory, so we must do this before modifying the table.
993 */
995 {
996 /*
997 * Can't split if running in partitioned mode, nor if frozen, nor if
998 * table is the subject of any active hash_seq_search scans.
999 */
1000 if (hctl->freeList[0].nentries > (long) hctl->max_bucket &&
1001 !IS_PARTITIONED(hctl) && !hashp->frozen &&
1002 !has_seq_scans(hashp))
1003 (void) expand_table(hashp);
1004 }
1005
1006 /*
1007 * Do the initial lookup
1008 */
1009 (void) hash_initial_lookup(hashp, hashvalue, &prevBucketPtr);
1010 currBucket = *prevBucketPtr;
1011
1012 /*
1013 * Follow collision chain looking for matching key
1014 */
1015 match = hashp->match; /* save one fetch in inner loop */
1016 keysize = hashp->keysize; /* ditto */
1017
1018 while (currBucket != NULL)
1019 {
1020 if (currBucket->hashvalue == hashvalue &&
1021 match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
1022 break;
1023 prevBucketPtr = &(currBucket->link);
1024 currBucket = *prevBucketPtr;
1025#ifdef HASH_STATISTICS
1026 hash_collisions++;
1027 hctl->collisions++;
1028#endif
1029 }
1030
1031 if (foundPtr)
1032 *foundPtr = (bool) (currBucket != NULL);
1033
1034 /*
1035 * OK, now what?
1036 */
1037 switch (action)
1038 {
1039 case HASH_FIND:
1040 if (currBucket != NULL)
1041 return ELEMENTKEY(currBucket);
1042 return NULL;
1043
1044 case HASH_REMOVE:
1045 if (currBucket != NULL)
1046 {
1047 /* if partitioned, must lock to touch nentries and freeList */
1048 if (IS_PARTITIONED(hctl))
1049 SpinLockAcquire(&(hctl->freeList[freelist_idx].mutex));
1050
1051 /* delete the record from the appropriate nentries counter. */
1052 Assert(hctl->freeList[freelist_idx].nentries > 0);
1053 hctl->freeList[freelist_idx].nentries--;
1054
1055 /* remove record from hash bucket's chain. */
1056 *prevBucketPtr = currBucket->link;
1057
1058 /* add the record to the appropriate freelist. */
1059 currBucket->link = hctl->freeList[freelist_idx].freeList;
1060 hctl->freeList[freelist_idx].freeList = currBucket;
1061
1062 if (IS_PARTITIONED(hctl))
1063 SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
1064
1065 /*
1066 * better hope the caller is synchronizing access to this
1067 * element, because someone else is going to reuse it the next
1068 * time something is added to the table
1069 */
1070 return ELEMENTKEY(currBucket);
1071 }
1072 return NULL;
1073
1074 case HASH_ENTER:
1075 case HASH_ENTER_NULL:
1076 /* Return existing element if found, else create one */
1077 if (currBucket != NULL)
1078 return ELEMENTKEY(currBucket);
1079
1080 /* disallow inserts if frozen */
1081 if (hashp->frozen)
1082 elog(ERROR, "cannot insert into frozen hashtable \"%s\"",
1083 hashp->tabname);
1084
1085 currBucket = get_hash_entry(hashp, freelist_idx);
1086 if (currBucket == NULL)
1087 {
1088 /* out of memory */
1089 if (action == HASH_ENTER_NULL)
1090 return NULL;
1091 /* report a generic message */
1092 if (hashp->isshared)
1093 ereport(ERROR,
1094 (errcode(ERRCODE_OUT_OF_MEMORY),
1095 errmsg("out of shared memory")));
1096 else
1097 ereport(ERROR,
1098 (errcode(ERRCODE_OUT_OF_MEMORY),
1099 errmsg("out of memory")));
1100 }
1101
1102 /* link into hashbucket chain */
1103 *prevBucketPtr = currBucket;
1104 currBucket->link = NULL;
1105
1106 /* copy key into record */
1107 currBucket->hashvalue = hashvalue;
1108 hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
1109
1110 /*
1111 * Caller is expected to fill the data field on return. DO NOT
1112 * insert any code that could possibly throw error here, as doing
1113 * so would leave the table entry incomplete and hence corrupt the
1114 * caller's data structure.
1115 */
1116
1117 return ELEMENTKEY(currBucket);
1118 }
1119
1120 elog(ERROR, "unrecognized hash action code: %d", (int) action);
1121
1122 return NULL; /* keep compiler quiet */
1123}
static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx)
Definition: dynahash.c:1256
static bool expand_table(HTAB *hashp)
Definition: dynahash.c:1551
#define ELEMENTKEY(helem)
Definition: dynahash.c:244
#define FREELIST_IDX(hctl, hashcode)
Definition: dynahash.c:212
static uint32 hash_initial_lookup(HTAB *hashp, uint32 hashvalue, HASHBUCKET **bucketptr)
Definition: dynahash.c:1756
#define SpinLockRelease(lock)
Definition: spin.h:61
#define SpinLockAcquire(lock)
Definition: spin.h:59
slock_t mutex
Definition: dynahash.c:155
HASHELEMENT * freeList
Definition: dynahash.c:157
struct HASHELEMENT * link
Definition: hsearch.h:53
uint32 hashvalue
Definition: hsearch.h:54
uint32 max_bucket
Definition: dynahash.c:186

References generate_unaccent_rules::action, Assert(), ELEMENTKEY, elog, ereport, errcode(), errmsg(), ERROR, expand_table(), FreeListData::freeList, HASHHDR::freeList, FREELIST_IDX, HTAB::frozen, get_hash_entry(), has_seq_scans(), HASH_ENTER, HASH_ENTER_NULL, HASH_FIND, hash_initial_lookup(), HASH_REMOVE, HASHELEMENT::hashvalue, HTAB::hctl, IS_PARTITIONED, HTAB::isshared, HTAB::keycopy, HTAB::keysize, HASHELEMENT::link, HTAB::match, HASHHDR::max_bucket, FreeListData::mutex, FreeListData::nentries, SpinLockAcquire, SpinLockRelease, and HTAB::tabname.

Referenced by BufTableDelete(), BufTableInsert(), BufTableLookup(), CheckTargetForConflictsIn(), CleanUpLock(), ClearOldPredicateLocks(), CreatePredicateLock(), DecrementParentLocks(), DeleteChildTargetLocks(), DeleteLockTarget(), DropAllPredicateLocksFromTable(), FastPathGetRelationLockEntry(), GetLockConflicts(), hash_search(), lock_twophase_recover(), LockAcquireExtended(), LockRefindAndRelease(), LockRelease(), LockWaiterCount(), PageIsPredicateLocked(), PredicateLockAcquire(), ReleaseOneSerializableXact(), RemoveScratchTarget(), RemoveTargetIfNoLongerUsed(), RestoreScratchTarget(), SetupLockInTable(), and TransferPredicateLocksToNewTarget().

◆ hash_select_dirsize()

long hash_select_dirsize ( long  num_entries)

Definition at line 830 of file dynahash.c.

831{
832 long nBuckets,
833 nSegments,
834 nDirEntries;
835
836 /* estimate number of buckets wanted */
837 nBuckets = next_pow2_long(num_entries);
838 /* # of segments needed for nBuckets */
839 nSegments = next_pow2_long((nBuckets - 1) / DEF_SEGSIZE + 1);
840 /* directory entries */
841 nDirEntries = DEF_DIRSIZE;
842 while (nDirEntries < nSegments)
843 nDirEntries <<= 1; /* dir_alloc doubles dsize at each call */
844
845 return nDirEntries;
846}

References DEF_DIRSIZE, DEF_SEGSIZE, and next_pow2_long().

Referenced by ShmemInitHash().

◆ hash_seq_init()

void hash_seq_init ( HASH_SEQ_STATUS status,
HTAB hashp 
)

Definition at line 1385 of file dynahash.c.

1386{
1387 status->hashp = hashp;
1388 status->curBucket = 0;
1389 status->curEntry = NULL;
1390 status->hasHashvalue = false;
1391 if (!hashp->frozen)
1392 register_seq_scan(hashp);
1393}
static void register_seq_scan(HTAB *hashp)
Definition: dynahash.c:1865
HASHELEMENT * curEntry
Definition: hsearch.h:124
uint32 curBucket
Definition: hsearch.h:123
HTAB * hashp
Definition: hsearch.h:122
bool hasHashvalue
Definition: hsearch.h:125

References HASH_SEQ_STATUS::curBucket, HASH_SEQ_STATUS::curEntry, HTAB::frozen, HASH_SEQ_STATUS::hasHashvalue, HASH_SEQ_STATUS::hashp, and register_seq_scan().

Referenced by AtAbort_Portals(), AtCleanup_Portals(), AtEOSubXact_RelationCache(), AtEOXact_RelationCache(), AtPrepare_Locks(), AtSubAbort_Portals(), AtSubCleanup_Portals(), AtSubCommit_Portals(), BeginReportingGUCOptions(), CheckForBufferLeaks(), CheckForSessionAndXactLocks(), CheckTableForSerializableConflictIn(), cleanup_rel_sync_cache(), compute_array_stats(), compute_tsvector_stats(), dblink_get_connections(), DestroyPartitionDirectory(), disconnect_cached_connections(), DropAllPredicateLocksFromTable(), DropAllPreparedStatements(), end_heap_rewrite(), entry_dealloc(), entry_reset(), ExecuteTruncateGuts(), forget_invalid_pages(), forget_invalid_pages_db(), ForgetPortalSnapshots(), gc_qtexts(), get_guc_variables(), GetLockStatusData(), GetPredicateLockStatusData(), GetRunningTransactionLocks(), GetWaitEventCustomNames(), hash_seq_init_with_hash_value(), HoldPinnedPortals(), InitializeGUCOptions(), InvalidateAttoptCacheCallback(), InvalidateOprCacheCallBack(), InvalidateOprProofCacheCallBack(), InvalidateShippableCacheCallback(), InvalidateTableSpaceCacheCallback(), InvalidateTSCacheCallBack(), LockReassignCurrentOwner(), LockReleaseAll(), LockReleaseCurrentOwner(), LockReleaseSession(), logical_end_heap_rewrite(), logical_heap_rewrite_flush_mappings(), logicalrep_partmap_invalidate_cb(), logicalrep_partmap_reset_relmap(), logicalrep_relmap_invalidate_cb(), MarkGUCPrefixReserved(), packGraph(), pg_cursor(), pg_get_shmem_allocations(), pg_get_shmem_allocations_numa(), pg_prepared_statement(), pg_stat_statements_internal(), pgfdw_inval_callback(), pgfdw_subxact_callback(), pgfdw_xact_callback(), pgss_shmem_shutdown(), plperl_fini(), PortalErrorCleanup(), PortalHashTableDeleteAll(), postgres_fdw_get_connections_internal(), PostPrepare_Locks(), PreCommit_Portals(), ProcessConfigFileInternal(), ProcessSyncRequests(), prune_element_hashtable(), prune_lexemes_hashtable(), rebuild_database_list(), rel_sync_cache_publication_cb(), rel_sync_cache_relation_cb(), RelationCacheInitializePhase3(), RelationCacheInvalidate(), RelfilenumberMapInvalidateCallback(), RememberSyncRequest(), ReorderBufferToastReset(), selectColorTrigrams(), SerializePendingSyncs(), SerializeUncommittedEnums(), smgrDoPendingSyncs(), smgrreleaseall(), StandbyReleaseAllLocks(), StandbyReleaseOldLocks(), ThereAreNoReadyPortals(), TypeCacheOpcCallback(), TypeCacheRelCallback(), TypeCacheTypCallback(), write_relcache_init_file(), and XLogCheckInvalidPages().

◆ hash_seq_init_with_hash_value()

void hash_seq_init_with_hash_value ( HASH_SEQ_STATUS status,
HTAB hashp,
uint32  hashvalue 
)

Definition at line 1405 of file dynahash.c.

1407{
1408 HASHBUCKET *bucketPtr;
1409
1410 hash_seq_init(status, hashp);
1411
1412 status->hasHashvalue = true;
1413 status->hashvalue = hashvalue;
1414
1415 status->curBucket = hash_initial_lookup(hashp, hashvalue, &bucketPtr);
1416 status->curEntry = *bucketPtr;
1417}
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
Definition: dynahash.c:1385
uint32 hashvalue
Definition: hsearch.h:126

References HASH_SEQ_STATUS::curBucket, HASH_SEQ_STATUS::curEntry, hash_initial_lookup(), hash_seq_init(), HASH_SEQ_STATUS::hasHashvalue, and HASH_SEQ_STATUS::hashvalue.

Referenced by InvalidateAttoptCacheCallback(), and TypeCacheTypCallback().

◆ hash_seq_search()

void * hash_seq_search ( HASH_SEQ_STATUS status)

Definition at line 1420 of file dynahash.c.

1421{
1422 HTAB *hashp;
1423 HASHHDR *hctl;
1424 uint32 max_bucket;
1425 long ssize;
1426 long segment_num;
1427 long segment_ndx;
1428 HASHSEGMENT segp;
1429 uint32 curBucket;
1430 HASHELEMENT *curElem;
1431
1432 if (status->hasHashvalue)
1433 {
1434 /*
1435 * Scan entries only in the current bucket because only this bucket
1436 * can contain entries with the given hash value.
1437 */
1438 while ((curElem = status->curEntry) != NULL)
1439 {
1440 status->curEntry = curElem->link;
1441 if (status->hashvalue != curElem->hashvalue)
1442 continue;
1443 return (void *) ELEMENTKEY(curElem);
1444 }
1445
1446 hash_seq_term(status);
1447 return NULL;
1448 }
1449
1450 if ((curElem = status->curEntry) != NULL)
1451 {
1452 /* Continuing scan of curBucket... */
1453 status->curEntry = curElem->link;
1454 if (status->curEntry == NULL) /* end of this bucket */
1455 ++status->curBucket;
1456 return ELEMENTKEY(curElem);
1457 }
1458
1459 /*
1460 * Search for next nonempty bucket starting at curBucket.
1461 */
1462 curBucket = status->curBucket;
1463 hashp = status->hashp;
1464 hctl = hashp->hctl;
1465 ssize = hashp->ssize;
1466 max_bucket = hctl->max_bucket;
1467
1468 if (curBucket > max_bucket)
1469 {
1470 hash_seq_term(status);
1471 return NULL; /* search is done */
1472 }
1473
1474 /*
1475 * first find the right segment in the table directory.
1476 */
1477 segment_num = curBucket >> hashp->sshift;
1478 segment_ndx = MOD(curBucket, ssize);
1479
1480 segp = hashp->dir[segment_num];
1481
1482 /*
1483 * Pick up the first item in this bucket's chain. If chain is not empty
1484 * we can begin searching it. Otherwise we have to advance to find the
1485 * next nonempty bucket. We try to optimize that case since searching a
1486 * near-empty hashtable has to iterate this loop a lot.
1487 */
1488 while ((curElem = segp[segment_ndx]) == NULL)
1489 {
1490 /* empty bucket, advance to next */
1491 if (++curBucket > max_bucket)
1492 {
1493 status->curBucket = curBucket;
1494 hash_seq_term(status);
1495 return NULL; /* search is done */
1496 }
1497 if (++segment_ndx >= ssize)
1498 {
1499 segment_num++;
1500 segment_ndx = 0;
1501 segp = hashp->dir[segment_num];
1502 }
1503 }
1504
1505 /* Begin scan of curBucket... */
1506 status->curEntry = curElem->link;
1507 if (status->curEntry == NULL) /* end of this bucket */
1508 ++curBucket;
1509 status->curBucket = curBucket;
1510 return ELEMENTKEY(curElem);
1511}
#define MOD(x, y)
Definition: dynahash.c:255
void hash_seq_term(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1514

References HASH_SEQ_STATUS::curBucket, HASH_SEQ_STATUS::curEntry, HTAB::dir, ELEMENTKEY, hash_seq_term(), HASH_SEQ_STATUS::hasHashvalue, HASH_SEQ_STATUS::hashp, HASHELEMENT::hashvalue, HASH_SEQ_STATUS::hashvalue, HTAB::hctl, HASHELEMENT::link, HASHHDR::max_bucket, MOD, HTAB::sshift, and HTAB::ssize.

Referenced by AtAbort_Portals(), AtCleanup_Portals(), AtEOSubXact_RelationCache(), AtEOXact_RelationCache(), AtPrepare_Locks(), AtSubAbort_Portals(), AtSubCleanup_Portals(), AtSubCommit_Portals(), BeginReportingGUCOptions(), CheckForBufferLeaks(), CheckForSessionAndXactLocks(), CheckTableForSerializableConflictIn(), cleanup_rel_sync_cache(), compute_array_stats(), compute_tsvector_stats(), dblink_get_connections(), DestroyPartitionDirectory(), disconnect_cached_connections(), DropAllPredicateLocksFromTable(), DropAllPreparedStatements(), end_heap_rewrite(), entry_dealloc(), entry_reset(), ExecuteTruncateGuts(), forget_invalid_pages(), forget_invalid_pages_db(), ForgetPortalSnapshots(), gc_qtexts(), get_guc_variables(), GetLockStatusData(), GetPredicateLockStatusData(), GetRunningTransactionLocks(), GetWaitEventCustomNames(), HoldPinnedPortals(), InitializeGUCOptions(), InvalidateAttoptCacheCallback(), InvalidateOprCacheCallBack(), InvalidateOprProofCacheCallBack(), InvalidateShippableCacheCallback(), InvalidateTableSpaceCacheCallback(), InvalidateTSCacheCallBack(), LockReassignCurrentOwner(), LockReleaseAll(), LockReleaseCurrentOwner(), LockReleaseSession(), logical_end_heap_rewrite(), logical_heap_rewrite_flush_mappings(), logicalrep_partmap_invalidate_cb(), logicalrep_partmap_reset_relmap(), logicalrep_relmap_invalidate_cb(), MarkGUCPrefixReserved(), packGraph(), pg_cursor(), pg_get_shmem_allocations(), pg_get_shmem_allocations_numa(), pg_prepared_statement(), pg_stat_statements_internal(), pgfdw_inval_callback(), pgfdw_subxact_callback(), pgfdw_xact_callback(), pgss_shmem_shutdown(), plperl_fini(), PortalErrorCleanup(), PortalHashTableDeleteAll(), postgres_fdw_get_connections_internal(), PostPrepare_Locks(), PreCommit_Portals(), ProcessConfigFileInternal(), ProcessSyncRequests(), prune_element_hashtable(), prune_lexemes_hashtable(), rebuild_database_list(), rel_sync_cache_publication_cb(), rel_sync_cache_relation_cb(), RelationCacheInitializePhase3(), RelationCacheInvalidate(), RelfilenumberMapInvalidateCallback(), RememberSyncRequest(), ReorderBufferToastReset(), selectColorTrigrams(), SerializePendingSyncs(), SerializeUncommittedEnums(), smgrDoPendingSyncs(), smgrreleaseall(), StandbyReleaseAllLocks(), StandbyReleaseOldLocks(), ThereAreNoReadyPortals(), TypeCacheOpcCallback(), TypeCacheRelCallback(), TypeCacheTypCallback(), write_relcache_init_file(), and XLogCheckInvalidPages().

◆ hash_seq_term()

◆ hash_stats()

void hash_stats ( const char *  where,
HTAB hashp 
)

Definition at line 884 of file dynahash.c.

885{
886#ifdef HASH_STATISTICS
887 fprintf(stderr, "%s: this HTAB -- accesses %ld collisions %ld\n",
888 where, hashp->hctl->accesses, hashp->hctl->collisions);
889
890 fprintf(stderr, "hash_stats: entries %ld keysize %ld maxp %u segmentcount %ld\n",
891 hash_get_num_entries(hashp), (long) hashp->hctl->keysize,
892 hashp->hctl->max_bucket, hashp->hctl->nsegs);
893 fprintf(stderr, "%s: total accesses %ld total collisions %ld\n",
894 where, hash_accesses, hash_collisions);
895 fprintf(stderr, "hash_stats: total expansions %ld\n",
896 hash_expansions);
897#endif
898}
#define fprintf(file, fmt, msg)
Definition: cubescan.l:21
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1341
long nsegs
Definition: dynahash.c:185

References fprintf, hash_get_num_entries(), HTAB::hctl, HASHHDR::keysize, HASHHDR::max_bucket, and HASHHDR::nsegs.

Referenced by hash_destroy().

◆ hash_update_hash_key()

bool hash_update_hash_key ( HTAB hashp,
void *  existingEntry,
const void *  newKeyPtr 
)

Definition at line 1145 of file dynahash.c.

1148{
1149 HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry);
1150 uint32 newhashvalue;
1151 Size keysize;
1152 uint32 bucket;
1153 uint32 newbucket;
1154 HASHBUCKET currBucket;
1155 HASHBUCKET *prevBucketPtr;
1156 HASHBUCKET *oldPrevPtr;
1157 HashCompareFunc match;
1158
1159#ifdef HASH_STATISTICS
1160 hash_accesses++;
1161 hctl->accesses++;
1162#endif
1163
1164 /* disallow updates if frozen */
1165 if (hashp->frozen)
1166 elog(ERROR, "cannot update in frozen hashtable \"%s\"",
1167 hashp->tabname);
1168
1169 /*
1170 * Lookup the existing element using its saved hash value. We need to do
1171 * this to be able to unlink it from its hash chain, but as a side benefit
1172 * we can verify the validity of the passed existingEntry pointer.
1173 */
1174 bucket = hash_initial_lookup(hashp, existingElement->hashvalue,
1175 &prevBucketPtr);
1176 currBucket = *prevBucketPtr;
1177
1178 while (currBucket != NULL)
1179 {
1180 if (currBucket == existingElement)
1181 break;
1182 prevBucketPtr = &(currBucket->link);
1183 currBucket = *prevBucketPtr;
1184 }
1185
1186 if (currBucket == NULL)
1187 elog(ERROR, "hash_update_hash_key argument is not in hashtable \"%s\"",
1188 hashp->tabname);
1189
1190 oldPrevPtr = prevBucketPtr;
1191
1192 /*
1193 * Now perform the equivalent of a HASH_ENTER operation to locate the hash
1194 * chain we want to put the entry into.
1195 */
1196 newhashvalue = hashp->hash(newKeyPtr, hashp->keysize);
1197 newbucket = hash_initial_lookup(hashp, newhashvalue, &prevBucketPtr);
1198 currBucket = *prevBucketPtr;
1199
1200 /*
1201 * Follow collision chain looking for matching key
1202 */
1203 match = hashp->match; /* save one fetch in inner loop */
1204 keysize = hashp->keysize; /* ditto */
1205
1206 while (currBucket != NULL)
1207 {
1208 if (currBucket->hashvalue == newhashvalue &&
1209 match(ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0)
1210 break;
1211 prevBucketPtr = &(currBucket->link);
1212 currBucket = *prevBucketPtr;
1213#ifdef HASH_STATISTICS
1214 hash_collisions++;
1215 hctl->collisions++;
1216#endif
1217 }
1218
1219 if (currBucket != NULL)
1220 return false; /* collision with an existing entry */
1221
1222 currBucket = existingElement;
1223
1224 /*
1225 * If old and new hash values belong to the same bucket, we need not
1226 * change any chain links, and indeed should not since this simplistic
1227 * update will corrupt the list if currBucket is the last element. (We
1228 * cannot fall out earlier, however, since we need to scan the bucket to
1229 * check for duplicate keys.)
1230 */
1231 if (bucket != newbucket)
1232 {
1233 /* OK to remove record from old hash bucket's chain. */
1234 *oldPrevPtr = currBucket->link;
1235
1236 /* link into new hashbucket chain */
1237 *prevBucketPtr = currBucket;
1238 currBucket->link = NULL;
1239 }
1240
1241 /* copy new key into record */
1242 currBucket->hashvalue = newhashvalue;
1243 hashp->keycopy(ELEMENTKEY(currBucket), newKeyPtr, keysize);
1244
1245 /* rest of record is untouched */
1246
1247 return true;
1248}
#define ELEMENT_FROM_KEY(key)
Definition: dynahash.c:249

References ELEMENT_FROM_KEY, ELEMENTKEY, elog, ERROR, HTAB::frozen, HTAB::hash, hash_initial_lookup(), HASHELEMENT::hashvalue, HTAB::keycopy, HTAB::keysize, HASHELEMENT::link, HTAB::match, and HTAB::tabname.

Referenced by PostPrepare_Locks().