integerset.c Source File (original) (raw)

83#define SIMPLE8B_MAX_VALUES_PER_CODEWORD 240

94#define MAX_INTERNAL_ITEMS 64

95#define MAX_LEAF_ITEMS 64

100

101

102

103

104

105

106

107

108

109#define MAX_TREE_LEVELS 11

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

136

137

139{

142};

143

144

146{

147

150

151

152

153

154

157};

158

159

160typedef struct

161{

165

166#define MAX_VALUES_PER_LEAF_ITEM (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)

167

169{

170

173

175

177};

178

179

180

181

182

183

184

185

186#define MAX_BUFFERED_VALUES (MAX_VALUES_PER_LEAF_ITEM * 2)

187

188

189

190

191

192

193

194

195

197{

198

199

200

201

202

203

204

205

208

211

212

213

214

215

216

217

218

219

220

225

226

227

228

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

247

251

253 int iter_itemno;

254

256};

257

258

259

260

264

266 bool nextkey);

268 bool nextkey);

269

273

274

275

276

277

278

279

280

281

284{

286

290

291 intset->num_entries = 0;

292 intset->highest_value = 0;

293

294 intset->num_levels = 0;

296 memset(intset->rightmost_nodes, 0, sizeof(intset->rightmost_nodes));

297 intset->leftmost_leaf = NULL;

298

299 intset->num_buffered_values = 0;

300

301 intset->iter_active = false;

302 intset->iter_node = NULL;

303 intset->iter_itemno = 0;

304 intset->iter_valueno = 0;

305 intset->iter_num_values = 0;

306 intset->iter_values = NULL;

307

309}

310

311

312

313

316{

318

322

323 n->level = 0;

325

326 return n;

327}

328

331{

333

337

340 n->next = NULL;

341

342 return n;

343}

344

345

346

347

350{

351 return intset->num_entries;

352}

353

354

355

356

359{

360 return intset->mem_used;

361}

362

363

364

365

366

367

368void

370{

371 if (intset->iter_active)

372 elog(ERROR, "cannot add new values to integer set while iteration is in progress");

373

374 if (x <= intset->highest_value && intset->num_entries > 0)

375 elog(ERROR, "cannot add value to integer set out of order");

376

378 {

379

382 }

383

384

385 intset->buffered_values[intset->num_buffered_values] = x;

386 intset->num_buffered_values++;

387 intset->num_entries++;

388 intset->highest_value = x;

389}

390

391

392

393

394static void

396{

398 uint64 num_values = intset->num_buffered_values;

399 int num_packed = 0;

401

403

404

405

406

407

408 if (leaf == NULL)

409 {

410

411

412

413

414

416

418 intset->leftmost_leaf = leaf;

420 intset->num_levels = 1;

421 }

422

423

424

425

426

427

428

430 {

432 int num_encoded;

433

434

435

436

437

440 &num_encoded,

442

443

444

445

446

448 {

449

451

453 old_leaf->next = leaf;

456 }

458

459 num_packed += 1 + num_encoded;

460 }

461

462

463

464

465 if (num_packed < intset->num_buffered_values)

466 {

467 memmove(&intset->buffered_values[0],

468 &intset->buffered_values[num_packed],

469 (intset->num_buffered_values - num_packed) * sizeof(uint64));

470 }

471 intset->num_buffered_values -= num_packed;

472}

473

474

475

476

477

478

479static void

482{

484

486

487

488

489

490 if (level >= intset->num_levels)

491 {

494

495

497 elog(ERROR, "could not expand integer set, maximum number of levels reached");

498 intset->num_levels++;

499

500

501

502

503

504 if (intset->root->level == 0)

505 downlink_key = ((intset_leaf_node *) oldroot)->items[0].first;

506 else

508

510 parent->level = level;

511 parent->values[0] = downlink_key;

514

517 }

518

519

520

521

523

525 {

529 }

530 else

531 {

532

533

534

535

536

538 parent->level = level;

539 parent->values[0] = child_key;

542

544

546 }

547}

548

549

550

551

552bool

