From 8a2bd21bde1cc87c6ae1364370f59f643b79cf93 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Sun, 19 Aug 2018 19:11:05 +0200 Subject: [PATCH] Heaps: Experiments with Pairing Heaps and Rank Pairing Heaps. --- ucw/Makefile | 3 + ucw/heap-bench-gen.h | 179 ++++++++++++++++ ucw/heap-bench.c | 296 ++++++++++++++++++++++++++ ucw/heap-gen.h | 497 +++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 975 insertions(+) create mode 100644 ucw/heap-bench-gen.h create mode 100644 ucw/heap-bench.c create mode 100644 ucw/heap-gen.h diff --git a/ucw/Makefile b/ucw/Makefile index dfdc9fbe..05fdcbbe 100644 --- a/ucw/Makefile +++ b/ucw/Makefile @@ -189,6 +189,9 @@ TESTS+=$(addprefix $(o)/ucw/,asio.test) $(o)/ucw/asio.test: $(o)/ucw/asio-t endif +$(o)/ucw/heap-bench: $(o)/ucw/heap-bench.o $(LIBUCW) +PROGS+=$(o)/ucw/heap-bench + # The version of autoconf.h that is a part of the public API needs to have # the internal symbols filtered out, so we generate ucw/autoconf.h in the # configure script and let the public config.h refer to diff --git a/ucw/heap-bench-gen.h b/ucw/heap-bench-gen.h new file mode 100644 index 00000000..4b36e5e3 --- /dev/null +++ b/ucw/heap-bench-gen.h @@ -0,0 +1,179 @@ +#define HEAP_PREFIX(x) TEST_PREFIX(x) +#if defined(TEST_WANT_SORT) +# define HEAP_WANT_INSERT +# define HEAP_WANT_DELETE_MIN +#endif +#if defined(TEST_WANT_DIJKSTRA) +# define HEAP_WANT_INSERT +# define HEAP_WANT_DELETE_MIN +# define HEAP_WANT_DECREASE +#endif +#if defined(TEST_WANT_MIX) +# define HEAP_WANT_FIND_MIN +# define HEAP_WANT_INSERT +# define HEAP_WANT_REMOVE +# define HEAP_WANT_DECREASE +# define HEAP_WANT_INCREASE +#endif +struct TEST_PREFIX(heap); +struct TEST_PREFIX(node); +static inline int TEST_PREFIX(less)(struct TEST_PREFIX(heap) *heap, struct TEST_PREFIX(node) *a, struct TEST_PREFIX(node) *b); +#include + +struct TEST_PREFIX(item) { + struct TEST_PREFIX(node) n; + intmax_t key; +}; + +static inline int TEST_PREFIX(less)(struct TEST_PREFIX(heap) *heap UNUSED, struct TEST_PREFIX(node) *a, struct TEST_PREFIX(node) *b) +{ + test.num_cmp++; + return ((struct TEST_PREFIX(item) *)a)->key < ((struct TEST_PREFIX(item) *)b)->key; +} + +#define P(x) TEST_PREFIX(x) + +#if defined(TEST_WANT_SORT) +static void +P(sort)(intmax_t *ary, uint n) +{ + test_init(STRINGIFY_EXPANDED(P(sort))); + struct P(heap) heap; + struct P(item) *items = mp_alloc(test.pool, n * sizeof(*items)); + for (uint i = 0; i < n; i++) + items[i].key = ary[i]; + start_clock(); + P(init)(&heap); + for (uint i = 0; i < n; i++) + P(insert)(&heap, &items[i].n); + for (uint i = 0; i < n; i++) + { + struct P(item) *min = (struct P(item) *)P(delete_min)(&heap); + if (!min) + ASSERT(0); + update_checksum(min->key); + } + if (P(delete_min)(&heap)) + ASSERT(0); + stop_clock(); + test_done(); +} +#endif + +#if defined(TEST_WANT_DIJKSTRA) +static void +P(dijkstra)(struct graph *g, uint start) +{ + test_init(STRINGIFY_EXPANDED(P(dijkstra))); + struct P(heap) heap; + struct P(item) *items = mp_alloc(test.pool, g->n * sizeof(*items)); + for (uint i = 0; i < g->n; i++) + items[i].key = INTMAX_MAX; + items[start].key = 0; + start_clock(); + P(init)(&heap); + for (uint v = 0; v < g->n; v++) + P(insert)(&heap, &items[v].n); + uint num_reachable = 0; + uintmax_t num_decrease = 0; + uintmax_t max_dist = 0; + while (1) + { + struct P(item) *min = (struct P(item) *)P(delete_min)(&heap); + if (!min || min->key == INTMAX_MAX) + break; + num_reachable++; + max_dist = min->key; + update_checksum(min->key); + uint u = min - items; + for (int e = g->v_first_edge[u]; e >= 0; e = g->e_next_edge[e]) + { + uint v = g->e_dest[e]; + intmax_t d = min->key + g->e_weight[e]; + if (d < items[v].key) + { + items[v].key = d; + P(decrease)(&heap, &items[v].n); + num_decrease++; + } + } + } + stop_clock(); + add_note("decrease:%ju reachable:%u max-dist:%ju", num_decrease, num_reachable, max_dist); + test_done(); +} +#endif + +#if defined(TEST_WANT_MIX) +static void +P(mix)(uint n, uint m, uint k) +{ + test_init(STRINGIFY_EXPANDED(P(mix))); + struct eltpool *item_pool = ep_new(sizeof(struct P(item)), 100);; + struct P(item) **item_ary; + GARY_INIT(item_ary, 0); + struct P(heap) heap; + uintmax_t num_insert = 0, num_remove = 0, num_increase = 0, num_decrease = 0; + start_clock(); + P(init)(&heap); + while (m--) + { + if (!GARY_SIZE(item_ary)) + goto force_insert; + uint ins_rem_prob = 20; + uint ins_prob; + if (GARY_SIZE(item_ary) < n) + ins_prob = ins_rem_prob / 4 * 3; + else + ins_prob = ins_rem_prob / 4; + int r = random_max(100); + if ((r -= ins_prob) < 0) + { +force_insert: + num_insert++; + struct P(item) *item = ep_alloc(item_pool); + item->key = random_max(k); + *GARY_PUSH(item_ary) = item; + P(insert)(&heap, &item->n); + } + else + { + uint i = random_max(GARY_SIZE(item_ary)); + struct P(item) *item = item_ary[i]; + if ((r -= ins_rem_prob - ins_prob) < 0) + { + num_remove++; + item_ary[i] = item_ary[GARY_SIZE(item_ary) - 1]; + GARY_POP(item_ary); + P(remove)(&heap, &item->n); + ep_free(item_pool, item); + } + else if ((r -= (100 - ins_rem_prob) / 2) < 0) + { + num_decrease++; + item->key -= (int)random_max(k / 10 + 1) + 1; + P(decrease)(&heap, &item->n); + } + else + { + num_increase++; + item->key += (int)random_max(k / 10 + 1) + 1; + P(increase)(&heap, &item->n); + } + } + struct P(item) *min = (struct P(item) *)P(find_min)(&heap); + update_checksum(min ? min->key : INTMAX_MIN); + } + stop_clock(); + GARY_FREE(item_ary); + ep_delete(item_pool); + add_note("insert:%ju remove:%ju decrease:%ju increase:%ju", num_insert, num_remove, num_decrease, num_increase); + test_done(); +} +#endif + +#undef TEST_PREFIX +#undef TEST_WANT_SORT +#undef TEST_WANT_DIJKSTRA +#undef TEST_WANT_MIX +#undef P diff --git a/ucw/heap-bench.c b/ucw/heap-bench.c new file mode 100644 index 00000000..0b2264ca --- /dev/null +++ b/ucw/heap-bench.c @@ -0,0 +1,296 @@ +/* + * Tests & benchmarks of various heap data structures + * + * (c) 2018 Pavel Charvat + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +static int o_seed; + +static int o_heap_pairing_noparent; +static int o_heap_pairing; +static int o_heap_rank_pairing_noparent; +static int o_heap_rank_pairing_type1; +static int o_heap_rank_pairing_type2; + +static int o_test_type = -1; +enum test_type { + TT_RANDOM_SORT, + TT_RANDOM_DIJKSTRA, + TT_RANDOM_MIX, +}; + +static uint o_n, o_m, o_k; + +static struct test { + struct mempool *pool; + const char *name; + timestamp_t timer; + uint time; + uint checksum; + uintmax_t num_cmp; + clist notes; +} test; + +static void test_init(const char *name) +{ + ASSERT(!test.pool); + bzero(&test, sizeof(test)); + test.pool = mp_new(4096); + test.name = name; + clist_init(&test.notes); + srand(o_seed); +} + +static inline void update_checksum(uintmax_t val) +{ + test.checksum = (test.checksum + val + 17) * 1125899906842597UL; +} + +static void FORMAT_CHECK(printf,1,2) add_note(const char *fmt, ...) +{ + va_list va; + va_start(va, fmt); + simp_append(test.pool, &test.notes)->s = mp_vprintf(test.pool, fmt, va); + va_end(va); +} + +static void start_clock(void) +{ + init_timer(&test.timer); +} + +static void stop_clock(void) +{ + test.time += get_timer(&test.timer); +} + +static void test_done(void) +{ + char *notes = mp_printf(test.pool, "sec:%0.3f csum:0x%x cmp:%ju", 0.001 * test.time, test.checksum, test.num_cmp); + CLIST_FOR_EACH(simp_node *, n, test.notes) + notes = mp_printf_append(test.pool, notes, " %s", n->s); + msg(L_INFO, "TEST[%s] -> %s", test.name, notes); + mp_delete(test.pool); + test.pool = NULL; +} + +struct graph { + uint n, m; + int *v_first_edge; + int *e_next_edge; + uint *e_dest; + uint *e_weight; +}; + +static struct graph *generate_random_graph(uint n, uint m, uint w_min, uint w_max) +{ + struct graph *g = xmalloc_zero(sizeof(*g)); + g->n = n; + g->m = m; + g->v_first_edge = xmalloc(n * sizeof(*g->v_first_edge)); + g->e_next_edge = xmalloc(m * sizeof(*g->e_next_edge)); + g->e_dest = xmalloc(m * sizeof(*g->e_dest)); + g->e_weight = xmalloc(m * sizeof(*g->e_weight)); + for (uint v = 0; v < n; v++) + g->v_first_edge[v] = -1; + for (uint e = 0; e < m; e++) + { + uint u = random_max(n); + uint v = random_max(n); + g->e_next_edge[e] = g->v_first_edge[u]; + g->v_first_edge[u] = e; + g->e_dest[e] = v; + g->e_weight[e] = w_min + random_max(w_max - w_min + 1); + } + return g; +} + +static void free_graph(struct graph *g) +{ + xfree(g->v_first_edge); + xfree(g->e_next_edge); + xfree(g->e_dest); + xfree(g->e_weight); + xfree(g); +} + +#define TEST_PREFIX(x) pairing_noparent_##x +#define HEAP_PAIRING +#define TEST_WANT_SORT +#include + +#define TEST_PREFIX(x) pairing_##x +#define HEAP_PAIRING +#define TEST_WANT_SORT +#define TEST_WANT_DIJKSTRA +#define TEST_WANT_MIX +#include + +#define TEST_PREFIX(x) rank_pairing_noparent_##x +#define HEAP_RANK_PAIRING +#define HEAP_RANK_PAIRING_TYPE1 +#define TEST_WANT_SORT +#include + +#define TEST_PREFIX(x) rank_pairing_type1_##x +#define HEAP_RANK_PAIRING +#define HEAP_RANK_PAIRING_TYPE1 +#define TEST_WANT_SORT +#define TEST_WANT_DIJKSTRA +#define TEST_WANT_MIX +#include + +#define TEST_PREFIX(x) rank_pairing_type2_##x +#define HEAP_RANK_PAIRING +#define HEAP_RANK_PAIRING_TYPE2 +#define TEST_WANT_SORT +#define TEST_WANT_DIJKSTRA +#define TEST_WANT_MIX +#include + +static void FORMAT_CHECK(printf,1,2) test_start(const char *fmt, ...) +{ + msg(L_INFO, " "); + va_list va; + va_start(va, fmt); + vmsg(L_INFO, fmt, va); + va_end(va); + srand(o_seed + 12345); +} + +static void test_random_sort(uint n, uint k) +{ + test_start("Testing randomized sort, n=%u k=%u", n, k); + + uintmax_t *ary = xmalloc(n * sizeof(*ary)); + for (uint i = 0; i < n; i++) + ary[i] = random_max(n); + + if (o_heap_pairing_noparent) + pairing_noparent_sort(ary, n); + if (o_heap_pairing) + pairing_sort(ary, n); + if (o_heap_rank_pairing_noparent) + rank_pairing_noparent_sort(ary, n); + if (o_heap_rank_pairing_type1) + rank_pairing_type1_sort(ary, n); + if (o_heap_rank_pairing_type2) + rank_pairing_type2_sort(ary, n); + + xfree(ary); +} + +static void test_random_dijkstra(uint n, uint m, uint k) +{ + test_start("Testing randomized dijkstra, n=%u m=%u k=%u", n, m, k); + + ASSERT(k); + struct graph *g = generate_random_graph(n, m, 1, k); + uint start = random_max(g->n); + + if (o_heap_pairing) + pairing_dijkstra(g, start); + if (o_heap_rank_pairing_type1) + rank_pairing_type1_dijkstra(g, start); + if (o_heap_rank_pairing_type2) + rank_pairing_type2_dijkstra(g, start); + + free_graph(g); +} + +static void test_random_mix(uint n, uint m, uint k) +{ + test_start("Testing randomized mix, n=%u m=%u k=%u", n, m, k); + + if (o_heap_pairing) + pairing_mix(n, m, k); + if (o_heap_rank_pairing_type1) + rank_pairing_type1_mix(n, m, k); + if (o_heap_rank_pairing_type2) + rank_pairing_type2_mix(n, m, k); +} + +static struct opt_section options = { + OPT_ITEMS { + OPT_HELP("Usage: heap-bench [] [] []"), + OPT_HELP(""), + OPT_HELP("Options:"), + OPT_HELP_OPTION, + OPT_INT('r', "random-seed", o_seed, OPT_REQUIRED_VALUE, "\tUse this random seed (default: generate one)"), + OPT_HELP(""), + OPT_HELP("Heap types (default: compare all of them):"), + OPT_BOOL(0, "pairing-noparent", o_heap_pairing_noparent, 0, "\tPairing heaps with no parent pointers (without Decrease, etc.)"), + OPT_BOOL(0, "pairing", o_heap_pairing, 0, "\tPairing heaps"), + OPT_BOOL(0, "rank-pairing-noparent", o_heap_rank_pairing_noparent, 0, "\tRank pairing heaps with no parent pointers (without Decrease, etc.)"), + OPT_BOOL(0, "rank-pairing-type1", o_heap_rank_pairing_type1, 0, "\tType 1 of rank pairing heaps"), + OPT_BOOL(0, "rank-pairing-type2", o_heap_rank_pairing_type2, 0, "\tType 2 of rank pairing heaps"), + OPT_HELP(""), + OPT_HELP("Test type (default: a mix of various tests):"), + OPT_SWITCH(0, "random-sort", o_test_type, TT_RANDOM_SORT, 0, "\tSort a random sequence (options: -n, -k)"), + OPT_SWITCH(0, "random-dijkstra", o_test_type, TT_RANDOM_DIJKSTRA, 0, "\tFind all nearest paths from a vertex in random graph (options: -n, -e, -k)"), + OPT_SWITCH(0, "random-mix", o_test_type, TT_RANDOM_MIX, 0, "\tRandomized mix of Insert, Remove, Decrease, Increase (options: -n, -e, -k)"), + OPT_UINT('n', NULL, o_n, OPT_REQUIRED_VALUE, NULL), + OPT_UINT('m', NULL, o_m, OPT_REQUIRED_VALUE, NULL), + OPT_UINT('k', NULL, o_k, OPT_REQUIRED_VALUE, NULL), + OPT_END + } +}; + +int main(int argc UNUSED, char **argv) +{ + o_seed = (u16)(hash_u32(getpid()) ^ get_timestamp()); + opt_parse(&options, argv + 1); + + msg(L_DEBUG, "Using random seed %u", o_seed); + + if (1 + && !o_heap_pairing_noparent + && !o_heap_pairing + && !o_heap_rank_pairing_noparent + && !o_heap_rank_pairing_type1 + && !o_heap_rank_pairing_type2 + ) + { + o_heap_pairing_noparent = 1; + o_heap_pairing = 1; + o_heap_rank_pairing_noparent = 1; + o_heap_rank_pairing_type1 = 1; + o_heap_rank_pairing_type2 = 1; + } + + switch (o_test_type) + { + case TT_RANDOM_SORT: + test_random_sort(o_n ? : 1000000, o_k ? : 1000000000); + break; + + case TT_RANDOM_DIJKSTRA: + test_random_dijkstra(o_n ? : 300000, o_m ? : 3000000, o_k ? : 1000); + break; + + case TT_RANDOM_MIX: + test_random_mix(o_n ? : 300000, o_m ? : 5000000, o_k ? : 10000); + break; + + default: + test_random_sort(1000000, 1000000000); + test_random_sort(1000000, 1000); + test_random_dijkstra(300000, 3000000, 1000); + test_random_mix(300000, 5000000, 10000); + break; + } + + return 0; +} diff --git a/ucw/heap-gen.h b/ucw/heap-gen.h new file mode 100644 index 00000000..9b487cbb --- /dev/null +++ b/ucw/heap-gen.h @@ -0,0 +1,497 @@ +/* + * UCW Library -- Heap Data Structures: Code generator + * + * (c) 2018 Pavel Charvat + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + * + * + * References: + * + * [1] Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert E. Tarjan, + * The pairing heap: A new form of self-adjusting heap, + * Algorithmica, 1(1–4):111–129, 1986. + * + * [2] Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan, + * Rank-Pairing Heaps, + * SIAM J. Computing, 40(6):1463–1485, 2011. + * + * [3] Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan, + * A Back-to-Basics Empirical Study of Priority Queues, + * 2014. + */ + +#define P(x) HEAP_PREFIX(x) + +#if defined(HEAP_PAIRING) +# if defined(HEAP_WANT_REPLACE) +# define HEAP_WANT_REMOVE +# define HEAP_WANT_INSERT +# endif +# if defined(HEAP_WANT_REMOVE) || defined(HEAP_WANT_DECREASE) +# define HEAP_NODE_STORE_PARENT +# endif + +#elif defined(HEAP_RANK_PAIRING) +# if !defined(HEAP_RANK_PAIRING_TYPE1) && !defined(HEAP_RANK_PAIRING_TYPE2) +# define HEAP_RANK_PAIRING_TYPE1 +# endif +# if defined(HEAP_WANT_INCREASE) || defined(HEAP_WANT_REPLACE) +# define HEAP_WANT_REMOVE +# define HEAP_WANT_INSERT +# endif +# define HEAP_NODE_STORE_RANK +# if defined(HEAP_WANT_REMOVE) || defined(HEAP_WANT_DECREASE) +# define HEAP_NODE_STORE_PARENT +# endif + +#else +# error Missing heap type +#endif + +typedef struct P(heap) *P(heap_p); +typedef struct P(node) *P(node_p); + +struct P(heap) { + P(node_p) root; +}; + +struct P(node) { + P(node_p) left, right; +#if defined(HEAP_NODE_STORE_PARENT) + P(node_p) parent; +#endif +#if defined(HEAP_NODE_STORE_RANK) + byte rank; +#endif +}; + +static inline void +P(init)(P(heap_p) h) +{ + h->root = NULL; +} + +// @a and @b must be non-NULL roots of two half-trees, function merges them and returns new half-tree. +// @parent and @right pointers in @a and @b can be undefined, but in resulting root they are not automatically cleared. +static inline P(node_p) +P(link)(P(heap_p) h, P(node_p) a, P(node_p) b) +{ + P(node_p) c; + if (P(less)(h, b, a)) + { + c = a; + a = b; + b = c; + } + c = a->left; + a->left = b; + b->right = c; +#if defined(HEAP_NODE_STORE_PARENT) + b->parent = a; + if (c) + c->parent = b; +#endif +#if defined(HEAP_NODE_STORE_RANK) + // "a->rank++" would not work for rank pairing heaps + a->rank = b->rank + 1; +#endif + return a; +} + +#if defined(HEAP_PAIRING) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE) || defined(HEAP_WANT_INCREASE)) +// Merges list of half-trees (from decomposed right spine of a half-tree) into one half-tree, +// using the two-pass pairing algorithm. Empty list is also supported. +static P(node_p) +P(two_pass)(P(heap_p) h, P(node_p) a) +{ + if (!a) + return NULL; + + // First pass: Merge pairs of trees from left to right and create a link list of them + P(node_p) l = NULL, b, c; + do + { + b = a->right; + if (!b) + c = NULL; + else + { + c = b->right; + a = P(link)(h, a, b); + } + a->right = l; + l = a; + } + while (a = c); + + // Second pass: Merge all trees in the link list from right to left + a = l; + l = l->right; + while (l) + { + b = l; + l = l->right; + a = P(link)(h, a, b); + } + + // Fix undefined pointers in the new root + a->right = NULL; +#if defined(HEAP_NODE_STORE_PARENT) + a->parent = NULL; +#endif + return a; +} +#endif + +#if defined(HEAP_NODE_STORE_PARENT) +// Removes @x from a right spine. @x must not be root. Does not update @parent and @right pointers of @x. +static inline void +P(cut_from_spine)(P(node_p) a) +{ + if (a->parent->left == a) + a->parent->left = a->right; + else + a->parent->right = a->right; + if (a->right) + a->right->parent = a->parent; +} +#endif + +#if defined(HEAP_RANK_PAIRING) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE)) +static void +P(cut_root_and_consolidate)(P(heap_p) h, P(node_p) a) +{ + P(node_p) min = NULL; + P(node_p) list, *list_tail = &list; + P(node_p) bucket[32]; + byte bucket_ary[32]; + byte bucket_count = 0; + uint bucket_mask = 0; + + // We are going to execute very similar code for two lists in a short loop: + // 1) The right spine of root->left + // 2) Remaining heap's half-trees except the deleted root + P(node_p) x = a->left, stop = NULL; + while (1) + { + while (x != stop) + { + P(node_p) next = x->right; + if (!(bucket_mask & (1U << x->rank))) + { + bucket_mask |= 1U << x->rank; + bucket_ary[bucket_count++] = x->rank; + bucket[x->rank] = x; + } + else if (!bucket[x->rank]) + { + bucket[x->rank] = x; + } + else + { + P(node_p) y = bucket[x->rank]; + bucket[x->rank] = NULL; + x = P(link)(h, y, x); + *list_tail = x; + list_tail = &x->right; +#if defined(HEAP_NODE_STORE_PARENT) + x->parent = NULL; +#endif + if (!min || P(less)(h, x, min)) + min = x; + } + x = next; + } + if (stop) + break; + stop = a; + x = a->right; + } + + // Process remaining unpaired half-trees in buckets + for (byte i = 0; i < bucket_count; i++) + { + P(node_p) x = bucket[bucket_ary[i]]; + if (!x) + continue; + *list_tail = x; + list_tail = &x->right; +#if defined(HEAP_NODE_STORE_PARENT) + x->parent = NULL; +#endif + if (!min || P(less)(h, x, min)) + min = x; + } + + // Close the resulting list of half-trees and update minimum + *list_tail = list; // list can be undefined here for an empty list, but it's OK + h->root = min; +} +#endif + +#if defined(HEAP_RANK_PAIRING) && (defined(HEAP_WANT_DECREASE) || defined(HEAP_WANT_REMOVE)) +static void +P(cut_from_spine_and_update_ranks)(P(node_p) a) +{ + P(node_p) x = a->parent, y = a->right; + if (x->left == a) + x->left = y; + else + x->right = y; + s8 rank = -1; + if (y) + { + y->parent = x; + rank = y->rank; + } + while (1) + { + P(node_p) z = x->parent; + if (!z) + { + x->rank = rank + 1; + break; + } +#if defined(HEAP_RANK_PAIRING_TYPE1) + if (!x->left || !x->right) + rank++; + else if (x->left->rank == x->right->rank) + rank = x->left->rank + 1; + else if (x->left->rank > x->right->rank) + rank = x->left->rank; + else + rank = x->right->rank; +#else + if (!x->left || !x->right) + rank = rank > 0 ? rank : rank + 1; + else if (x->left->rank >= x->right->rank) + rank = x->left->rank + (x->left->rank - x->right->rank <= 1); + else + rank = x->right->rank + (x->right->rank - x->left->rank <= 1); +#endif + if (x->rank <= (byte)rank) + break; + x->rank = (byte)rank; + y = x; + x = z; + } +} +#endif + +#if defined(HEAP_WANT_EMPTY) +static inline bool +P(empty)(P(heap_p) h) +{ + return h->root != NULL; +} +#endif + +#if defined(HEAP_WANT_FIND_MIN) +static inline P(node_p) +P(find_min)(P(heap_p) h) +{ + return h->root; +} +#endif + +#if defined(HEAP_WANT_INSERT) +static void +P(insert)(P(heap_p) h, P(node_p) a) +{ +#if defined(HEAP_PAIRING) + a->left = a->right = NULL; +#if defined(HEAP_NODE_STORE_PARENT) + a->parent = NULL; +#endif + h->root = h->root ? P(link)(h, h->root, a) : a; + +#elif defined(HEAP_RANK_PAIRING) + a->left = NULL; +#if defined(HEAP_NODE_STORE_PARENT) + a->parent = NULL; +#endif +#if defined(HEAP_NODE_STORE_RANK) + a->rank = 0; +#endif + P(node_p) b = h->root; + if (!b) + { + a->right = a; + h->root = a; + } + else + { + a->right = b->right; + b->right = a; + if (P(less)(h, a, b)) + h->root = a; + } +#else +# error HEAP_WANT_INSERT is not supported for this heap type +#endif +} +#endif + +#if defined(HEAP_WANT_MERGE) +static void +P(merge)(P(heap_p) h, P(heap_p) g) +{ + P(node_p) a = g->root; + if (!g) + return; + g->root = NULL; +#if defined(HEAP_PAIRING) + h->root = h->root ? P(link)(h, h->root, a) : a; +#elif defined(HEAP_RANK_PAIRING) + P(node_p) b = h->root; + if (!b) + h->root = a; + else + { + P(node_p) c = a->right; + a->right = b->right; + b->right = c; + if (P(less)(h, a, b)) + h->root = a; + } +#else +# error HEAP_WANT_MERGE is not supported for this heap type +#endif +} +#endif + +#if defined(HEAP_WANT_DELETE_MIN) +static P(node_p) +P(delete_min)(P(heap_p) h) +{ + P(node_p) a = h->root; + if (!a) + return NULL; +#if defined(HEAP_PAIRING) + h->root = P(two_pass)(h, a->left); +#elif defined(HEAP_RANK_PAIRING) + P(cut_root_and_consolidate)(h, a); +#else +# error HEAP_WANT_DELETE_MIN is not supported for this heap type +#endif + return a; +} +#endif + +#if defined(HEAP_WANT_REMOVE) +static void +P(remove)(P(heap_p) h, P(node_p) a) +{ +#if defined(HEAP_PAIRING) + P(node_p) b = P(two_pass)(h, a->left); + if (!a->parent) + { + h->root = b; + return; + } + P(cut_from_spine)(a); + if (b) + h->root = P(link)(h, h->root, b); +#elif defined(HEAP_RANK_PAIRING) + // Move @x to a root by emulating decrease; we don't need to update heap->root yet + if (a->parent) + { + P(cut_from_spine_and_update_ranks)(a); + a->parent = NULL; + a->right = h->root->right; + h->root->right = a; + } + P(cut_root_and_consolidate)(h, a); +#else +# error HEAP_WANT_REMOVE is not supported for this heap type +#endif +} +#endif + +#if defined(HEAP_WANT_DECREASE) +static void +P(decrease)(P(heap_p) h, P(node_p) a) +{ +#if defined(HEAP_PAIRING) + if (!a->parent) + return; + P(cut_from_spine)(a); + a->parent = a->right = NULL; + h->root = P(link)(h, h->root, a); +#elif defined(HEAP_RANK_PAIRING) + if (!a->parent) + { + if (a == h->root) + return; + } + else + { + P(cut_from_spine_and_update_ranks)(a); + a->rank = a->left ? a->left->rank + 1 : 0; + a->parent = NULL; + a->right = h->root->right; + h->root->right = a; + } + if (P(less)(h, a, h->root)) + h->root = a; +#else +# error HEAP_WANT_DECREASE is not supported for this heap type +#endif +} +#endif + +#if defined(HEAP_WANT_INCREASE) +static void +P(increase)(P(heap_p) h, P(node_p) a) +{ +#if defined(HEAP_PAIRING) + if (!a->left) + return; + P(node_p) b = P(two_pass)(h, a->left); + a->left = NULL; + h->root = P(link)(h, h->root, b); +#elif defined(HEAP_RANK_PAIRING) + // FIXME: Optimize? + P(remove)(h, a); + P(insert)(h, a); +#else +# error HEAP_WANT_INCREASE is not supported for this heap type +#endif +} +#endif + +#if defined(HEAP_WANT_REPLACE) +static void +P(replace)(P(heap_p) h, P(node_p) a) +{ +#if defined(HEAP_PAIRING) || defined(HEAP_RANK_PAIRING) + P(remove)(h, a); + P(insert)(h, a); +#else +# error HEAP_WANT_REPLACE is not supported for this heap type +#endif +} +#endif + +#undef HEAP_PREFIX + +#undef HEAP_PAIRING +#undef HEAP_RANK_PAIRING +#undef HEAP_RANK_PAIRING_TYPE1 +#undef HEAP_RANK_PAIRING_TYPE2 + +#undef HEAP_WANT_EMPTY +#undef HEAP_WANT_FIND_MIN +#undef HEAP_WANT_INSERT +#undef HEAP_WANT_MERGE +#undef HEAP_WANT_DELETE_MIN +#undef HEAP_WANT_REMOVE +#undef HEAP_WANT_DECREASE +#undef HEAP_WANT_INCREASE +#undef HEAP_WANT_REPLACE + +#undef P +#undef HEAP_NODE_STORE_PARENT +#undef HEAP_NODE_STORE_RANK -- 2.39.2