From 810f64a01567610af7b92b0de930f16f3e20064e Mon Sep 17 00:00:00 2001 From: Masahiko Sawada Date: Thu, 11 Apr 2024 17:18:05 +0900 Subject: Revert indexed and enlargable binary heap implementation. This reverts commit b840508644 and bcb14f4abc. These commits were made for commit 5bec1d6bc5 (Improve eviction algorithm in ReorderBuffer using max-heap for many subtransactions). However, per discussion, commit efb8acc0d0 replaced binary heap + index with pairing heap, and made these commits unnecessary. Reported-by: Jeff Davis Discussion: https://postgr.es/m/12747c15811d94efcc5cda72d6b35c80d7bf3443.camel%40j-davis.com --- src/include/lib/binaryheap.h | 40 +++------------------------------------- 1 file changed, 3 insertions(+), 37 deletions(-) (limited to 'src/include/lib/binaryheap.h') diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 4c1a1bb274b..19025c08ef1 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -29,29 +29,6 @@ typedef Datum bh_node_type; */ typedef int (*binaryheap_comparator) (bh_node_type a, bh_node_type b, void *arg); -/* - * Struct for a hash table element to store the node's index in the bh_nodes - * array. - */ -typedef struct bh_nodeidx_entry -{ - bh_node_type key; - int index; /* entry's index within the node array */ - char status; /* hash status */ - uint32 hash; /* hash values (cached) */ -} bh_nodeidx_entry; - -/* Define parameters necessary to generate the hash table interface. */ -#define SH_PREFIX bh_nodeidx -#define SH_ELEMENT_TYPE bh_nodeidx_entry -#define SH_KEY_TYPE bh_node_type -#define SH_SCOPE extern -#ifdef FRONTEND -#define SH_RAW_ALLOCATOR pg_malloc0 -#endif -#define SH_DECLARE -#include "lib/simplehash.h" - /* * binaryheap * @@ -69,19 +46,12 @@ typedef struct binaryheap bool bh_has_heap_property; /* debugging cross-check */ binaryheap_comparator bh_compare; void *bh_arg; - bh_node_type *bh_nodes; - - /* - * If bh_nodeidx is not NULL, the bh_nodeidx is used to track of each - * node's index in bh_nodes. This enables the caller to perform - * binaryheap_remove_node_ptr(), binaryheap_update_up/down in O(log n). - */ - bh_nodeidx_hash *bh_nodeidx; + bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER]; } binaryheap; -extern binaryheap *binaryheap_allocate(int num_nodes, +extern binaryheap *binaryheap_allocate(int capacity, binaryheap_comparator compare, - bool indexed, void *arg); + void *arg); extern void binaryheap_reset(binaryheap *heap); extern void binaryheap_free(binaryheap *heap); extern void binaryheap_add_unordered(binaryheap *heap, bh_node_type d); @@ -90,14 +60,10 @@ extern void binaryheap_add(binaryheap *heap, bh_node_type d); extern bh_node_type binaryheap_first(binaryheap *heap); extern bh_node_type binaryheap_remove_first(binaryheap *heap); extern void binaryheap_remove_node(binaryheap *heap, int n); -extern void binaryheap_remove_node_ptr(binaryheap *heap, bh_node_type d); extern void binaryheap_replace_first(binaryheap *heap, bh_node_type d); -extern void binaryheap_update_up(binaryheap *heap, bh_node_type d); -extern void binaryheap_update_down(binaryheap *heap, bh_node_type d); #define binaryheap_empty(h) ((h)->bh_size == 0) #define binaryheap_size(h) ((h)->bh_size) #define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) -#define binaryheap_indexed(h) ((h)->bh_nodeidx != NULL) #endif /* BINARYHEAP_H */ -- cgit v1.2.3