dynahash.c Source File (original) (raw)

97#include <limits.h>

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123#define DEF_SEGSIZE 256

124#define DEF_SEGSIZE_SHIFT 8

125#define DEF_DIRSIZE 256

126

127

128#define NUM_FREELISTS 32

129

130

132

133

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153typedef struct

154{

155 slock_t mutex;

156 long nentries;

159

160

161

162

163

164

165

166

167

169{

170

171

172

173

174

175

176

177

178

179

181

182

183

184 long dsize;

185 long nsegs;

189

190

193 long num_partitions;

194 long max_dsize;

195 long ssize;

196 int sshift;

197 int nelem_alloc;

198

199#ifdef HASH_STATISTICS

200

201

202

203

204

205 long accesses;

206 long collisions;

207#endif

208};

209

210#define IS_PARTITIONED(hctl) ((hctl)->num_partitions != 0)

211

212#define FREELIST_IDX(hctl, hashcode) \

213 (IS_PARTITIONED(hctl) ? (hashcode) % NUM_FREELISTS : 0)

214

215

216

217

218

220{

228 char *tabname;

229 bool isshared;

230 bool isfixed;

231

232

233 bool frozen;

234

235

237 long ssize;

238 int sshift;

239};

240

241

242

243

244#define ELEMENTKEY(helem) (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))

245

246

247

248

249#define ELEMENT_FROM_KEY(key) \

250 ((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT))))

251

252

253

254

255#define MOD(x,y) ((x) & ((y)-1))

256

257#ifdef HASH_STATISTICS

258static long hash_accesses,

259 hash_collisions,

260 hash_expansions;

261#endif

262

263

264

265

268static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx);

283

284

285

286

287

289

290static void *

292{

296}

297

298

299

300

301

302

303

304

305

306static int

308{

309 return strncmp(key1, key2, keysize - 1);

310}

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

353{

356

357

358

359

360

364

365

366

367

368

369

370

371

372

373

374

376 {

377

379 }

380 else

381 {

382

385 else

388 "dynahash",

390 }

391

392

394 sizeof(HTAB) + strlen(tabname) + 1);

396

397 hashp->tabname = (char *) (hashp + 1);

398 strcpy(hashp->tabname, tabname);

399

400

403

404

405

406

408 {

411 }

413 {

415

418 else

420 }

421 else

422 {

423

424

425

426

427

428

429

430

433

435 }

436

437

438

439

440

441

442

443

444

445

450 else

451 hashp->match = memcmp;

452

453

454

455

459 {

460

461

462

463

464

465

466

468 }

469 else

471

472

475 else

477

479 {

480

481

482

483

484

487 hashp->hcxt = NULL;

489

490

492 {

493

494 hctl = hashp->hctl;

498

499 return hashp;

500 }

501 }

502 else

503 {

504

505 hashp->hctl = NULL;

506 hashp->dir = NULL;

509 }

510

511 if (!hashp->hctl)

512 {

514 if (!hashp->hctl)

516 (errcode(ERRCODE_OUT_OF_MEMORY),

517 errmsg("out of memory")));

518 }

519

520 hashp->frozen = false;

521

523

524 hctl = hashp->hctl;

525

527 {

528

530

531

532

533

534

535

537

539 }

540

542 {

545

547 }

548

549

550

551

553 {

556 }

557

558

561

562

566

567

569 elog(ERROR, "failed to initialize hash table \"%s\"", hashp->tabname);

570

571

572

573

574

575

576

577

578

580 nelem < hctl->nelem_alloc)