554{

557 int level;

558 int itemno;

560

561

562

563

564 if (intset->num_buffered_values > 0 && x >= intset->buffered_values[0])

565 {

567 intset->buffered_values,

568 intset->num_buffered_values,

569 false);

570 if (itemno >= intset->num_buffered_values)

571 return false;

572 else

573 return (intset->buffered_values[itemno] == x);

574 }

575

576

577

578

579

581 return false;

583 for (level = intset->num_levels - 1; level > 0; level--)

584 {

586

588

590 if (itemno == 0)

591 return false;

593 }

596

597

598

599

601 if (itemno == 0)

602 return false;

603 item = &leaf->items[itemno - 1];

604

605

606 if (item->first == x)

607 return true;

609

610

612 return true;

613

614 return false;

615}

616

617

618

619

620

621

622void

624{

625

626 intset->iter_active = true;

628 intset->iter_itemno = 0;

629 intset->iter_valueno = 0;

630 intset->iter_num_values = 0;

631 intset->iter_values = intset->iter_values_buf;

632}

633

634

635

636

637

638

639

640

641bool

643{

645 for (;;)

646 {

647

648 if (intset->iter_valueno < intset->iter_num_values)

649 {

651 return true;

652 }

653

654

655 if (intset->iter_node &&

656 intset->iter_itemno < intset->iter_node->num_items)

657 {

659 int num_decoded;

660

661 item = &intset->iter_node->items[intset->iter_itemno++];

662

663 intset->iter_values_buf[0] = item->first;

665 &intset->iter_values_buf[1],

667 intset->iter_num_values = num_decoded + 1;

668 intset->iter_valueno = 0;

669 continue;

670 }

671

672

673 if (intset->iter_node)

674 {

676 intset->iter_itemno = 0;

677 continue;

678 }

679

680

681

682

683

685 {

686 intset->iter_values = intset->buffered_values;

687 intset->iter_num_values = intset->num_buffered_values;

688 intset->iter_valueno = 0;

689 continue;

690 }

691

692 break;

693 }

694

695

696 intset->iter_active = false;

697 *next = 0;

698 return false;

699}

700

701

702

703

704

705

706

707

708

709

710

711

712static int

714{

715 int low,

716 high,

717 mid;

718

719 low = 0;

720 high = arr_elems;

721 while (high > low)

722 {

723 mid = low + (high - low) / 2;

724

725 if (nextkey)

726 {

727 if (item >= arr[mid])

728 low = mid + 1;

729 else

730 high = mid;

731 }

732 else

733 {

734 if (item > arr[mid])

735 low = mid + 1;

736 else

737 high = mid;

738 }

739 }

740

741 return low;

742}

743

744

745static int

747{

748 int low,

749 high,

750 mid;

751

752 low = 0;

753 high = arr_elems;

754 while (high > low)

755 {

756 mid = low + (high - low) / 2;

757

758 if (nextkey)

759 {

760 if (item >= arr[mid].first)

761 low = mid + 1;

762 else

763 high = mid;

764 }

765 else

766 {

767 if (item > arr[mid].first)

768 low = mid + 1;

769 else

770 high = mid;

771 }

772 }

773

774 return low;

775}

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

