[PATCH 1/3] salad: make heap struct more friendly to use

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

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)