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 44 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 44 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,
114  HASH_ENTER,
115  HASH_REMOVE,
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",
1953  seq_scan_tables[i]);
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:225
int i
Definition: isn.c:72

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",
1930  seq_scan_tables[i]);
1931  }
1932  }
1933  num_seq_scans = 0;
1934 }

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

Referenced by AbortTransaction(), 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)
514  ereport(ERROR,
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))
614  ereport(ERROR,
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 }
unsigned int uint32
Definition: c.h:518
#define Assert(condition)
Definition: c.h:863
#define MemSet(start, val, len)
Definition: c.h:1025
void(* pg_funcptr_t)(void)
Definition: c.h:403
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:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#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
#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:149
void MemoryContextSetIdentifier(MemoryContext context, const char *id)
Definition: mcxt.c:612
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
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(), 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(), plpgsql_HashTableInit(), PLy_add_exceptions(), populate_recordset_object_start(), process_syncing_tables_for_apply(), 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  */
879  MemoryContextDelete(hashp->hcxt);
880  }
881 }
void hash_stats(const char *where, HTAB *hashp)
Definition: dynahash.c:884
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:454

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(), ReleasePredicateLocksLocal(), ReorderBufferReturnTXN(), 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:816
size_t Size
Definition: c.h:610
#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
static pg_noinline void Size size
Definition: slab.c:607

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

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(), CheckAndPromotePredicateLockRequest(), CheckForSerializableConflictOut(), CheckForSessionAndXactLocks(), colname_is_unique(), CompactCheckpointerRequestQueue(), compile_plperl_function(), compile_pltcl_function(), compute_array_stats(), compute_tsvector_stats(), createNewConnection(), define_custom_variable(), delete_rel_type_cache_if_needed(), deleteConnection(), do_autovacuum(), DropAllPredicateLocksFromTable(), DropAllPreparedStatements(), DropPreparedStatement(), DropRelationAllLocalBuffers(), DropRelationLocalBuffers(), 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(), GetLocalVictimBuffer(), getmissingattr(), GetPrivateRefCountEntry(), getState(), GetWaitEventCustomIdentifier(), gistGetNodeBuffer(), gistGetParent(), gistMemorizeParent(), gistRelocateBuildBuffersOnSplit(), hash_object_field_end(), init_sequence(), insert_rel_type_cache_if_needed(), InvalidateAttoptCacheCallback(), 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(), plpgsql_HashTableDelete(), plpgsql_HashTableInsert(), plpgsql_HashTableLookup(), 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 (void *) 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 (void *) 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 (void *) 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 (void *) ELEMENTKEY(currBucket);
1118  }
1119 
1120  elog(ERROR, "unrecognized hash action code: %d", (int) action);
1121 
1122  return NULL; /* keep compiler quiet */
1123 }
unsigned char bool
Definition: c.h:471
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_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 (void *) 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 (void *) 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_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()

void hash_seq_term ( HASH_SEQ_STATUS status)

◆ 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 }
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1341
#define fprintf
Definition: port.h:242
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().