821{

825

826{

827 {0, 240},

828 {0, 120},

829 {1, 60},

830 {2, 30},

831 {3, 20},

832 {4, 15},

833 {5, 12},

834 {6, 10},

835 {7, 8},

836

837 {8, 7},

838

839 {10, 6},

840 {12, 5},

841 {15, 4},

842 {20, 3},

843 {30, 2},

844 {60, 1},

845

846 {0, 0}

848

849

850

851

852

853

854

855

856#define EMPTY_CODEWORD UINT64CONST(0x0FFFFFFFFFFFFFFF)

857

858

859

860

861

862

863

864

865

866

867

868

869

870

873{

874 int selector;

875 int nints;

876 int bits;

880 int i;

881

882 Assert(ints[0] > base);

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899 selector = 0;

902 diff = ints[0] - base - 1;

903 last_val = ints[0];

904 i = 0;

905 for (;;)

906 {

908 {

909

910 selector++;

913

914 if (i >= nints)

915 break;

916 }

917 else

918 {

919

920 i++;

921 if (i >= nints)

922 break;

923

924 Assert(ints[i] > last_val);

925 diff = ints[i] - last_val - 1;

926 last_val = ints[i];

927 }

928 }

929

930 if (nints == 0)

931 {

932

933

934

935

936

937

938

940 *num_encoded = 0;

942 }

943

944

945

946

947

948

949 codeword = 0;

950 if (bits > 0)

951 {

952 for (i = nints - 1; i > 0; i--)

953 {

954 diff = ints[i] - ints[i - 1] - 1;

955 codeword |= diff;

956 codeword <<= bits;

957 }

958 diff = ints[0] - base - 1;

959 codeword |= diff;

960 }

961

962

963 codeword |= (uint64) selector << 60;

964

965 *num_encoded = nints;

966 return codeword;

967}

968

969

970

971

972

973static int

975{

976 int selector = (codeword >> 60);

981

983 return 0;

984

985 curr_value = base;

986 for (int i = 0; i < nints; i++)

987 {

988 uint64 diff = codeword & mask;

989

990 curr_value += 1 + diff;

991 decoded[i] = curr_value;

992 codeword >>= bits;

993 }

994 return nints;

995}

996

997

998

999

1000

1001

1002static bool

1004{

1005 int selector = (codeword >> 60);

1008

1010 return false;

1011

1012 if (bits == 0)

1013 {

1014

1015 return (key - base) <= nints;

1016 }

1017 else

1018 {

1021

1022 curr_value = base;

1023 for (int i = 0; i < nints; i++)

1024 {

1025 uint64 diff = codeword & mask;

1026

1027 curr_value += 1 + diff;

1028

1029 if (curr_value >= key)

1030 {

1031 if (curr_value == key)

1032 return true;

1033 else

1034 return false;

1035 }

1036

1037 codeword >>= bits;

1038 }

1039 }

1040 return false;

1041}

Datum intset(PG_FUNCTION_ARGS)

static Datum values[MAXATTR]

Assert(PointerIsAligned(start, uint64))

#define MAX_VALUES_PER_LEAF_ITEM

uint64 intset_memory_usage(IntegerSet *intset)

uint64 intset_num_entries(IntegerSet *intset)

static void intset_update_upper(IntegerSet *intset, int level, intset_node *child, uint64 child_key)

bool intset_is_member(IntegerSet *intset, uint64 x)

#define MAX_INTERNAL_ITEMS

#define MAX_BUFFERED_VALUES

static intset_internal_node * intset_new_internal_node(IntegerSet *intset)

void intset_begin_iterate(IntegerSet *intset)

static int intset_binsrch_uint64(uint64 item, uint64 *arr, int arr_elems, bool nextkey)

static void intset_flush_buffered_values(IntegerSet *intset)

static uint64 simple8b_encode(const uint64 *ints, int *num_encoded, uint64 base)

bool intset_iterate_next(IntegerSet *intset, uint64 *next)

static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)

IntegerSet * intset_create(void)

void intset_add_member(IntegerSet *intset, uint64 x)

static const struct simple8b_mode simple8b_modes[17]

static int intset_binsrch_leaf(uint64 item, leaf_item *arr, int arr_elems, bool nextkey)

static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)

static intset_leaf_node * intset_new_leaf_node(IntegerSet *intset)

if(TABLE==NULL||TABLE_index==NULL)

void * MemoryContextAlloc(MemoryContext context, Size size)

Size GetMemoryChunkSpace(void *pointer)

MemoryContext CurrentMemoryContext

intset_node * rightmost_nodes[MAX_TREE_LEVELS]

uint64 iter_values_buf[MAX_VALUES_PER_LEAF_ITEM]

intset_leaf_node * leftmost_leaf

const uint64 * iter_values

uint64 buffered_values[MAX_BUFFERED_VALUES]

intset_leaf_node * iter_node

intset_node * downlinks[MAX_INTERNAL_ITEMS]

uint64 values[MAX_INTERNAL_ITEMS]

leaf_item items[MAX_LEAF_ITEMS]