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);
393 hashp->
tabname = (
char *) (hashp + 1);
394 strcpy(hashp->
tabname, tabname);
447 hashp->
match = memcmp;
512 (
errcode(ERRCODE_OUT_OF_MEMORY),
513 errmsg(
"out of memory")));
576 nelem < hctl->nelem_alloc)
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);
604 nelem_alloc_first = nelem_alloc;
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);
713 while (nbuckets < hctl->num_partitions)
722 nsegs = (nbuckets - 1) / hctl->
ssize + 1;
729 if (nsegs > hctl->
dsize)
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;
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)
1448 if ((curElem =
status->curEntry) != NULL)
1452 if (
status->curEntry == NULL)
1460 curBucket =
status->curBucket;
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)
1491 status->curBucket = curBucket;
1495 if (++segment_ndx >= ssize)
1499 segp = hashp->
dir[segment_num];
1505 if (
status->curEntry == NULL)
1507 status->curBucket = curBucket;
1514 if (!
status->hashp->frozen)
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;
1668 memcpy(p, old_p, old_dirsize);
1669 MemSet(((
char *) p) + old_dirsize, 0, new_dirsize - old_dirsize);
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\"",
1863 elog(
ERROR,
"no hash_seq_search scan for hash table \"%s\"",
1900 elog(
WARNING,
"leaked hash_seq_search scan for hash table %p",
1923 elog(
WARNING,
"leaked hash_seq_search scan for hash table %p",
#define MemSet(start, val, len)
void(* pg_funcptr_t)(void)
elog(ERROR, "%s: %s", p2, msg)
static HTAB * seq_scan_tables[MAX_SEQ_SCANS]
static int seq_scan_level[MAX_SEQ_SCANS]
#define ELEMENT_FROM_KEY(key)
static void * DynaHashAlloc(Size size)
static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx)
void AtEOXact_HashTables(bool isCommit)
static bool init_htab(HTAB *hashp, long nelem)
static HASHSEGMENT seg_alloc(HTAB *hashp)
static MemoryContext CurrentDynaHashCxt
static int choose_nelem_alloc(Size entrysize)
static int next_pow2_int(long num)
Size hash_get_shared_size(HASHCTL *info, int flags)
static void register_seq_scan(HTAB *hashp)
#define IS_PARTITIONED(hctl)
#define DEF_SEGSIZE_SHIFT
void AtEOSubXact_HashTables(bool isCommit, int nestDepth)
static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx)
void hash_destroy(HTAB *hashp)
static int string_compare(const char *key1, const char *key2, Size keysize)
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
static bool expand_table(HTAB *hashp)
static void hdefault(HTAB *hashp)
static void deregister_seq_scan(HTAB *hashp)
#define ELEMENTKEY(helem)
void hash_seq_term(HASH_SEQ_STATUS *status)
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
#define FREELIST_IDX(hctl, hashcode)
long hash_get_num_entries(HTAB *hashp)
long hash_select_dirsize(long num_entries)
static void hash_corrupted(HTAB *hashp)
Size hash_estimate_size(long num_entries, Size entrysize)
void hash_stats(const char *where, HTAB *hashp)
void hash_freeze(HTAB *hashp)
static bool dir_realloc(HTAB *hashp)
bool hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr)
uint32 get_hash_value(HTAB *hashp, const void *keyPtr)
static uint32 calc_bucket(HASHHDR *hctl, uint32 hash_val)
static bool has_seq_scans(HTAB *hashp)
static long next_pow2_long(long num)
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
void * hash_seq_search(HASH_SEQ_STATUS *status)
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
uint32 tag_hash(const void *key, Size keysize)
uint32 uint32_hash(const void *key, Size keysize)
uint32 string_hash(const void *key, Size keysize)
int(* HashCompareFunc)(const void *key1, const void *key2, Size keysize)
uint32(* HashValueFunc)(const void *key, Size keysize)
void *(* HashAllocFunc)(Size request)
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
MemoryContext TopMemoryContext
void * MemoryContextAlloc(MemoryContext context, Size size)
void MemoryContextDelete(MemoryContext context)
void MemoryContextSetIdentifier(MemoryContext context, const char *id)
#define MemoryContextIsValid(context)
#define AllocSetContextCreate
#define ALLOCSET_DEFAULT_SIZES
static uint64 pg_ceil_log2_64(uint64 num)
static uint32 pg_ceil_log2_32(uint32 num)
static void static void status(const char *fmt,...) pg_attribute_printf(1
size_t strlcpy(char *dst, const char *src, size_t siz)
Size add_size(Size s1, Size s2)
Size mul_size(Size s1, Size s2)
#define SpinLockInit(lock)
#define SpinLockRelease(lock)
#define SpinLockAcquire(lock)
struct HASHELEMENT * link
FreeListData freeList[NUM_FREELISTS]
int GetCurrentTransactionNestLevel(void)