123 #define DEF_SEGSIZE 256 124 #define DEF_SEGSIZE_SHIFT 8 125 #define DEF_DIRSIZE 256 128 #define NUM_FREELISTS 32 199 #ifdef HASH_STATISTICS 210 #define IS_PARTITIONED(hctl) ((hctl)->num_partitions != 0) 212 #define FREELIST_IDX(hctl, hashcode) \ 213 (IS_PARTITIONED(hctl) ? (hashcode) % NUM_FREELISTS : 0) 244 #define ELEMENTKEY(helem) (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT))) 249 #define ELEMENT_FROM_KEY(key) \ 250 ((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT)))) 255 #define MOD(x,y) ((x) & ((y)-1)) 257 #ifdef HASH_STATISTICS 258 static long hash_accesses,
306 return strncmp(key1, key2, keysize - 1);
381 CurrentDynaHashCxt = info->
hcxt;
393 hashp->
tabname = (
char *) (hashp + 1);
394 strcpy(hashp->
tabname, tabname);
397 if (!(flags & HASH_SHARED_MEM))
447 hashp->
match = memcmp;
474 if (flags & HASH_SHARED_MEM)
512 (
errcode(ERRCODE_OUT_OF_MEMORY),
513 errmsg(
"out of memory")));
525 Assert(flags & HASH_SHARED_MEM);
575 if ((flags & HASH_SHARED_MEM) ||
590 freelist_partitions = 1;
592 nelem_alloc = nelem / freelist_partitions;
593 if (nelem_alloc <= 0)
600 if (nelem_alloc * freelist_partitions < nelem)
602 nelem - nelem_alloc * (freelist_partitions - 1);
606 for (i = 0; i < freelist_partitions; i++)
608 int temp = (i == 0) ? nelem_alloc_first : nelem_alloc;
612 (
errcode(ERRCODE_OUT_OF_MEMORY),
613 errmsg(
"out of memory")));
643 #ifdef HASH_STATISTICS 644 hctl->accesses = hctl->collisions = 0;
675 nelem_alloc = allocSize / elementSize;
676 }
while (nelem_alloc < 32);
722 nsegs = (nbuckets - 1) / hctl->
ssize + 1;
729 if (nsegs > hctl->
dsize)
740 CurrentDynaHashCxt = hashp->
hcxt;
748 for (segp = hashp->
dir; hctl->
nsegs < nsegs; hctl->
nsegs++, segp++)
759 fprintf(stderr,
"init_htab:\n%s%p\n%s%ld\n%s%ld\n%s%d\n%s%ld\n%s%u\n%s%x\n%s%x\n%s%ld\n",
760 "TABLE POINTER ", hashp,
761 "DIRECTORY SIZE ", hctl->
dsize,
762 "SEGMENT SIZE ", hctl->
ssize,
763 "SEGMENT SHIFT ", hctl->
sshift,
767 "NSEGS ", hctl->
nsegs);
796 while (nDirEntries < nSegments)
808 nElementAllocs = (num_entries - 1) / elementAllocCnt + 1;
812 mul_size(elementAllocCnt, elementSize)));
839 while (nDirEntries < nSegments)
883 #ifdef HASH_STATISTICS 884 fprintf(stderr,
"%s: this HTAB -- accesses %ld collisions %ld\n",
885 where, hashp->
hctl->accesses, hashp->
hctl->collisions);
887 fprintf(stderr,
"hash_stats: entries %ld keysize %ld maxp %u segmentcount %ld\n",
890 fprintf(stderr,
"%s: total accesses %ld total collisions %ld\n",
891 where, hash_accesses, hash_collisions);
892 fprintf(stderr,
"hash_stats: total expansions %ld\n",
984 #ifdef HASH_STATISTICS 1014 segment_num = bucket >> hashp->
sshift;
1015 segment_ndx =
MOD(bucket, hashp->
ssize);
1017 segp = hashp->
dir[segment_num];
1022 prevBucketPtr = &segp[segment_ndx];
1023 currBucket = *prevBucketPtr;
1028 match = hashp->
match;
1031 while (currBucket != NULL)
1033 if (currBucket->
hashvalue == hashvalue &&
1034 match(
ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
1036 prevBucketPtr = &(currBucket->
link);
1037 currBucket = *prevBucketPtr;
1038 #ifdef HASH_STATISTICS 1045 *foundPtr = (
bool) (currBucket != NULL);
1053 if (currBucket != NULL)
1058 if (currBucket != NULL)
1069 *prevBucketPtr = currBucket->
link;
1094 if (currBucket != NULL)
1099 elog(
ERROR,
"cannot insert into frozen hashtable \"%s\"",
1103 if (currBucket == NULL)
1111 (
errcode(ERRCODE_OUT_OF_MEMORY),
1112 errmsg(
"out of shared memory")));
1115 (
errcode(ERRCODE_OUT_OF_MEMORY),
1116 errmsg(
"out of memory")));
1120 *prevBucketPtr = currBucket;
1121 currBucket->
link = NULL;
1137 elog(
ERROR,
"unrecognized hash action code: %d", (
int) action);
1163 void *existingEntry,
1164 const void *newKeyPtr)
1180 #ifdef HASH_STATISTICS 1187 elog(
ERROR,
"cannot update in frozen hashtable \"%s\"",
1197 segment_num = bucket >> hashp->
sshift;
1198 segment_ndx =
MOD(bucket, hashp->
ssize);
1200 segp = hashp->
dir[segment_num];
1205 prevBucketPtr = &segp[segment_ndx];
1206 currBucket = *prevBucketPtr;
1208 while (currBucket != NULL)
1210 if (currBucket == existingElement)
1212 prevBucketPtr = &(currBucket->
link);
1213 currBucket = *prevBucketPtr;
1216 if (currBucket == NULL)
1217 elog(
ERROR,
"hash_update_hash_key argument is not in hashtable \"%s\"",
1220 oldPrevPtr = prevBucketPtr;
1226 newhashvalue = hashp->
hash(newKeyPtr, hashp->
keysize);
1230 segment_num = newbucket >> hashp->
sshift;
1231 segment_ndx =
MOD(newbucket, hashp->
ssize);
1233 segp = hashp->
dir[segment_num];
1238 prevBucketPtr = &segp[segment_ndx];
1239 currBucket = *prevBucketPtr;
1244 match = hashp->
match;
1247 while (currBucket != NULL)
1249 if (currBucket->
hashvalue == newhashvalue &&
1250 match(
ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0)
1252 prevBucketPtr = &(currBucket->
link);
1253 currBucket = *prevBucketPtr;
1254 #ifdef HASH_STATISTICS 1260 if (currBucket != NULL)
1263 currBucket = existingElement;
1272 if (bucket != newbucket)
1275 *oldPrevPtr = currBucket->
link;
1278 *prevBucketPtr = currBucket;
1279 currBucket->
link = NULL;
1311 if (newElement != NULL)
1331 int borrow_from_idx;
1337 borrow_from_idx = freelist_idx;
1341 if (borrow_from_idx == freelist_idx)
1347 if (newElement != NULL)
1428 status->
hashp = hashp;
1448 if ((curElem = status->
curEntry) != NULL)
1461 hashp = status->
hashp;
1463 ssize = hashp->
ssize;
1466 if (curBucket > max_bucket)
1475 segment_num = curBucket >> hashp->
sshift;
1476 segment_ndx =
MOD(curBucket, ssize);
1478 segp = hashp->
dir[segment_num];
1486 while ((curElem = segp[segment_ndx]) == NULL)
1489 if (++curBucket > max_bucket)
1495 if (++segment_ndx >= ssize)
1499 segp = hashp->
dir[segment_num];
1537 elog(
ERROR,
"cannot freeze hashtable \"%s\" because it has active scans",
1567 #ifdef HASH_STATISTICS 1572 new_segnum = new_bucket >> hashp->
sshift;
1573 new_segndx =
MOD(new_bucket, hashp->
ssize);
1575 if (new_segnum >= hctl->
nsegs)
1578 if (new_segnum >= hctl->
dsize)
1595 old_bucket = (new_bucket & hctl->
low_mask);
1612 old_segnum = old_bucket >> hashp->
sshift;
1613 old_segndx =
MOD(old_bucket, hashp->
ssize);
1615 old_seg = hashp->
dir[old_segnum];
1616 new_seg = hashp->
dir[new_segnum];
1618 oldlink = &old_seg[old_segndx];
1619 newlink = &new_seg[new_segndx];
1621 for (currElement = *oldlink;
1622 currElement != NULL;
1623 currElement = nextElement)
1625 nextElement = currElement->
link;
1628 *oldlink = currElement;
1629 oldlink = &currElement->
link;
1633 *newlink = currElement;
1634 newlink = &currElement->
link;
1663 CurrentDynaHashCxt = hashp->
hcxt;
1668 memcpy(p, old_p, old_dirsize);
1669 MemSet(((
char *) p) + old_dirsize, 0, new_dirsize - old_dirsize);
1689 CurrentDynaHashCxt = hashp->
hcxt;
1719 CurrentDynaHashCxt = hashp->
hcxt;
1727 tmpElement = firstElement;
1728 for (i = 0; i < nelem; i++)
1730 tmpElement->
link = prevElement;
1731 prevElement = tmpElement;
1732 tmpElement = (
HASHELEMENT *) (((
char *) tmpElement) + elementSize);
1771 if (num > LONG_MAX / 2)
1793 if (num > INT_MAX / 2)
1827 #define MAX_SEQ_SCANS 100 1839 elog(
ERROR,
"too many active hash_seq_search scans, cannot start one on \"%s\"",
1855 if (seq_scan_tables[i] == hashp)
1863 elog(
ERROR,
"no hash_seq_search scan for hash table \"%s\"",
1875 if (seq_scan_tables[i] == hashp)
1900 elog(
WARNING,
"leaked hash_seq_search scan for hash table %p",
1901 seq_scan_tables[i]);
1923 elog(
WARNING,
"leaked hash_seq_search scan for hash table %p",
1924 seq_scan_tables[i]);
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
static int seq_scan_level[MAX_SEQ_SCANS]
int(* HashCompareFunc)(const void *key1, const void *key2, Size keysize)
uint32(* HashValueFunc)(const void *key, Size keysize)
void hash_destroy(HTAB *hashp)
void MemoryContextDelete(MemoryContext context)
#define AllocSetContextCreate
static long next_pow2_long(long num)
static uint32 calc_bucket(HASHHDR *hctl, uint32 hash_val)
#define IS_PARTITIONED(hctl)
uint32 string_hash(const void *key, Size keysize)
#define SpinLockInit(lock)
#define ELEMENTKEY(helem)
void AtEOSubXact_HashTables(bool isCommit, int nestDepth)
void hash_stats(const char *where, HTAB *hashp)
#define ELEMENT_FROM_KEY(key)
int errcode(int sqlerrcode)
#define MemSet(start, val, len)
long hash_get_num_entries(HTAB *hashp)
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
static int string_compare(const char *key1, const char *key2, Size keysize)
static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx)
uint32 uint32_hash(const void *key, Size keysize)
static uint64 pg_ceil_log2_64(uint64 num)
#define SpinLockAcquire(lock)
uint32 get_hash_value(HTAB *hashp, const void *keyPtr)
void pfree(void *pointer)
static uint32 pg_ceil_log2_32(uint32 num)
#define ALLOCSET_DEFAULT_SIZES
#define DEF_SEGSIZE_SHIFT
static void hdefault(HTAB *hashp)
static void hash_corrupted(HTAB *hashp)
static bool has_seq_scans(HTAB *hashp)
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
static bool init_htab(HTAB *hashp, long nelem)
MemoryContext TopMemoryContext
Size hash_estimate_size(long num_entries, Size entrysize)
static int next_pow2_int(long num)
#define SpinLockRelease(lock)
Size mul_size(Size s1, Size s2)
static HTAB * seq_scan_tables[MAX_SEQ_SCANS]
uint32 tag_hash(const void *key, Size keysize)
Size add_size(Size s1, Size s2)
FreeListData freeList[NUM_FREELISTS]
static void deregister_seq_scan(HTAB *hashp)
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
#define ereport(elevel,...)
long hash_select_dirsize(long num_entries)
int GetCurrentTransactionNestLevel(void)
size_t strlcpy(char *dst, const char *src, size_t siz)
#define MemoryContextIsValid(context)
static void register_seq_scan(HTAB *hashp)
#define Assert(condition)
void *(* HashAllocFunc)(Size request)
void hash_freeze(HTAB *hashp)
static HASHSEGMENT seg_alloc(HTAB *hashp)
void MemoryContextSetIdentifier(MemoryContext context, const char *id)
Size hash_get_shared_size(HASHCTL *info, int flags)
static bool expand_table(HTAB *hashp)
bool hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr)
void * hash_seq_search(HASH_SEQ_STATUS *status)
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
static void * DynaHashAlloc(Size size)
int errmsg(const char *fmt,...)
void * MemoryContextAlloc(MemoryContext context, Size size)
struct HASHELEMENT * link
static int choose_nelem_alloc(Size entrysize)
static MemoryContext CurrentDynaHashCxt
void(* pg_funcptr_t)(void)
static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx)
#define FREELIST_IDX(hctl, hashcode)
void AtEOXact_HashTables(bool isCommit)
static void static void status(const char *fmt,...) pg_attribute_printf(1
static bool dir_realloc(HTAB *hashp)
void hash_seq_term(HASH_SEQ_STATUS *status)