581 {

582 int i,

583 freelist_partitions,

584 nelem_alloc,

585 nelem_alloc_first;

586

587

588

589

590

593 else

594 freelist_partitions = 1;

595

596 nelem_alloc = nelem / freelist_partitions;

597 if (nelem_alloc <= 0)

598 nelem_alloc = 1;

599

600

601

602

603

604 if (nelem_alloc * freelist_partitions < nelem)

605 nelem_alloc_first =

606 nelem - nelem_alloc * (freelist_partitions - 1);

607 else

608 nelem_alloc_first = nelem_alloc;

609

610 for (i = 0; i < freelist_partitions; i++)

611 {

612 int temp = (i == 0) ? nelem_alloc_first : nelem_alloc;

613

616 (errcode(ERRCODE_OUT_OF_MEMORY),

617 errmsg("out of memory")));

618 }

619 }

620

623 return hashp;

624}

625

626

627

628

629static void

631{

633

635

638

640

641

643

646

647#ifdef HASH_STATISTICS

648 hctl->accesses = hctl->collisions = 0;

649#endif

650}

651

652

653

654

655

656static int

658{

659 int nelem_alloc;

660 Size elementSize;

661 Size allocSize;

662

663

664

666

667

668

669

670

671

672

673

674

675 allocSize = 32 * 4;

676 do

677 {

678 allocSize <<= 1;

679 nelem_alloc = allocSize / elementSize;

680 } while (nelem_alloc < 32);

681

682 return nelem_alloc;

683}

684

685

686

687

688

689static bool

691{

694 int nbuckets;

695 int nsegs;

696 int i;

697

698

699

700

704

705

706

707

708

710

711

712

713

714

715

716

717 while (nbuckets < hctl->num_partitions)

718 nbuckets <<= 1;

719

721 hctl->high_mask = (nbuckets << 1) - 1;

722

723

724

725

726 nsegs = (nbuckets - 1) / hctl->ssize + 1;

728

729

730

731

732

733 if (nsegs > hctl->dsize)

734 {

735 if (!(hashp->dir))

736 hctl->dsize = nsegs;

737 else

738 return false;

739 }

740

741

742 if (!(hashp->dir))

743 {

747 if (!hashp->dir)

748 return false;

749 }

750

751

752 for (segp = hashp->dir; hctl->nsegs < nsegs; hctl->nsegs++, segp++)

753 {

755 if (*segp == NULL)

756 return false;

757 }

758

759

761

762#ifdef HASH_DEBUG

763 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",

764 "TABLE POINTER ", hashp,

765 "DIRECTORY SIZE ", hctl->dsize,

766 "SEGMENT SIZE ", hctl->ssize,

767 "SEGMENT SHIFT ", hctl->sshift,

771 "NSEGS ", hctl->nsegs);

772#endif

773 return true;

774}

775

776

777

778

779

780

781

782

785{

787 long nBuckets,

788 nSegments,

789 nDirEntries,

790 nElementAllocs,

791 elementSize,

792 elementAllocCnt;

793

794

796

798

800 while (nDirEntries < nSegments)

801 nDirEntries <<= 1;

802

803

804 size = MAXALIGN(sizeof(HASHHDR));

805

807

810

812 nElementAllocs = (num_entries - 1) / elementAllocCnt + 1;

816 mul_size(elementAllocCnt, elementSize)));

817

818 return size;

819}

820

821

822

823

824

825

826

827

828

829

830long

832{

833 long nBuckets,

834 nSegments,

835 nDirEntries;

836

837

839

841

843 while (nDirEntries < nSegments)

844 nDirEntries <<= 1;

845

846 return nDirEntries;

847}

848

849

850

851

852

853

856{

860}

861

862

863

864

865void

867{

868 if (hashp != NULL)

869 {

870

872

874

876

877

878

879

881 }

882}

883

884void

886{

887#ifdef HASH_STATISTICS

888 fprintf(stderr, "%s: this HTAB -- accesses %ld collisions %ld\n",

889 where, hashp->hctl->accesses, hashp->hctl->collisions);

890

891 fprintf(stderr, "hash_stats: entries %ld keysize %ld maxp %u segmentcount %ld\n",

894 fprintf(stderr, "%s: total accesses %ld total collisions %ld\n",

895 where, hash_accesses, hash_collisions);

896 fprintf(stderr, "hash_stats: total expansions %ld\n",

897 hash_expansions);

898#endif

899}

900

901

902

903

904

905

906

907

908

909

910

913{

914 return hashp->hash(keyPtr, hashp->keysize);

915}

916

917

920{

922

923 bucket = hash_val & hctl->high_mask;

925 bucket = bucket & hctl->low_mask;

926

927 return bucket;

928}

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955void *

957 const void *keyPtr,

959 bool *foundPtr)

