From 3a51f25ae712b792bdde90b133c09b0b940f4198 Mon Sep 17 00:00:00 2001 From: Nathan Bossart Date: Mon, 4 Sep 2023 15:04:40 -0700 Subject: [PATCH v7 1/5] Allow binaryheap to use any type. We would like to make binaryheap available to frontend code in a future commit, but presently the implementation uses Datum for the node type, which is inaccessible in the frontend. This commit modifies the implementation to allow using any type for the nodes. binaryheap_allocate() now requires callers to specify the size of the node, and several of the other functions now use void pointers. --- src/backend/executor/nodeGatherMerge.c | 19 ++-- src/backend/executor/nodeMergeAppend.c | 22 ++--- src/backend/lib/binaryheap.c | 99 +++++++++++-------- src/backend/postmaster/pgarch.c | 36 ++++--- .../replication/logical/reorderbuffer.c | 21 ++-- src/backend/storage/buffer/bufmgr.c | 20 ++-- src/include/lib/binaryheap.h | 21 ++-- 7 files changed, 137 insertions(+), 101 deletions(-) diff --git a/src/backend/executor/nodeGatherMerge.c b/src/backend/executor/nodeGatherMerge.c index 9d5e1a46e9..f76406b575 100644 --- a/src/backend/executor/nodeGatherMerge.c +++ b/src/backend/executor/nodeGatherMerge.c @@ -52,7 +52,7 @@ typedef struct GMReaderTupleBuffer } GMReaderTupleBuffer; static TupleTableSlot *ExecGatherMerge(PlanState *pstate); -static int32 heap_compare_slots(Datum a, Datum b, void *arg); +static int32 heap_compare_slots(const void *a, const void *b, void *arg); static TupleTableSlot *gather_merge_getnext(GatherMergeState *gm_state); static MinimalTuple gm_readnext_tuple(GatherMergeState *gm_state, int nreader, bool nowait, bool *done); @@ -429,6 +429,7 @@ gather_merge_setup(GatherMergeState *gm_state) /* Allocate the resources for the merge */ gm_state->gm_heap = binaryheap_allocate(nreaders + 1, + sizeof(int), heap_compare_slots, gm_state); } @@ -489,7 +490,7 @@ reread: /* Don't have a tuple yet, try to get one */ if (gather_merge_readnext(gm_state, i, nowait)) binaryheap_add_unordered(gm_state->gm_heap, - Int32GetDatum(i)); + &i); } else { @@ -565,14 +566,14 @@ gather_merge_getnext(GatherMergeState *gm_state) * the heap, because it might now compare differently against the * other elements of the heap. */ - i = DatumGetInt32(binaryheap_first(gm_state->gm_heap)); + binaryheap_first(gm_state->gm_heap, &i); if (gather_merge_readnext(gm_state, i, false)) - binaryheap_replace_first(gm_state->gm_heap, Int32GetDatum(i)); + binaryheap_replace_first(gm_state->gm_heap, &i); else { /* reader exhausted, remove it from heap */ - (void) binaryheap_remove_first(gm_state->gm_heap); + binaryheap_remove_first(gm_state->gm_heap, NULL); } } @@ -585,7 +586,7 @@ gather_merge_getnext(GatherMergeState *gm_state) else { /* Return next tuple from whichever participant has the leading one */ - i = DatumGetInt32(binaryheap_first(gm_state->gm_heap)); + binaryheap_first(gm_state->gm_heap, &i); return gm_state->gm_slots[i]; } } @@ -750,11 +751,11 @@ typedef int32 SlotNumber; * Compare the tuples in the two given slots. */ static int32 -heap_compare_slots(Datum a, Datum b, void *arg) +heap_compare_slots(const void *a, const void *b, void *arg) { GatherMergeState *node = (GatherMergeState *) arg; - SlotNumber slot1 = DatumGetInt32(a); - SlotNumber slot2 = DatumGetInt32(b); + SlotNumber slot1 = *((const int *) a); + SlotNumber slot2 = *((const int *) b); TupleTableSlot *s1 = node->gm_slots[slot1]; TupleTableSlot *s2 = node->gm_slots[slot2]; diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c index 21b5726e6e..e0ace294a0 100644 --- a/src/backend/executor/nodeMergeAppend.c +++ b/src/backend/executor/nodeMergeAppend.c @@ -52,7 +52,7 @@ typedef int32 SlotNumber; static TupleTableSlot *ExecMergeAppend(PlanState *pstate); -static int heap_compare_slots(Datum a, Datum b, void *arg); +static int heap_compare_slots(const void *a, const void *b, void *arg); /* ---------------------------------------------------------------- @@ -125,8 +125,8 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags) mergestate->ms_nplans = nplans; mergestate->ms_slots = (TupleTableSlot **) palloc0(sizeof(TupleTableSlot *) * nplans); - mergestate->ms_heap = binaryheap_allocate(nplans, heap_compare_slots, - mergestate); + mergestate->ms_heap = binaryheap_allocate(nplans, sizeof(int), + heap_compare_slots, mergestate); /* * Miscellaneous initialization @@ -229,7 +229,7 @@ ExecMergeAppend(PlanState *pstate) { node->ms_slots[i] = ExecProcNode(node->mergeplans[i]); if (!TupIsNull(node->ms_slots[i])) - binaryheap_add_unordered(node->ms_heap, Int32GetDatum(i)); + binaryheap_add_unordered(node->ms_heap, &i); } binaryheap_build(node->ms_heap); node->ms_initialized = true; @@ -244,12 +244,12 @@ ExecMergeAppend(PlanState *pstate) * by doing this before returning from the prior call, but it's better * to not pull tuples until necessary.) */ - i = DatumGetInt32(binaryheap_first(node->ms_heap)); + binaryheap_first(node->ms_heap, &i); node->ms_slots[i] = ExecProcNode(node->mergeplans[i]); if (!TupIsNull(node->ms_slots[i])) - binaryheap_replace_first(node->ms_heap, Int32GetDatum(i)); + binaryheap_replace_first(node->ms_heap, &i); else - (void) binaryheap_remove_first(node->ms_heap); + binaryheap_remove_first(node->ms_heap, NULL); } if (binaryheap_empty(node->ms_heap)) @@ -259,7 +259,7 @@ ExecMergeAppend(PlanState *pstate) } else { - i = DatumGetInt32(binaryheap_first(node->ms_heap)); + binaryheap_first(node->ms_heap, &i); result = node->ms_slots[i]; } @@ -270,11 +270,11 @@ ExecMergeAppend(PlanState *pstate) * Compare the tuples in the two given slots. */ static int32 -heap_compare_slots(Datum a, Datum b, void *arg) +heap_compare_slots(const void *a, const void *b, void *arg) { MergeAppendState *node = (MergeAppendState *) arg; - SlotNumber slot1 = DatumGetInt32(a); - SlotNumber slot2 = DatumGetInt32(b); + SlotNumber slot1 = *((const int *) a); + SlotNumber slot2 = *((const int *) b); TupleTableSlot *s1 = node->ms_slots[slot1]; TupleTableSlot *s2 = node->ms_slots[slot2]; diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.c index 1737546757..6f63181c4c 100644 --- a/src/backend/lib/binaryheap.c +++ b/src/backend/lib/binaryheap.c @@ -29,16 +29,19 @@ static void sift_up(binaryheap *heap, int node_off); * argument specified by 'arg'. */ binaryheap * -binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg) +binaryheap_allocate(int capacity, size_t elem_size, + binaryheap_comparator compare, void *arg) { int sz; binaryheap *heap; - sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * capacity; + sz = offsetof(binaryheap, bh_nodes) + elem_size * (capacity + 1); heap = (binaryheap *) palloc(sz); heap->bh_space = capacity; + heap->bh_elem_size = elem_size; heap->bh_compare = compare; heap->bh_arg = arg; + heap->bh_hole = &heap->bh_nodes[capacity * elem_size]; heap->bh_size = 0; heap->bh_has_heap_property = true; @@ -97,6 +100,27 @@ parent_offset(int i) return (i - 1) / 2; } +/* + * This utility function returns a pointer to the nth node of the binary heap. + */ +static inline void * +bh_node(binaryheap *heap, int n) +{ + return &heap->bh_nodes[n * heap->bh_elem_size]; +} + +/* + * This utility function sets the nth node of the binary heap to the value that + * d points to. + */ +static inline void +bh_set(binaryheap *heap, int n, const void *d) +{ + void *node = bh_node(heap, n); + + memmove(node, d, heap->bh_elem_size); +} + /* * binaryheap_add_unordered * @@ -106,12 +130,12 @@ parent_offset(int i) * afterwards. */ void -binaryheap_add_unordered(binaryheap *heap, Datum d) +binaryheap_add_unordered(binaryheap *heap, void *d) { if (heap->bh_size >= heap->bh_space) elog(ERROR, "out of binary heap slots"); heap->bh_has_heap_property = false; - heap->bh_nodes[heap->bh_size] = d; + bh_set(heap, heap->bh_size, d); heap->bh_size++; } @@ -138,11 +162,11 @@ binaryheap_build(binaryheap *heap) * the heap property. */ void -binaryheap_add(binaryheap *heap, Datum d) +binaryheap_add(binaryheap *heap, void *d) { if (heap->bh_size >= heap->bh_space) elog(ERROR, "out of binary heap slots"); - heap->bh_nodes[heap->bh_size] = d; + bh_set(heap, heap->bh_size, d); heap->bh_size++; sift_up(heap, heap->bh_size - 1); } @@ -154,11 +178,11 @@ binaryheap_add(binaryheap *heap, Datum d) * without modifying the heap. The caller must ensure that this * routine is not used on an empty heap. Always O(1). */ -Datum -binaryheap_first(binaryheap *heap) +void +binaryheap_first(binaryheap *heap, void *result) { Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); - return heap->bh_nodes[0]; + memmove(result, heap->bh_nodes, heap->bh_elem_size); } /* @@ -169,31 +193,28 @@ binaryheap_first(binaryheap *heap) * that this routine is not used on an empty heap. O(log n) worst * case. */ -Datum -binaryheap_remove_first(binaryheap *heap) +void +binaryheap_remove_first(binaryheap *heap, void *result) { - Datum result; - Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); /* extract the root node, which will be the result */ - result = heap->bh_nodes[0]; + if (result) + memmove(result, heap->bh_nodes, heap->bh_elem_size); /* easy if heap contains one element */ if (heap->bh_size == 1) { heap->bh_size--; - return result; + return; } /* * Remove the last node, placing it in the vacated root entry, and sift * the new root node down to its correct position. */ - heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size]; + bh_set(heap, 0, bh_node(heap, --heap->bh_size)); sift_down(heap, 0); - - return result; } /* @@ -204,11 +225,11 @@ binaryheap_remove_first(binaryheap *heap) * sifting the new node down. */ void -binaryheap_replace_first(binaryheap *heap, Datum d) +binaryheap_replace_first(binaryheap *heap, void *d) { Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); - heap->bh_nodes[0] = d; + bh_set(heap, 0, d); if (heap->bh_size > 1) sift_down(heap, 0); @@ -221,26 +242,26 @@ binaryheap_replace_first(binaryheap *heap, Datum d) static void sift_up(binaryheap *heap, int node_off) { - Datum node_val = heap->bh_nodes[node_off]; + memmove(heap->bh_hole, bh_node(heap, node_off), heap->bh_elem_size); /* * Within the loop, the node_off'th array entry is a "hole" that - * notionally holds node_val, but we don't actually store node_val there - * till the end, saving some unnecessary data copying steps. + * notionally holds the swapped value, but we don't actually store the + * value there till the end, saving some unnecessary data copying steps. */ while (node_off != 0) { int cmp; int parent_off; - Datum parent_val; + void *parent_val; /* * If this node is smaller than its parent, the heap condition is * satisfied, and we're done. */ parent_off = parent_offset(node_off); - parent_val = heap->bh_nodes[parent_off]; - cmp = heap->bh_compare(node_val, + parent_val = bh_node(heap, parent_off); + cmp = heap->bh_compare(heap->bh_hole, parent_val, heap->bh_arg); if (cmp <= 0) @@ -250,11 +271,11 @@ sift_up(binaryheap *heap, int node_off) * Otherwise, swap the parent value with the hole, and go on to check * the node's new parent. */ - heap->bh_nodes[node_off] = parent_val; + bh_set(heap, node_off, parent_val); node_off = parent_off; } /* Re-fill the hole */ - heap->bh_nodes[node_off] = node_val; + bh_set(heap, node_off, heap->bh_hole); } /* @@ -264,12 +285,12 @@ sift_up(binaryheap *heap, int node_off) static void sift_down(binaryheap *heap, int node_off) { - Datum node_val = heap->bh_nodes[node_off]; + memmove(heap->bh_hole, bh_node(heap, node_off), heap->bh_elem_size); /* * Within the loop, the node_off'th array entry is a "hole" that - * notionally holds node_val, but we don't actually store node_val there - * till the end, saving some unnecessary data copying steps. + * notionally holds the swapped value, but we don't actually store the + * value there till the end, saving some unnecessary data copying steps. */ while (true) { @@ -279,21 +300,21 @@ sift_down(binaryheap *heap, int node_off) /* Is the left child larger than the parent? */ if (left_off < heap->bh_size && - heap->bh_compare(node_val, - heap->bh_nodes[left_off], + heap->bh_compare(heap->bh_hole, + bh_node(heap, left_off), heap->bh_arg) < 0) swap_off = left_off; /* Is the right child larger than the parent? */ if (right_off < heap->bh_size && - heap->bh_compare(node_val, - heap->bh_nodes[right_off], + heap->bh_compare(heap->bh_hole, + bh_node(heap, right_off), heap->bh_arg) < 0) { /* swap with the larger child */ if (!swap_off || - heap->bh_compare(heap->bh_nodes[left_off], - heap->bh_nodes[right_off], + heap->bh_compare(bh_node(heap, left_off), + bh_node(heap, right_off), heap->bh_arg) < 0) swap_off = right_off; } @@ -309,9 +330,9 @@ sift_down(binaryheap *heap, int node_off) * Otherwise, swap the hole with the child that violates the heap * property; then go on to check its children. */ - heap->bh_nodes[node_off] = heap->bh_nodes[swap_off]; + bh_set(heap, node_off, bh_node(heap, swap_off)); node_off = swap_off; } /* Re-fill the hole */ - heap->bh_nodes[node_off] = node_val; + bh_set(heap, node_off, heap->bh_hole); } diff --git a/src/backend/postmaster/pgarch.c b/src/backend/postmaster/pgarch.c index 46af349564..f7ee95d8f9 100644 --- a/src/backend/postmaster/pgarch.c +++ b/src/backend/postmaster/pgarch.c @@ -145,7 +145,7 @@ static bool pgarch_readyXlog(char *xlog); static void pgarch_archiveDone(char *xlog); static void pgarch_die(int code, Datum arg); static void HandlePgArchInterrupts(void); -static int ready_file_comparator(Datum a, Datum b, void *arg); +static int ready_file_comparator(const void *a, const void *b, void *arg); static void LoadArchiveLibrary(void); static void pgarch_call_module_shutdown_cb(int code, Datum arg); @@ -250,6 +250,7 @@ PgArchiverMain(void) /* Initialize our max-heap for prioritizing files to archive. */ arch_files->arch_heap = binaryheap_allocate(NUM_FILES_PER_DIRECTORY_SCAN, + sizeof(char *), ready_file_comparator, NULL); /* Load the archive_library. */ @@ -631,22 +632,27 @@ pgarch_readyXlog(char *xlog) /* If the heap isn't full yet, quickly add it. */ arch_file = arch_files->arch_filenames[arch_files->arch_heap->bh_size]; strcpy(arch_file, basename); - binaryheap_add_unordered(arch_files->arch_heap, CStringGetDatum(arch_file)); + binaryheap_add_unordered(arch_files->arch_heap, &arch_file); /* If we just filled the heap, make it a valid one. */ if (arch_files->arch_heap->bh_size == NUM_FILES_PER_DIRECTORY_SCAN) binaryheap_build(arch_files->arch_heap); } - else if (ready_file_comparator(binaryheap_first(arch_files->arch_heap), - CStringGetDatum(basename), NULL) > 0) + else { - /* - * Remove the lowest priority file and add the current one to the - * heap. - */ - arch_file = DatumGetCString(binaryheap_remove_first(arch_files->arch_heap)); - strcpy(arch_file, basename); - binaryheap_add(arch_files->arch_heap, CStringGetDatum(arch_file)); + char *root; + + binaryheap_first(arch_files->arch_heap, &root); + if (ready_file_comparator(&root, &basename, NULL) > 0) + { + /* + * Remove the lowest priority file and add the current one to + * the heap. + */ + binaryheap_remove_first(arch_files->arch_heap, &arch_file); + strcpy(arch_file, basename); + binaryheap_add(arch_files->arch_heap, &arch_file); + } } } FreeDir(rldir); @@ -668,7 +674,7 @@ pgarch_readyXlog(char *xlog) */ arch_files->arch_files_size = arch_files->arch_heap->bh_size; for (int i = 0; i < arch_files->arch_files_size; i++) - arch_files->arch_files[i] = DatumGetCString(binaryheap_remove_first(arch_files->arch_heap)); + binaryheap_remove_first(arch_files->arch_heap, &arch_files->arch_files[i]); /* Return the highest priority file. */ arch_files->arch_files_size--; @@ -686,10 +692,10 @@ pgarch_readyXlog(char *xlog) * If "a" and "b" have equivalent values, 0 will be returned. */ static int -ready_file_comparator(Datum a, Datum b, void *arg) +ready_file_comparator(const void *a, const void *b, void *arg) { - char *a_str = DatumGetCString(a); - char *b_str = DatumGetCString(b); + const char *a_str = *((const char **) a); + const char *b_str = *((const char **) b); bool a_history = IsTLHistoryFileName(a_str); bool b_history = IsTLHistoryFileName(b_str); diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c index 12edc5772a..e22680da0b 100644 --- a/src/backend/replication/logical/reorderbuffer.c +++ b/src/backend/replication/logical/reorderbuffer.c @@ -1223,11 +1223,11 @@ ReorderBufferCommitChild(ReorderBuffer *rb, TransactionId xid, * Binary heap comparison function. */ static int -ReorderBufferIterCompare(Datum a, Datum b, void *arg) +ReorderBufferIterCompare(const void *a, const void *b, void *arg) { ReorderBufferIterTXNState *state = (ReorderBufferIterTXNState *) arg; - XLogRecPtr pos_a = state->entries[DatumGetInt32(a)].lsn; - XLogRecPtr pos_b = state->entries[DatumGetInt32(b)].lsn; + XLogRecPtr pos_a = state->entries[*((const int *) a)].lsn; + XLogRecPtr pos_b = state->entries[*((const int *) b)].lsn; if (pos_a < pos_b) return 1; @@ -1297,6 +1297,7 @@ ReorderBufferIterTXNInit(ReorderBuffer *rb, ReorderBufferTXN *txn, /* allocate heap */ state->heap = binaryheap_allocate(state->nr_txns, + sizeof(int), ReorderBufferIterCompare, state); @@ -1330,7 +1331,8 @@ ReorderBufferIterTXNInit(ReorderBuffer *rb, ReorderBufferTXN *txn, state->entries[off].change = cur_change; state->entries[off].txn = txn; - binaryheap_add_unordered(state->heap, Int32GetDatum(off++)); + binaryheap_add_unordered(state->heap, &off); + off++; } /* add subtransactions if they contain changes */ @@ -1359,7 +1361,8 @@ ReorderBufferIterTXNInit(ReorderBuffer *rb, ReorderBufferTXN *txn, state->entries[off].change = cur_change; state->entries[off].txn = cur_txn; - binaryheap_add_unordered(state->heap, Int32GetDatum(off++)); + binaryheap_add_unordered(state->heap, &off); + off++; } } @@ -1384,7 +1387,7 @@ ReorderBufferIterTXNNext(ReorderBuffer *rb, ReorderBufferIterTXNState *state) if (state->heap->bh_size == 0) return NULL; - off = DatumGetInt32(binaryheap_first(state->heap)); + binaryheap_first(state->heap, &off); entry = &state->entries[off]; /* free memory we might have "leaked" in the previous *Next call */ @@ -1414,7 +1417,7 @@ ReorderBufferIterTXNNext(ReorderBuffer *rb, ReorderBufferIterTXNState *state) state->entries[off].lsn = next_change->lsn; state->entries[off].change = next_change; - binaryheap_replace_first(state->heap, Int32GetDatum(off)); + binaryheap_replace_first(state->heap, &off); return change; } @@ -1450,14 +1453,14 @@ ReorderBufferIterTXNNext(ReorderBuffer *rb, ReorderBufferIterTXNState *state) /* txn stays the same */ state->entries[off].lsn = next_change->lsn; state->entries[off].change = next_change; - binaryheap_replace_first(state->heap, Int32GetDatum(off)); + binaryheap_replace_first(state->heap, &off); return change; } } /* ok, no changes there anymore, remove */ - binaryheap_remove_first(state->heap); + binaryheap_remove_first(state->heap, NULL); return change; } diff --git a/src/backend/storage/buffer/bufmgr.c b/src/backend/storage/buffer/bufmgr.c index 3bd82dbfca..7c78a0d625 100644 --- a/src/backend/storage/buffer/bufmgr.c +++ b/src/backend/storage/buffer/bufmgr.c @@ -501,7 +501,7 @@ static void CheckForBufferLeaks(void); static int rlocator_comparator(const void *p1, const void *p2); static inline int buffertag_comparator(const BufferTag *ba, const BufferTag *bb); static inline int ckpt_buforder_comparator(const CkptSortItem *a, const CkptSortItem *b); -static int ts_ckpt_progress_comparator(Datum a, Datum b, void *arg); +static int ts_ckpt_progress_comparator(const void *a, const void *b, void *arg); /* @@ -2640,6 +2640,7 @@ BufferSync(int flags) * processed buffer is. */ ts_heap = binaryheap_allocate(num_spaces, + sizeof(CkptTsStatus *), ts_ckpt_progress_comparator, NULL); @@ -2649,7 +2650,7 @@ BufferSync(int flags) ts_stat->progress_slice = (float8) num_to_scan / ts_stat->num_to_scan; - binaryheap_add_unordered(ts_heap, PointerGetDatum(ts_stat)); + binaryheap_add_unordered(ts_heap, &ts_stat); } binaryheap_build(ts_heap); @@ -2665,8 +2666,9 @@ BufferSync(int flags) while (!binaryheap_empty(ts_heap)) { BufferDesc *bufHdr = NULL; - CkptTsStatus *ts_stat = (CkptTsStatus *) - DatumGetPointer(binaryheap_first(ts_heap)); + CkptTsStatus *ts_stat; + + binaryheap_first(ts_heap, &ts_stat); buf_id = CkptBufferIds[ts_stat->index].buf_id; Assert(buf_id != -1); @@ -2708,12 +2710,12 @@ BufferSync(int flags) /* Have all the buffers from the tablespace been processed? */ if (ts_stat->num_scanned == ts_stat->num_to_scan) { - binaryheap_remove_first(ts_heap); + binaryheap_remove_first(ts_heap, NULL); } else { /* update heap with the new progress */ - binaryheap_replace_first(ts_heap, PointerGetDatum(ts_stat)); + binaryheap_replace_first(ts_heap, &ts_stat); } /* @@ -5416,10 +5418,10 @@ ckpt_buforder_comparator(const CkptSortItem *a, const CkptSortItem *b) * progress. */ static int -ts_ckpt_progress_comparator(Datum a, Datum b, void *arg) +ts_ckpt_progress_comparator(const void *a, const void *b, void *arg) { - CkptTsStatus *sa = (CkptTsStatus *) a; - CkptTsStatus *sb = (CkptTsStatus *) b; + const CkptTsStatus *sa = *((const CkptTsStatus **) a); + const CkptTsStatus *sb = *((const CkptTsStatus **) b); /* we want a min-heap, so return 1 for the a < b */ if (sa->progress < sb->progress) diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 52f7b06b25..b8c7ef81ef 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -15,7 +15,7 @@ * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b, * and >0 iff a > b. For a min-heap, the conditions are reversed. */ -typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg); +typedef int (*binaryheap_comparator) (const void *a, const void *b, void *arg); /* * binaryheap @@ -25,29 +25,32 @@ typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg); * bh_has_heap_property no unordered operations since last heap build * bh_compare comparison function to define the heap property * bh_arg user data for comparison function - * bh_nodes variable-length array of "space" nodes + * bh_hole extra node used during sifting operations + * bh_nodes variable-length array of "space + 1" nodes */ typedef struct binaryheap { int bh_size; int bh_space; + size_t bh_elem_size; bool bh_has_heap_property; /* debugging cross-check */ binaryheap_comparator bh_compare; void *bh_arg; - Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]; + void *bh_hole; + char bh_nodes[FLEXIBLE_ARRAY_MEMBER]; } binaryheap; -extern binaryheap *binaryheap_allocate(int capacity, +extern binaryheap *binaryheap_allocate(int capacity, size_t elem_size, binaryheap_comparator compare, void *arg); extern void binaryheap_reset(binaryheap *heap); extern void binaryheap_free(binaryheap *heap); -extern void binaryheap_add_unordered(binaryheap *heap, Datum d); +extern void binaryheap_add_unordered(binaryheap *heap, void *d); extern void binaryheap_build(binaryheap *heap); -extern void binaryheap_add(binaryheap *heap, Datum d); -extern Datum binaryheap_first(binaryheap *heap); -extern Datum binaryheap_remove_first(binaryheap *heap); -extern void binaryheap_replace_first(binaryheap *heap, Datum d); +extern void binaryheap_add(binaryheap *heap, void *d); +extern void binaryheap_first(binaryheap *heap, void *result); +extern void binaryheap_remove_first(binaryheap *heap, void *result); +extern void binaryheap_replace_first(binaryheap *heap, void *d); #define binaryheap_empty(h) ((h)->bh_size == 0) -- 2.25.1