* [PATCH 1/3] salad: make heap struct more friendly to use
2019-02-22 11:38 [PATCH 0/3] Make heap API more friendly Vladislav Shpilevoy
@ 2019-02-22 11:38 ` Vladislav Shpilevoy
2019-02-22 18:26 ` [tarantool-patches] " Konstantin Osipov
2019-02-22 11:38 ` [PATCH 2/3] salad: do not touch struct heap_node.pos in user's code Vladislav Shpilevoy
2019-02-22 11:39 ` [PATCH 3/3] salad: fix heap reserve() behaviour Vladislav Shpilevoy
2 siblings, 1 reply; 9+ messages in thread
From: Vladislav Shpilevoy @ 2019-02-22 11:38 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
Now heap API works with struct heap_node only, which forces a
user to constantly call container_of. Such a code looks really
awful. This commit makes heap taking and returning user defined
structures, and removes container_of clue.
It is worth noting, that the similar API rb-tree and b-tree
have. Even rlist has its rlist_*_entry() wrappers, and mhash
provides macroses to define your own value type.
---
src/box/vy_lsm.c | 9 ++-
src/box/vy_range.h | 6 +-
src/box/vy_scheduler.c | 67 ++++++++-------------
src/box/vy_write_iterator.c | 49 +++++++--------
src/lib/salad/heap.h | 115 ++++++++++++++++++++++--------------
test/unit/heap.c | 76 ++++++++++--------------
test/unit/heap_iterator.c | 67 ++++++++-------------
7 files changed, 180 insertions(+), 209 deletions(-)
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 1b59e4364..57f5a7a29 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -673,10 +673,9 @@ vy_lsm_generation(struct vy_lsm *lsm)
int
vy_lsm_compaction_priority(struct vy_lsm *lsm)
{
- struct heap_node *n = vy_range_heap_top(&lsm->range_heap);
- if (n == NULL)
+ struct vy_range *range = vy_range_heap_top(&lsm->range_heap);
+ if (range == NULL)
return 0;
- struct vy_range *range = container_of(n, struct vy_range, heap_node);
return range->compaction_priority;
}
@@ -766,7 +765,7 @@ void
vy_lsm_add_range(struct vy_lsm *lsm, struct vy_range *range)
{
assert(range->heap_node.pos == UINT32_MAX);
- vy_range_heap_insert(&lsm->range_heap, &range->heap_node);
+ vy_range_heap_insert(&lsm->range_heap, range);
vy_range_tree_insert(&lsm->range_tree, range);
lsm->range_count++;
}
@@ -775,7 +774,7 @@ void
vy_lsm_remove_range(struct vy_lsm *lsm, struct vy_range *range)
{
assert(range->heap_node.pos != UINT32_MAX);
- vy_range_heap_delete(&lsm->range_heap, &range->heap_node);
+ vy_range_heap_delete(&lsm->range_heap, range);
vy_range_tree_remove(&lsm->range_tree, range);
lsm->range_count--;
}
diff --git a/src/box/vy_range.h b/src/box/vy_range.h
index 0c068c0ab..facd2ac01 100644
--- a/src/box/vy_range.h
+++ b/src/box/vy_range.h
@@ -141,13 +141,13 @@ struct vy_range {
*/
#define HEAP_NAME vy_range_heap
static inline bool
-vy_range_heap_less(struct heap_node *a, struct heap_node *b)
+vy_range_heap_less(struct vy_range *r1, struct vy_range *r2)
{
- struct vy_range *r1 = container_of(a, struct vy_range, heap_node);
- struct vy_range *r2 = container_of(b, struct vy_range, heap_node);
return r1->compaction_priority > r2->compaction_priority;
}
#define HEAP_LESS(h, l, r) vy_range_heap_less(l, r)
+#define heap_value_t struct vy_range
+#define heap_value_attr heap_node
#include "salad/heap.h"
#undef HEAP_LESS
#undef HEAP_NAME
diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
index f0e47fcee..073c2c7cf 100644
--- a/src/box/vy_scheduler.c
+++ b/src/box/vy_scheduler.c
@@ -278,11 +278,8 @@ vy_task_delete(struct vy_task *task)
}
static bool
-vy_dump_heap_less(struct heap_node *a, struct heap_node *b)
+vy_dump_heap_less(struct vy_lsm *i1, struct vy_lsm *i2)
{
- struct vy_lsm *i1 = container_of(a, struct vy_lsm, in_dump);
- struct vy_lsm *i2 = container_of(b, struct vy_lsm, in_dump);
-
/*
* LSM trees that are currently being dumped or can't be
* scheduled for dump right now are moved off the top of
@@ -311,17 +308,14 @@ vy_dump_heap_less(struct heap_node *a, struct heap_node *b)
#define HEAP_NAME vy_dump_heap
#define HEAP_LESS(h, l, r) vy_dump_heap_less(l, r)
+#define heap_value_t struct vy_lsm
+#define heap_value_attr in_dump
#include "salad/heap.h"
-#undef HEAP_LESS
-#undef HEAP_NAME
-
static bool
-vy_compaction_heap_less(struct heap_node *a, struct heap_node *b)
+vy_compaction_heap_less(struct vy_lsm *i1, struct vy_lsm *i2)
{
- struct vy_lsm *i1 = container_of(a, struct vy_lsm, in_compaction);
- struct vy_lsm *i2 = container_of(b, struct vy_lsm, in_compaction);
/*
* Prefer LSM trees whose read amplification will be reduced
* most as a result of compaction.
@@ -331,12 +325,11 @@ vy_compaction_heap_less(struct heap_node *a, struct heap_node *b)
#define HEAP_NAME vy_compaction_heap
#define HEAP_LESS(h, l, r) vy_compaction_heap_less(l, r)
+#define heap_value_t struct vy_lsm
+#define heap_value_attr in_compaction
#include "salad/heap.h"
-#undef HEAP_LESS
-#undef HEAP_NAME
-
static void
vy_worker_pool_start(struct vy_worker_pool *pool)
{
@@ -523,9 +516,8 @@ vy_scheduler_add_lsm(struct vy_scheduler *scheduler, struct vy_lsm *lsm)
assert(!lsm->is_dropped);
assert(lsm->in_dump.pos == UINT32_MAX);
assert(lsm->in_compaction.pos == UINT32_MAX);
- vy_dump_heap_insert(&scheduler->dump_heap, &lsm->in_dump);
- vy_compaction_heap_insert(&scheduler->compaction_heap,
- &lsm->in_compaction);
+ vy_dump_heap_insert(&scheduler->dump_heap, lsm);
+ vy_compaction_heap_insert(&scheduler->compaction_heap, lsm);
}
void
@@ -534,9 +526,8 @@ vy_scheduler_remove_lsm(struct vy_scheduler *scheduler, struct vy_lsm *lsm)
assert(!lsm->is_dropped);
assert(lsm->in_dump.pos != UINT32_MAX);
assert(lsm->in_compaction.pos != UINT32_MAX);
- vy_dump_heap_delete(&scheduler->dump_heap, &lsm->in_dump);
- vy_compaction_heap_delete(&scheduler->compaction_heap,
- &lsm->in_compaction);
+ vy_dump_heap_delete(&scheduler->dump_heap, lsm);
+ vy_compaction_heap_delete(&scheduler->compaction_heap, lsm);
lsm->in_dump.pos = UINT32_MAX;
lsm->in_compaction.pos = UINT32_MAX;
}
@@ -552,9 +543,8 @@ vy_scheduler_update_lsm(struct vy_scheduler *scheduler, struct vy_lsm *lsm)
}
assert(lsm->in_dump.pos != UINT32_MAX);
assert(lsm->in_compaction.pos != UINT32_MAX);
- vy_dump_heap_update(&scheduler->dump_heap, &lsm->in_dump);
- vy_compaction_heap_update(&scheduler->compaction_heap,
- &lsm->in_compaction);
+ vy_dump_heap_update(&scheduler->dump_heap, lsm);
+ vy_compaction_heap_update(&scheduler->compaction_heap, lsm);
}
static void
@@ -653,11 +643,9 @@ vy_scheduler_complete_dump(struct vy_scheduler *scheduler)
}
int64_t min_generation = scheduler->generation;
- struct heap_node *pn = vy_dump_heap_top(&scheduler->dump_heap);
- if (pn != NULL) {
- struct vy_lsm *lsm = container_of(pn, struct vy_lsm, in_dump);
+ struct vy_lsm *lsm = vy_dump_heap_top(&scheduler->dump_heap);
+ if (lsm != NULL)
min_generation = vy_lsm_generation(lsm);
- }
if (min_generation == scheduler->dump_generation) {
/*
* There are still LSM trees that must be dumped
@@ -1614,7 +1602,7 @@ vy_task_compaction_complete(struct vy_task *task)
task->wi->iface->close(task->wi);
assert(range->heap_node.pos == UINT32_MAX);
- vy_range_heap_insert(&lsm->range_heap, &range->heap_node);
+ vy_range_heap_insert(&lsm->range_heap, range);
vy_scheduler_update_lsm(scheduler, lsm);
say_info("%s: completed compacting range %s",
@@ -1646,7 +1634,7 @@ vy_task_compaction_abort(struct vy_task *task)
vy_run_discard(task->new_run);
assert(range->heap_node.pos == UINT32_MAX);
- vy_range_heap_insert(&lsm->range_heap, &range->heap_node);
+ vy_range_heap_insert(&lsm->range_heap, range);
vy_scheduler_update_lsm(scheduler, lsm);
}
@@ -1659,15 +1647,10 @@ vy_task_compaction_new(struct vy_scheduler *scheduler, struct vy_worker *worker,
.complete = vy_task_compaction_complete,
.abort = vy_task_compaction_abort,
};
-
- struct heap_node *range_node;
- struct vy_range *range;
-
assert(!lsm->is_dropped);
- range_node = vy_range_heap_top(&lsm->range_heap);
- assert(range_node != NULL);
- range = container_of(range_node, struct vy_range, heap_node);
+ struct vy_range *range = vy_range_heap_top(&lsm->range_heap);
+ assert(range != NULL);
assert(range->compaction_priority > 1);
if (vy_lsm_split_range(lsm, range) ||
@@ -1738,8 +1721,8 @@ vy_task_compaction_new(struct vy_scheduler *scheduler, struct vy_worker *worker,
* Remove the range we are going to compact from the heap
* so that it doesn't get selected again.
*/
- vy_range_heap_delete(&lsm->range_heap, range_node);
- range_node->pos = UINT32_MAX;
+ vy_range_heap_delete(&lsm->range_heap, range);
+ range->heap_node.pos = UINT32_MAX;
vy_scheduler_update_lsm(scheduler, lsm);
say_info("%s: started compacting range %s, runs %d/%d",
@@ -1858,8 +1841,8 @@ retry:
/*
* Look up the oldest LSM tree eligible for dump.
*/
- struct heap_node *pn = vy_dump_heap_top(&scheduler->dump_heap);
- if (pn == NULL) {
+ struct vy_lsm *lsm = vy_dump_heap_top(&scheduler->dump_heap);
+ if (lsm == NULL) {
/*
* There is no LSM tree and so no task to schedule.
* Complete the current dump round.
@@ -1867,7 +1850,6 @@ retry:
vy_scheduler_complete_dump(scheduler);
goto no_task;
}
- struct vy_lsm *lsm = container_of(pn, struct vy_lsm, in_dump);
if (!lsm->is_dumping && lsm->pin_count == 0 &&
vy_lsm_generation(lsm) == scheduler->dump_generation) {
/*
@@ -1924,10 +1906,9 @@ vy_scheduler_peek_compaction(struct vy_scheduler *scheduler,
struct vy_worker *worker = NULL;
retry:
*ptask = NULL;
- struct heap_node *pn = vy_compaction_heap_top(&scheduler->compaction_heap);
- if (pn == NULL)
+ struct vy_lsm *lsm = vy_compaction_heap_top(&scheduler->compaction_heap);
+ if (lsm == NULL)
goto no_task; /* nothing to do */
- struct vy_lsm *lsm = container_of(pn, struct vy_lsm, in_compaction);
if (vy_lsm_compaction_priority(lsm) <= 1)
goto no_task; /* nothing to do */
if (worker == NULL) {
diff --git a/src/box/vy_write_iterator.c b/src/box/vy_write_iterator.c
index 7a6a20627..365b44bbf 100644
--- a/src/box/vy_write_iterator.c
+++ b/src/box/vy_write_iterator.c
@@ -37,13 +37,6 @@
#define HEAP_FORWARD_DECLARATION
#include "salad/heap.h"
-static bool
-heap_less(heap_t *heap, struct heap_node *n1, struct heap_node *n2);
-
-#define HEAP_NAME vy_source_heap
-#define HEAP_LESS heap_less
-#include "salad/heap.h"
-
/**
* Merge source of a write iterator. Represents a mem or a run.
*/
@@ -73,6 +66,15 @@ struct vy_write_src {
};
};
+static bool
+heap_less(heap_t *heap, struct vy_write_src *src1, struct vy_write_src *src2);
+
+#define HEAP_NAME vy_source_heap
+#define HEAP_LESS heap_less
+#define heap_value_t struct vy_write_src
+#define heap_value_attr heap_node
+#include "salad/heap.h"
+
/**
* A sequence of versions of a key, sorted by LSN in ascending order.
* (history->tuple.lsn < history->next->tuple.lsn).
@@ -218,14 +220,10 @@ struct vy_write_iterator {
* it's a virtual source (is_end_of_key).
*/
static bool
-heap_less(heap_t *heap, struct heap_node *node1, struct heap_node *node2)
+heap_less(heap_t *heap, struct vy_write_src *src1, struct vy_write_src *src2)
{
struct vy_write_iterator *stream =
container_of(heap, struct vy_write_iterator, src_heap);
- struct vy_write_src *src1 =
- container_of(node1, struct vy_write_src, heap_node);
- struct vy_write_src *src2 =
- container_of(node2, struct vy_write_src, heap_node);
int cmp = vy_tuple_compare(src1->tuple, src2->tuple, stream->cmp_def);
if (cmp != 0)
@@ -310,7 +308,7 @@ vy_write_iterator_add_src(struct vy_write_iterator *stream,
vy_write_iterator_delete_src(stream, src);
return rc;
}
- rc = vy_source_heap_insert(&stream->src_heap, &src->heap_node);
+ rc = vy_source_heap_insert(&stream->src_heap, src);
if (rc != 0) {
diag_set(OutOfMemory, sizeof(void *),
"malloc", "vinyl write stream heap");
@@ -327,7 +325,7 @@ static void
vy_write_iterator_remove_src(struct vy_write_iterator *stream,
struct vy_write_src *src)
{
- vy_source_heap_delete(&stream->src_heap, &src->heap_node);
+ vy_source_heap_delete(&stream->src_heap, src);
vy_write_iterator_delete_src(stream, src);
}
@@ -486,15 +484,13 @@ vy_write_iterator_new_slice(struct vy_stmt_stream *vstream,
static NODISCARD int
vy_write_iterator_merge_step(struct vy_write_iterator *stream)
{
- struct heap_node *node = vy_source_heap_top(&stream->src_heap);
- assert(node != NULL);
- struct vy_write_src *src = container_of(node, struct vy_write_src,
- heap_node);
+ struct vy_write_src *src = vy_source_heap_top(&stream->src_heap);
+ assert(src != NULL);
int rc = src->stream.iface->next(&src->stream, &src->tuple);
if (rc != 0)
return rc;
if (src->tuple != NULL)
- vy_source_heap_update(&stream->src_heap, node);
+ vy_source_heap_update(&stream->src_heap, src);
else
vy_write_iterator_remove_src(stream, src);
return 0;
@@ -656,11 +652,9 @@ vy_write_iterator_build_history(struct vy_write_iterator *stream,
*is_first_insert = false;
assert(stream->stmt_i == -1);
assert(stream->deferred_delete_stmt == NULL);
- struct heap_node *node = vy_source_heap_top(&stream->src_heap);
- if (node == NULL)
+ struct vy_write_src *src = vy_source_heap_top(&stream->src_heap);
+ if (src == NULL)
return 0; /* no more data */
- struct vy_write_src *src =
- container_of(node, struct vy_write_src, heap_node);
/* Search must have been started already. */
assert(src->tuple != NULL);
/*
@@ -675,7 +669,7 @@ vy_write_iterator_build_history(struct vy_write_iterator *stream,
struct vy_write_src end_of_key_src;
end_of_key_src.is_end_of_key = true;
end_of_key_src.tuple = src->tuple;
- int rc = vy_source_heap_insert(&stream->src_heap, &end_of_key_src.heap_node);
+ int rc = vy_source_heap_insert(&stream->src_heap, &end_of_key_src);
if (rc) {
diag_set(OutOfMemory, sizeof(void *),
"malloc", "vinyl write stream heap");
@@ -777,9 +771,8 @@ next_lsn:
rc = vy_write_iterator_merge_step(stream);
if (rc != 0)
break;
- node = vy_source_heap_top(&stream->src_heap);
- assert(node != NULL);
- src = container_of(node, struct vy_write_src, heap_node);
+ src = vy_source_heap_top(&stream->src_heap);
+ assert(src != NULL);
assert(src->tuple != NULL);
if (src->is_end_of_key)
break;
@@ -796,7 +789,7 @@ next_lsn:
stream->deferred_delete_stmt = NULL;
}
- vy_source_heap_delete(&stream->src_heap, &end_of_key_src.heap_node);
+ vy_source_heap_delete(&stream->src_heap, &end_of_key_src);
vy_stmt_unref_if_possible(end_of_key_src.tuple);
return rc;
}
diff --git a/src/lib/salad/heap.h b/src/lib/salad/heap.h
index fd9e8ea54..6ba4a22ca 100644
--- a/src/lib/salad/heap.h
+++ b/src/lib/salad/heap.h
@@ -75,9 +75,8 @@
* my_type instances.
* The function below is example of valid comparator by value:
*
- * int test_type_less(const heap_t *heap,
- * const struct heap_node *a,
- * const struct heap_node *b) {
+ * bool test_type_less(const heap_t *heap, const struct heap_node *a,
+ * const struct heap_node *b) {
*
* const struct my_type *left = (struct my_type *)((char *)a -
* offsetof(struct my_type, vnode));
@@ -93,6 +92,15 @@
#error "HEAP_LESS must be defined"
#endif
+/** Structure, stored in the heap. */
+#ifndef heap_value_t
+#error "heap_value_t must be defined"
+#endif
+
+/** Name of heap_node attribute in heap_value_t. */
+#ifndef heap_value_attr
+#error "heap_value_attr must be defined"
+#endif
/**
* Tools for name substitution:
@@ -153,6 +161,15 @@ struct heap_iterator {
#ifndef HEAP_FORWARD_DECLARATION
+#ifndef container_of
+#define container_of(ptr, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (ptr); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+#endif
+
+#define node_to_value(n) container_of(n, heap_value_t, heap_value_attr)
+#define value_to_node(v) (&(v)->heap_value_attr)
+
/* Extern API that is the most usefull part. */
/**
@@ -170,32 +187,32 @@ HEAP(destroy)(heap_t *heap);
/**
* Return min value.
*/
-static inline struct heap_node *
+static inline heap_value_t *
HEAP(top)(heap_t *heap);
/**
* Erase min value.
*/
-static inline struct heap_node *
+static inline heap_value_t *
HEAP(pop)(heap_t *heap);
/**
* Insert value.
*/
static inline int
-HEAP(insert)(heap_t *heap, struct heap_node *nd);
+HEAP(insert)(heap_t *heap, heap_value_t *value);
/**
* Delete node from heap.
*/
static inline void
-HEAP(delete)(heap_t *heap, struct heap_node *value_node);
+HEAP(delete)(heap_t *heap, heap_value_t *value);
/**
- * Heapify tree after update of value under value_node pointer.
+ * Heapify tree after update of value.
*/
static inline void
-HEAP(update)(heap_t *heap, struct heap_node *value_node);
+HEAP(update)(heap_t *heap, heap_value_t *value);
/**
* Heapify tree after updating all values.
@@ -212,11 +229,17 @@ HEAP(iterator_init)(heap_t *heap, struct heap_iterator *it);
/**
* Heap iterator next.
*/
-static inline struct heap_node *
-HEAP(iterator_next) (struct heap_iterator *it);
+static inline heap_value_t *
+HEAP(iterator_next)(struct heap_iterator *it);
/* Routines. Functions below are useless for ordinary user. */
+/**
+ * Heapify tree after update of value having @a node attribute.
+ */
+static inline void
+HEAP(update_node)(heap_t *heap, struct heap_node *node);
+
/*
* Update backlink in the give heap_node structure.
*/
@@ -266,6 +289,13 @@ HEAP(destroy)(heap_t *heap)
free(heap->harr);
}
+static inline void
+HEAP(update_node)(heap_t *heap, struct heap_node *node)
+{
+ HEAP(sift_down)(heap, node);
+ HEAP(sift_up)(heap, node);
+}
+
/*
* Update backlink in the give heap_node structure.
*/
@@ -283,7 +313,8 @@ HEAP(sift_up)(heap_t *heap, struct heap_node *node)
{
heap_off_t curr_pos = node->pos, parent = (curr_pos - 1) / 2;
- while (curr_pos > 0 && HEAP_LESS(heap, node, heap->harr[parent])) {
+ while (curr_pos > 0 && HEAP_LESS(heap, node_to_value(node),
+ node_to_value(heap->harr[parent]))) {
node = heap->harr[curr_pos];
heap->harr[curr_pos] = heap->harr[parent];
@@ -311,13 +342,13 @@ HEAP(sift_down)(heap_t *heap, struct heap_node *node)
right = 2 * curr_pos + 2;
min_child = left;
if (right < heap->size &&
- HEAP_LESS(heap, heap->harr[right], heap->harr[left]))
+ HEAP_LESS(heap, node_to_value(heap->harr[right]),
+ node_to_value(heap->harr[left])))
min_child = right;
if (left >= heap->size ||
- HEAP_LESS(heap,
- heap->harr[curr_pos],
- heap->harr[min_child]) )
+ HEAP_LESS(heap, node_to_value(heap->harr[curr_pos]),
+ node_to_value(heap->harr[min_child])))
return;
node = heap->harr[curr_pos];
@@ -350,16 +381,13 @@ HEAP(reserve)(heap_t *heap)
* Insert value.
*/
static inline int
-HEAP(insert)(heap_t *heap, struct heap_node *node)
+HEAP(insert)(heap_t *heap, heap_value_t *value)
{
- (void) heap;
- assert(heap);
-
if (heap->size + 1 > heap->capacity) {
if (HEAP(reserve)(heap))
return -1;
}
-
+ struct heap_node *node = value_to_node(value);
heap->harr[heap->size] = node;
HEAP(update_link)(heap, heap->size++);
HEAP(sift_up)(heap, node); /* heapify */
@@ -371,25 +399,24 @@ HEAP(insert)(heap_t *heap, struct heap_node *node)
* Return min value without removing it from heap.
* If heap is empty, return NULL.
*/
-static inline struct heap_node *
+static inline heap_value_t *
HEAP(top)(heap_t *heap)
{
if (heap->size == 0)
return NULL;
- return heap->harr[0];
+ return node_to_value(heap->harr[0]);
}
/**
* Erase min value. Returns delete value.
*/
-static inline struct heap_node *
+static inline heap_value_t *
HEAP(pop)(heap_t *heap)
{
if (heap->size == 0)
return NULL;
-
- struct heap_node *res = heap->harr[0];
- HEAP(delete)(heap, heap->harr[0]);
+ heap_value_t *res = node_to_value(heap->harr[0]);
+ HEAP(delete)(heap, res);
return res;
}
@@ -397,32 +424,27 @@ HEAP(pop)(heap_t *heap)
* Delete node from heap.
*/
static inline void
-HEAP(delete)(heap_t *heap, struct heap_node *value_node)
+HEAP(delete)(heap_t *heap, heap_value_t *value)
{
if (heap->size == 0)
return;
heap->size--;
- heap_off_t curr_pos = value_node->pos;
+ heap_off_t curr_pos = value_to_node(value)->pos;
if (curr_pos == heap->size)
return;
heap->harr[curr_pos] = heap->harr[heap->size];
HEAP(update_link)(heap, curr_pos);
- HEAP(update)(heap, heap->harr[curr_pos]);
+ HEAP(update_node)(heap, heap->harr[curr_pos]);
}
-/**
- * Heapify tree after update of value under value_node pointer.
- */
static inline void
-HEAP(update)(heap_t *heap, struct heap_node *value_node)
+HEAP(update)(heap_t *heap, heap_value_t *value)
{
- /* heapify */
- HEAP(sift_down)(heap, value_node);
- HEAP(sift_up)(heap, value_node);
+ HEAP(update_node)(heap, value_to_node(value));
}
/**
@@ -455,12 +477,12 @@ HEAP(iterator_init)(heap_t *heap, struct heap_iterator *it)
/**
* Heap iterator next.
*/
-static inline struct heap_node *
+static inline heap_value_t *
HEAP(iterator_next)(struct heap_iterator *it)
{
if (it->curr_pos == it->heap->size)
return NULL;
- return it->heap->harr[it->curr_pos++];
+ return node_to_value(it->heap->harr[it->curr_pos++]);
}
/**
@@ -478,18 +500,25 @@ HEAP(check)(heap_t *heap)
right = 2 * curr_pos + 2;
min_child = left;
if (right < heap->size &&
- HEAP_LESS(heap, heap->harr[right], heap->harr[left]))
+ HEAP_LESS(heap, node_to_value(heap->harr[right]),
+ node_to_value(heap->harr[left])))
min_child = right;
- if (HEAP_LESS(heap,
- heap->harr[min_child],
- heap->harr[curr_pos]))
+ if (HEAP_LESS(heap, node_to_value(heap->harr[min_child]),
+ node_to_value(heap->harr[curr_pos])))
return -1;
}
return 0;
}
+#undef node_to_value
+#undef value_to_node
+#undef heap_value_t
+#undef heap_value_attr
+
#endif /* HEAP_FORWARD_DECLARATION */
#undef HEAP_FORWARD_DECLARATION
+#undef HEAP_NAME
+#undef HEAP_LESS
diff --git a/test/unit/heap.c b/test/unit/heap.c
index 8629cf5f1..5cf32802a 100644
--- a/test/unit/heap.c
+++ b/test/unit/heap.c
@@ -10,7 +10,6 @@
#define HEAP_FORWARD_DECLARATION
#include "salad/heap.h"
-#undef HEAP_FORWARD_DECLARATION
const uint32_t TEST_CASE_SIZE = 1000;
@@ -24,21 +23,18 @@ struct test_type {
/* If set, order by test_type->val2, otherwise by test_type->val1. */
static bool order_by_val2;
-int test_type_less(const heap_t *heap,
- const struct heap_node *a,
- const struct heap_node *b) {
-
- const struct test_type *left =
- (struct test_type *)((char *)a - offsetof(struct test_type, node));
- const struct test_type *right =
- (struct test_type *)((char *)b - offsetof(struct test_type, node));
+int
+test_type_less(const struct test_type *left, const struct test_type *right)
+{
if (order_by_val2)
return left->val2 < right->val2;
return left->val1 < right->val1;
}
#define HEAP_NAME test_heap
-#define HEAP_LESS(h, a, b) test_type_less(h, a, b)
+#define HEAP_LESS(h, a, b) test_type_less(a, b)
+#define heap_value_t struct test_type
+#define heap_value_attr node
#include "salad/heap.h"
@@ -63,10 +59,9 @@ test_insert_1_to_3()
for (uint32_t i = 0; i < 4; ++i) {
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = i;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
if (root_value->val1 != 0) {
fail("check that min.val1 is incorrect",
"root_value->val1 != 0");
@@ -94,10 +89,9 @@ test_insert_3_to_1()
for (uint32_t i = 3; i > 0; --i) {
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = i;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
if (root_value->val1 != i) {
fail("check that min.val1 is incorrect",
"root_value->val1 != i");
@@ -125,10 +119,9 @@ test_insert_50_to_150_mod_100()
for (uint32_t i = 50; i < 150; ++i) {
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = i % 100;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
if (i < 100 && root_value->val1 != 50) {
fail("min.val1 is incorrect",
@@ -146,8 +139,7 @@ test_insert_50_to_150_mod_100()
}
for (int i = 0; i < 100; ++i) {
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
test_heap_pop(&heap);
free(root_value);
}
@@ -170,10 +162,9 @@ test_insert_many_random()
value->val1 = rand();
ans = (value->val1 < ans ? value->val1 : ans);
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
if (root_value->val1 != ans) {
fail("min.val1 is incorrect", "root_value->val1 != ans");
}
@@ -204,9 +195,8 @@ test_insert_10_to_1_pop()
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = i;
- test_heap_insert(&heap, &value->node);
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ test_heap_insert(&heap, value);
+ root_value = test_heap_top(&heap);
if (root_value->val1 != i) {
fail("check that min.val1 is correct failed",
"root_value->val1 != i");
@@ -218,8 +208,7 @@ test_insert_10_to_1_pop()
}
for (uint32_t i = 1; i <= 10; ++i) {
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
test_heap_pop(&heap);
if (root_value->val1 != i) {
@@ -272,10 +261,9 @@ test_insert_many_pop_many_random()
keys[keys_it++] = value->val1 = rand();
ans = (value->val1 < ans ? value->val1 : ans);
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
if (root_value->val1 != ans) {
fail("check that min.val1 is correct failed",
"root_value->val1 != ans");
@@ -302,8 +290,7 @@ test_insert_many_pop_many_random()
uint32_t full_size = heap.size;
for (uint32_t i = 0; i < TEST_CASE_SIZE; ++i) {
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
test_heap_pop(&heap);
@@ -346,12 +333,11 @@ test_insert_pop_workload()
value = (struct test_type *)
malloc(sizeof(struct test_type));
value->val1 = rand();
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
else {
current_size--;
- root_value = container_of(test_heap_top(&heap),
- struct test_type, node);
+ root_value = test_heap_top(&heap);
test_heap_pop(&heap);
free(root_value);
@@ -383,7 +369,7 @@ test_pop_last()
test_heap_create(&heap);
value = (struct test_type *)malloc(sizeof(struct test_type));
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
test_heap_pop(&heap);
if (heap.size != 0) {
@@ -421,11 +407,11 @@ test_insert_update_workload()
value->val1 = rand();
nodes[current_size++] = value;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
else {
nodes[nodes_it]->val1 = rand();
- test_heap_update(&heap, &(nodes[nodes_it]->node));
+ test_heap_update(&heap, nodes[nodes_it]);
nodes_it++;
}
@@ -471,10 +457,10 @@ test_random_delete_workload()
value->val1 = rand();
nodes[current_size++] = value;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
else {
- test_heap_delete(&heap, &(nodes[nodes_it]->node));
+ test_heap_delete(&heap, nodes[nodes_it]);
current_size--;
nodes_it++;
}
@@ -507,10 +493,10 @@ test_delete_last_node()
value = (struct test_type *)
malloc(sizeof(struct test_type));
value->val1 = 0;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
- test_heap_delete(&heap, &value->node);
+ test_heap_delete(&heap, value);
if (test_heap_check(&heap)) {
fail("check heap invariants failed", "test_heap_check(&heap)");
}
@@ -529,7 +515,7 @@ test_heapify()
struct test_type *value = malloc(sizeof(struct test_type));
value->val1 = rand();
value->val2 = rand();
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
order_by_val2 = true;
diff --git a/test/unit/heap_iterator.c b/test/unit/heap_iterator.c
index 568a45d9b..3dfb8e77c 100644
--- a/test/unit/heap_iterator.c
+++ b/test/unit/heap_iterator.c
@@ -18,19 +18,15 @@ struct test_type {
struct heap_node node;
};
-int test_type_less(const heap_t *heap,
- const struct heap_node *a,
- const struct heap_node *b) {
-
- const struct test_type *left = (struct test_type *)((char *)a -
- offsetof(struct test_type, node));
- const struct test_type *right = (struct test_type *)((char *)b -
- offsetof(struct test_type, node));
+int test_type_less(const struct test_type *left, const struct test_type *right)
+{
return left->val1 < right->val1;
}
#define HEAP_NAME test_heap
-#define HEAP_LESS(h, a, b) test_type_less(h, a, b)
+#define HEAP_LESS(h, a, b) test_type_less(a, b)
+#define heap_value_t struct test_type
+#define heap_value_attr node
#include "salad/heap.h"
@@ -54,7 +50,7 @@ test_iterator_create()
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = 0;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
struct heap_iterator it;
test_heap_iterator_init(&heap, &it);
@@ -71,17 +67,16 @@ static void
test_iterator_empty()
{
header();
- struct heap_node *nd;
heap_t heap;
test_heap_create(&heap);
struct heap_iterator it;
test_heap_iterator_init(&heap, &it);
- nd = test_heap_iterator_next(&it);
+ struct test_type *t = test_heap_iterator_next(&it);
- if (nd != NULL)
- fail("incorrect node", "nd != NULL");
+ if (t != NULL)
+ fail("incorrect node", "t != NULL");
free_all_nodes(&heap);
@@ -93,15 +88,14 @@ static void
test_iterator_small()
{
header();
- struct test_type *value, *root_value;
- struct heap_node *test_node;
+ struct test_type *value;
heap_t heap;
test_heap_create(&heap);
for (uint32_t i = 4; i > 0; --i) {
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = i;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
struct heap_iterator it;
@@ -109,16 +103,11 @@ test_iterator_small()
memset((void *)used_key, 0, sizeof(used_key));
test_heap_iterator_init(&heap, &it);
- test_node = NULL;
for (uint32_t i = 0; i < 4; ++i) {
- test_node = test_heap_iterator_next(&it);
+ value = test_heap_iterator_next(&it);
- if (test_node == NULL)
- fail("NULL returned from iterator",
- "test_node == NULL");
-
- value = (struct test_type *)((char *)test_node -
- offsetof(struct test_type, node));
+ if (value == NULL)
+ fail("NULL returned from iterator", "value == NULL");
uint32_t val = value->val1;
if (val < 1 || val > 5)
fail("from iterator returned incorrect value",
@@ -135,10 +124,9 @@ test_iterator_small()
if (!f)
fail("some node was skipped", "!f");
- test_node = test_heap_iterator_next(&it);
- if (test_node != NULL)
- fail("after all iterator returns not NULL",
- "test_node != NULL");
+ value = test_heap_iterator_next(&it);
+ if (value != NULL)
+ fail("after all iterator returns not NULL", "value != NULL");
free_all_nodes(&heap);
footer();
@@ -149,15 +137,14 @@ test_iterator_large()
{
header();
uint32_t const TEST_CASE_SIZE = 1000;
- struct test_type *value, *root_value;
- struct heap_node *test_node;
+ struct test_type *value;
heap_t heap;
test_heap_create(&heap);
for (uint32_t i = TEST_CASE_SIZE; i > 0; --i) {
value = (struct test_type *)malloc(sizeof(struct test_type));
value->val1 = i;
- test_heap_insert(&heap, &value->node);
+ test_heap_insert(&heap, value);
}
struct heap_iterator it;
@@ -165,16 +152,12 @@ test_iterator_large()
memset((void *)used_key, 0, sizeof(used_key));
test_heap_iterator_init(&heap, &it);
- test_node = NULL;
for (uint32_t i = 0; i < TEST_CASE_SIZE; ++i) {
- test_node = test_heap_iterator_next(&it);
+ value = test_heap_iterator_next(&it);
- if (test_node == NULL)
- fail("NULL returned from iterator",
- "test_node == NULL");
+ if (value == NULL)
+ fail("NULL returned from iterator", "value == NULL");
- value = (struct test_type *)((char *)test_node -
- offsetof(struct test_type, node));
uint32_t val = value->val1;
if (val == 0 || val > TEST_CASE_SIZE)
fail("from iterator returned incorrect value",
@@ -192,10 +175,10 @@ test_iterator_large()
if (!f)
fail("some node was skipped", "!f");
- test_node = test_heap_iterator_next(&it);
- if (test_node != NULL)
+ value = test_heap_iterator_next(&it);
+ if (value != NULL)
fail("after all iterator returns not nil",
- "test_node != NULL");
+ "value != NULL");
free_all_nodes(&heap);
footer();
--
2.17.2 (Apple Git-113)
^ permalink raw reply [flat|nested] 9+ messages in thread