960{

962 keyPtr,

965 foundPtr);

966}

967

968void *

970 const void *keyPtr,

973 bool *foundPtr)

974{

976 int freelist_idx = FREELIST_IDX(hctl, hashvalue);

977 Size keysize;

981

982#ifdef HASH_STATISTICS

983 hash_accesses++;

984 hctl->accesses++;

985#endif

986

987

988

989

990

991

992

993

994

996 {

997

998

999

1000

1005 }

1006

1007

1008

1009

1011 currBucket = *prevBucketPtr;

1012

1013

1014

1015

1016 match = hashp->match;

1017 keysize = hashp->keysize;

1018

1019 while (currBucket != NULL)

1020 {

1021 if (currBucket->hashvalue == hashvalue &&

1022 match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)

1023 break;

1024 prevBucketPtr = &(currBucket->link);

1025 currBucket = *prevBucketPtr;

1026#ifdef HASH_STATISTICS

1027 hash_collisions++;

1028 hctl->collisions++;

1029#endif

1030 }

1031

1032 if (foundPtr)

1033 *foundPtr = (bool) (currBucket != NULL);

1034

1035

1036

1037

1039 {

1041 if (currBucket != NULL)

1043 return NULL;

1044

1046 if (currBucket != NULL)

1047 {

1048

1051

1052

1055

1056

1057 *prevBucketPtr = currBucket->link;

1058

1059

1062

1065

1066

1067

1068

1069

1070

1072 }

1073 return NULL;

1074

1077

1078 if (currBucket != NULL)

1080

1081

1083 elog(ERROR, "cannot insert into frozen hashtable \"%s\"",

1085

1087 if (currBucket == NULL)

1088 {

1089

1091 return NULL;

1092

1095 (errcode(ERRCODE_OUT_OF_MEMORY),

1096 errmsg("out of shared memory")));

1097 else

1099 (errcode(ERRCODE_OUT_OF_MEMORY),

1100 errmsg("out of memory")));

1101 }

1102

1103

1104 *prevBucketPtr = currBucket;

1105 currBucket->link = NULL;

1106

1107

1108 currBucket->hashvalue = hashvalue;

1110

1111

1112

1113

1114

1115

1116

1117

1119 }

1120

1121 elog(ERROR, "unrecognized hash action code: %d", (int) action);

1122

1123 return NULL;

1124}

1125

1126

1127

1128

1129

1130

1131

1132

1133

1134

1135

1136

1137

1138

1139

1140

1141

1142

1143

1144

1145bool

1147 void *existingEntry,

1148 const void *newKeyPtr)

1149{

1151 uint32 newhashvalue;

1152 Size keysize;

1159

1160#ifdef HASH_STATISTICS

1161 hash_accesses++;

1162 hctl->accesses++;

1163#endif

1164

1165

1167 elog(ERROR, "cannot update in frozen hashtable \"%s\"",

1169

1170

1171

1172

1173

1174

1176 &prevBucketPtr);

1177 currBucket = *prevBucketPtr;

1178

1179 while (currBucket != NULL)

1180 {

1181 if (currBucket == existingElement)

1182 break;

1183 prevBucketPtr = &(currBucket->link);

1184 currBucket = *prevBucketPtr;

1185 }

1186

1187 if (currBucket == NULL)

1188 elog(ERROR, "hash_update_hash_key argument is not in hashtable \"%s\"",

1190

1191 oldPrevPtr = prevBucketPtr;

1192

1193

1194

1195

1196

1197 newhashvalue = hashp->hash(newKeyPtr, hashp->keysize);

1199 currBucket = *prevBucketPtr;

1200

1201

1202

1203

1204 match = hashp->match;

1205 keysize = hashp->keysize;

1206

1207 while (currBucket != NULL)

1208 {

1209 if (currBucket->hashvalue == newhashvalue &&

1210 match(ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0)

1211 break;

1212 prevBucketPtr = &(currBucket->link);

1213 currBucket = *prevBucketPtr;

1214#ifdef HASH_STATISTICS

1215 hash_collisions++;

1216 hctl->collisions++;

1217#endif

1218 }

1219

1220 if (currBucket != NULL)

1221 return false;

1222

1223 currBucket = existingElement;

1224

1225

1226

1227

1228

1229

1230

1231

1232 if (bucket != newbucket)

1233 {

1234

1235 *oldPrevPtr = currBucket->link;

1236

1237

1238 *prevBucketPtr = currBucket;

1239 currBucket->link = NULL;

1240 }

1241

1242

1243 currBucket->hashvalue = newhashvalue;

1245

1246

1247

1248 return true;

1249}

1250

1251

1252

1253

1254

1255

1258{

1261

1262 for (;;)

1263 {

1264

1267

1268

1270

1271 if (newElement != NULL)

1272 break;

1273

1276

1277

1278

1279

1280

1281

1282

1283

1284

1285

1286

1287

1288

1290 {

1291 int borrow_from_idx;

1292

1294 return NULL;

1295

1296

1297 borrow_from_idx = freelist_idx;

1298 for (;;)

1299 {

1300 borrow_from_idx = (borrow_from_idx + 1) % NUM_FREELISTS;

1301 if (borrow_from_idx == freelist_idx)

1302 break;

1303

1306

1307 if (newElement != NULL)

1308 {

1311

1312

1316

1317 return newElement;

1318 }

1319

1321 }

1322

1323

1324 return NULL;

1325 }

1326 }

1327

1328

1331

1334

1335 return newElement;

1336}

1337

1338

1339

1340

1341long

1343{

1344 int i;

1346

1347

1348

1349

1350

1351

1353 {

1356 }

1357

1358 return sum;

1359}

1360

1361

1362

1363

1364

1365

1366

1367

1368

1369

1370

1371

1372

1373

1374

1375

1376

1377

1378

1379

1380

1381

1382

1383

1384

1385void

1387{

1388 status->hashp = hashp;

1394}

1395

1396

1397

1398

1399

1400

1401

1402

1403

1404

1405void

1408{

1410

1412

1415

1417 status->curEntry = *bucketPtr;

1418}

1419

1420void *

1422{

1423 HTAB *hashp;

1426 long ssize;

1427 long segment_num;

1428 long segment_ndx;

1432

1434 {

1435

1436

1437

1438

1439 while ((curElem = status->curEntry) != NULL)

1440 {

1443 continue;

1444 return (void *) ELEMENTKEY(curElem);

1445 }

1446

1448 return NULL;

1449 }

1450

1451 if ((curElem = status->curEntry) != NULL)

1452 {

1453

1455 if (status->curEntry == NULL)

1458 }

1459

1460

1461

1462

1464 hashp = status->hashp;

1465 hctl = hashp->hctl;

1466 ssize = hashp->ssize;

1468

1469 if (curBucket > max_bucket)

1470 {

1472 return NULL;

1473 }

1474

1475

1476

1477

1478 segment_num = curBucket >> hashp->sshift;

1479 segment_ndx = MOD(curBucket, ssize);

1480

1481 segp = hashp->dir[segment_num];

1482

1483

1484

1485

1486

1487

1488

1489 while ((curElem = segp[segment_ndx]) == NULL)

1490 {

1491

1492 if (++curBucket > max_bucket)

1493 {

1496 return NULL;

1497 }

1498 if (++segment_ndx >= ssize)

1499 {

1500 segment_num++;

1501 segment_ndx = 0;

1502 segp = hashp->dir[segment_num];

1503 }

1504 }

1505

1506

1508 if (status->curEntry == NULL)

1509 ++curBucket;

1512}

1513

1514void

1516{

1519}

1520

1521

1522

1523

1524

1525

1526

1527

1528

1529

1530

1531

1532

1533

1534void

1536{

1538 elog(ERROR, "cannot freeze shared hashtable \"%s\"", hashp->tabname);

1540 elog(ERROR, "cannot freeze hashtable \"%s\" because it has active scans",

1542 hashp->frozen = true;

1543}

1544

1545

1546

1547

1548

1549

1550

1551static bool

1553{

1556 new_seg;

1557 long old_bucket,

1558 new_bucket;

1559 long new_segnum,

1560 new_segndx;

1561 long old_segnum,

1562 old_segndx;

1564 *newlink;

1566 nextElement;

1567

1569

1570#ifdef HASH_STATISTICS

1571 hash_expansions++;

1572#endif

1573

1575 new_segnum = new_bucket >> hashp->sshift;

1576 new_segndx = MOD(new_bucket, hashp->ssize);

1577

1578 if (new_segnum >= hctl->nsegs)

1579 {

1580

1581 if (new_segnum >= hctl->dsize)

1583 return false;

1584 if (!(hashp->dir[new_segnum] = seg_alloc(hashp)))

1585 return false;

1587 }

1588

1589

1591

1592

1593

1594

1595

1596

1597

1598 old_bucket = (new_bucket & hctl->low_mask);

1599

1600

1601

1602

1604 {

1607 }

1608

1609

1610

1611

1612

1613

1614

1615 old_segnum = old_bucket >> hashp->sshift;

1616 old_segndx = MOD(old_bucket, hashp->ssize);

1617

1618 old_seg = hashp->dir[old_segnum];

1619 new_seg = hashp->dir[new_segnum];

1620

1621 oldlink = &old_seg[old_segndx];

1622 newlink = &new_seg[new_segndx];

1623

1624 for (currElement = *oldlink;

1625 currElement != NULL;

1626 currElement = nextElement)

1627 {

1628 nextElement = currElement->link;

1630 {

1631 *oldlink = currElement;

1632 oldlink = &currElement->link;

1633 }

1634 else

1635 {

1636 *newlink = currElement;

1637 newlink = &currElement->link;

1638 }

1639 }

1640

1641 *oldlink = NULL;

1642 *newlink = NULL;

1643

1644 return true;

1645}

1646

1647

1648static bool

1650{

1653 long new_dsize;

1654 long old_dirsize;

1655 long new_dirsize;

1656

1658 return false;

1659

1660

1661 new_dsize = hashp->hctl->dsize << 1;

1663 new_dirsize = new_dsize * sizeof(HASHSEGMENT);

1664

1665 old_p = hashp->dir;

1668

1669 if (p != NULL)

1670 {

1671 memcpy(p, old_p, old_dirsize);

1672 MemSet(((char *) p) + old_dirsize, 0, new_dirsize - old_dirsize);

1673 hashp->dir = p;

1675

1676

1679

1680 return true;

1681 }

1682

1683 return false;

1684}

1685

1686

1689{

1691

1694

1695 if (!segp)

1696 return NULL;

1697

1699

1700 return segp;

1701}

1702

1703

1704

1705

1706static bool

1708{

1710 Size elementSize;

1714 int i;

1715

1717 return false;

1718

1719

1721

1723 firstElement = (HASHELEMENT *) hashp->alloc(nelem * elementSize);

1724

1725 if (!firstElement)

1726 return false;

1727

1728

1729 prevElement = NULL;

1730 tmpElement = firstElement;

1731 for (i = 0; i < nelem; i++)

1732 {

1733 tmpElement->link = prevElement;

1734 prevElement = tmpElement;

1735 tmpElement = (HASHELEMENT *) (((char *) tmpElement) + elementSize);

1736 }

1737

1738

1741

1742

1745

1748

1749 return true;

1750}

1751

1752

1753

1754

1755

1758{

1761 long segment_num;

1762 long segment_ndx;

1764

1766

1767 segment_num = bucket >> hashp->sshift;

1768 segment_ndx = MOD(bucket, hashp->ssize);

1769

1770 segp = hashp->dir[segment_num];

1771

1772 if (segp == NULL)

1774

1775 *bucketptr = &segp[segment_ndx];

1776 return bucket;

1777}

1778

1779

1780static void

1782{

1783

1784

1785

1786

1789 else

1791}

1792

1793

1794int

1796{

1797

1798

1799

1800

1801 if (num > LONG_MAX / 2)

1802 num = LONG_MAX / 2;

1803

1804#if SIZEOF_LONG < 8

1806#else

1808#endif

1809}

1810

1811

1812static long

1814{

1815

1816 return 1L << my_log2(num);

1817}

1818

1819

1820static int

1822{

1823 if (num > INT_MAX / 2)

1824 num = INT_MAX / 2;

1825 return 1 << my_log2(num);

1826}

1827

1828

1829

1830

1831

1832

1833

1834

1835

1836

1837

1838

1839

1840

1841

1842

1843

1844

1845

1846

1847

1848

1849

1850

1851

1852

1853

1854

1855

1856

1857#define MAX_SEQ_SCANS 100

1858

1862

1863

1864

1865static void

1867{

1869 elog(ERROR, "too many active hash_seq_search scans, cannot start one on \"%s\"",

1874}

1875

1876

1877static void

1879{

1880 int i;

1881

1882

1884 {

1886 {

1890 return;

1891 }

1892 }

1893 elog(ERROR, "no hash_seq_search scan for hash table \"%s\"",

1895}

1896

1897

1898static bool

1900{

1901 int i;

1902

1904 {

1906 return true;

1907 }

1908 return false;

1909}

1910

1911

1912void

1914{

1915

1916

1917

1918

1919

1920

1921

1922

1923

1924 if (isCommit)

1925 {

1926 int i;

1927

1929 {

1930 elog(WARNING, "leaked hash_seq_search scan for hash table %p",

1932 }

1933 }

1935}

1936

1937

1938void

1940{

1941 int i;

1942

1943

1944

1945

1946

1947

1949 {

1951 {

1952 if (isCommit)

1953 elog(WARNING, "leaked hash_seq_search scan for hash table %p",

1958 }

1959 }

1960}

#define MemSet(start, val, len)

void(* pg_funcptr_t)(void)

#define fprintf(file, fmt, msg)

static HTAB * seq_scan_tables[MAX_SEQ_SCANS]

static int seq_scan_level[MAX_SEQ_SCANS]

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

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

#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_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)

void * hash_seq_search(HASH_SEQ_STATUS *status)

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)

#define FREELIST_IDX(hctl, hashcode)

long hash_get_num_entries(HTAB *hashp)

long hash_select_dirsize(long num_entries)

static pg_noreturn void hash_corrupted(HTAB *hashp)

Size hash_estimate_size(long num_entries, Size entrysize)

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

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)

static uint32 hash_initial_lookup(HTAB *hashp, uint32 hashvalue, HASHBUCKET **bucketptr)

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_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)

int errcode(int sqlerrcode)

int errmsg(const char *fmt,...)

#define ereport(elevel,...)

#define MCXT_ALLOC_NO_OOM

uint32 tag_hash(const void *key, Size keysize)

uint32 uint32_hash(const void *key, Size keysize)

uint32 string_hash(const void *key, Size keysize)

Assert(PointerIsAligned(start, uint64))

void *(* HashAllocFunc)(Size request)

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

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

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

void * MemoryContextAlloc(MemoryContext context, Size size)

void pfree(void *pointer)

MemoryContext TopMemoryContext

void * MemoryContextAllocExtended(MemoryContext context, Size size, int flags)

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)

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)