[PATCH 0/3] Make heap API more friendly

[PATCH 0/3] Make heap API more friendly

[Vladislav Shpilevoy]

This patchset fixes some flaws in the salad heap API. First of all, fixed the
most irritating thing - a necessity to constantly call constainer_of in the code
because of heap's inability to cope with user-defined structures.

Secondly, fixed a hole in encapsulation of heap_node structure, which was
expluatated by vinyl.

Thirdly, fixed heap reserve behaviour, which was not really reserve(), but
rather twice().

Branch: http://github.com/tarantool/tarantool/tree/gerold103/heap-friendly-api

Vladislav Shpilevoy (3):
  salad: make heap struct more friendly to use
  salad: do not touch struct heap_node.pos in user's code
  salad: fix heap reserve() behaviour

 src/box/vy_lsm.c            |  21 +++---
 src/box/vy_range.c          |   2 +-
 src/box/vy_range.h          |   8 +-
 src/box/vy_scheduler.c      |  88 +++++++++-------------
 src/box/vy_write_iterator.c |  49 ++++++------
 src/lib/salad/heap.h        | 144 ++++++++++++++++++++++++------------
 test/unit/heap.c            |  76 ++++++++-----------
 test/unit/heap_iterator.c   |  67 +++++++----------
 8 files changed, 220 insertions(+), 235 deletions(-)

-- 
2.17.2 (Apple Git-113)

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

[Vladislav Shpilevoy]

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)

[PATCH 2/3] salad: do not touch struct heap_node.pos in user's code

[Vladislav Shpilevoy]

The only goal of reading and writing heap_node.pos was checking
if a node is now in a heap, or not. This commit encapsulates this
logic into a couple of functions.
---
 src/box/vy_lsm.c       | 12 ++++++------
 src/box/vy_range.c     |  2 +-
 src/box/vy_range.h     |  2 +-
 src/box/vy_scheduler.c | 23 ++++++++++-------------
 src/lib/salad/heap.h   | 23 ++++++++++++++++++++---
 5 files changed, 38 insertions(+), 24 deletions(-)

diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 57f5a7a29..07da145bd 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -196,8 +196,8 @@ vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
 		vy_lsm_ref(pk);
 	lsm->mem_format = format;
 	tuple_format_ref(lsm->mem_format);
-	lsm->in_dump.pos = UINT32_MAX;
-	lsm->in_compaction.pos = UINT32_MAX;
+	heap_node_create(&lsm->in_dump);
+	heap_node_create(&lsm->in_compaction);
 	lsm->space_id = index_def->space_id;
 	lsm->index_id = index_def->iid;
 	lsm->group_id = group_id;
@@ -240,8 +240,8 @@ void
 vy_lsm_delete(struct vy_lsm *lsm)
 {
 	assert(lsm->refs == 0);
-	assert(lsm->in_dump.pos == UINT32_MAX);
-	assert(lsm->in_compaction.pos == UINT32_MAX);
+	assert(heap_node_is_stray(&lsm->in_dump));
+	assert(heap_node_is_stray(&lsm->in_compaction));
 	assert(vy_lsm_read_set_empty(&lsm->read_set));
 	assert(lsm->env->lsm_count > 0);
 
@@ -764,7 +764,7 @@ vy_lsm_remove_run(struct vy_lsm *lsm, struct vy_run *run)
 void
 vy_lsm_add_range(struct vy_lsm *lsm, struct vy_range *range)
 {
-	assert(range->heap_node.pos == UINT32_MAX);
+	assert(heap_node_is_stray(&range->heap_node));
 	vy_range_heap_insert(&lsm->range_heap, range);
 	vy_range_tree_insert(&lsm->range_tree, range);
 	lsm->range_count++;
@@ -773,7 +773,7 @@ vy_lsm_add_range(struct vy_lsm *lsm, struct vy_range *range)
 void
 vy_lsm_remove_range(struct vy_lsm *lsm, struct vy_range *range)
 {
-	assert(range->heap_node.pos != UINT32_MAX);
+	assert(! heap_node_is_stray(&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.c b/src/box/vy_range.c
index d9afcfff3..3491784a4 100644
--- a/src/box/vy_range.c
+++ b/src/box/vy_range.c
@@ -197,7 +197,7 @@ vy_range_new(int64_t id, struct tuple *begin, struct tuple *end,
 	}
 	range->cmp_def = cmp_def;
 	rlist_create(&range->slices);
-	range->heap_node.pos = UINT32_MAX;
+	heap_node_create(&range->heap_node);
 	return range;
 }
 
diff --git a/src/box/vy_range.h b/src/box/vy_range.h
index facd2ac01..91f2682c8 100644
--- a/src/box/vy_range.h
+++ b/src/box/vy_range.h
@@ -156,7 +156,7 @@ vy_range_heap_less(struct vy_range *r1, struct vy_range *r2)
 static inline bool
 vy_range_is_scheduled(struct vy_range *range)
 {
-	return range->heap_node.pos == UINT32_MAX;
+	return heap_node_is_stray(&range->heap_node);
 }
 
 /**
diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
index 073c2c7cf..92d407808 100644
--- a/src/box/vy_scheduler.c
+++ b/src/box/vy_scheduler.c
@@ -514,8 +514,8 @@ void
 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);
+	assert(heap_node_is_stray(&lsm->in_dump));
+	assert(heap_node_is_stray(&lsm->in_compaction));
 	vy_dump_heap_insert(&scheduler->dump_heap, lsm);
 	vy_compaction_heap_insert(&scheduler->compaction_heap, lsm);
 }
@@ -524,12 +524,10 @@ void
 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);
+	assert(! heap_node_is_stray(&lsm->in_dump));
+	assert(! heap_node_is_stray(&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;
 }
 
 static void
@@ -537,12 +535,12 @@ vy_scheduler_update_lsm(struct vy_scheduler *scheduler, struct vy_lsm *lsm)
 {
 	if (lsm->is_dropped) {
 		/* Dropped LSM trees are exempted from scheduling. */
-		assert(lsm->in_dump.pos == UINT32_MAX);
-		assert(lsm->in_compaction.pos == UINT32_MAX);
+		assert(heap_node_is_stray(&lsm->in_dump));
+		assert(heap_node_is_stray(&lsm->in_compaction));
 		return;
 	}
-	assert(lsm->in_dump.pos != UINT32_MAX);
-	assert(lsm->in_compaction.pos != UINT32_MAX);
+	assert(! heap_node_is_stray(&lsm->in_dump));
+	assert(! heap_node_is_stray(&lsm->in_compaction));
 	vy_dump_heap_update(&scheduler->dump_heap, lsm);
 	vy_compaction_heap_update(&scheduler->compaction_heap, lsm);
 }
@@ -1601,7 +1599,7 @@ vy_task_compaction_complete(struct vy_task *task)
 	/* The iterator has been cleaned up in worker. */
 	task->wi->iface->close(task->wi);
 
-	assert(range->heap_node.pos == UINT32_MAX);
+	assert(heap_node_is_stray(&range->heap_node));
 	vy_range_heap_insert(&lsm->range_heap, range);
 	vy_scheduler_update_lsm(scheduler, lsm);
 
@@ -1633,7 +1631,7 @@ vy_task_compaction_abort(struct vy_task *task)
 
 	vy_run_discard(task->new_run);
 
-	assert(range->heap_node.pos == UINT32_MAX);
+	assert(heap_node_is_stray(&range->heap_node));
 	vy_range_heap_insert(&lsm->range_heap, range);
 	vy_scheduler_update_lsm(scheduler, lsm);
 }
@@ -1722,7 +1720,6 @@ vy_task_compaction_new(struct vy_scheduler *scheduler, struct vy_worker *worker,
 	 * so that it doesn't get selected again.
 	 */
 	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",
diff --git a/src/lib/salad/heap.h b/src/lib/salad/heap.h
index 6ba4a22ca..f267de3f1 100644
--- a/src/lib/salad/heap.h
+++ b/src/lib/salad/heap.h
@@ -126,7 +126,8 @@
 #define HEAP_STRUCTURES
 
 enum {
-	HEAP_INITIAL_CAPACITY = 8
+	HEAP_INITIAL_CAPACITY = 8,
+	HEAP_NODE_STRAY_POS = UINT32_MAX,
 };
 
 typedef uint32_t heap_off_t;
@@ -149,6 +150,20 @@ struct heap_node {
 	heap_off_t pos;
 };
 
+/** Initialize a heap node with default values. */
+static inline void
+heap_node_create(struct heap_node *node)
+{
+	node->pos = HEAP_NODE_STRAY_POS;
+}
+
+/** Check if a heap node does not belong to any heap. */
+static inline bool
+heap_node_is_stray(const struct heap_node *node)
+{
+	return node->pos == HEAP_NODE_STRAY_POS;
+}
+
 /**
  * Heap iterator structure.
  */
@@ -429,9 +444,11 @@ HEAP(delete)(heap_t *heap, heap_value_t *value)
 	if (heap->size == 0)
 		return;
 
+	struct heap_node *node = value_to_node(value);
+	assert(! heap_node_is_stray(node));
 	heap->size--;
-
-	heap_off_t curr_pos = value_to_node(value)->pos;
+	heap_off_t curr_pos = node->pos;
+	heap_node_create(node);
 
 	if (curr_pos == heap->size)
 		return;
-- 
2.17.2 (Apple Git-113)

[PATCH 3/3] salad: fix heap reserve() behaviour

[Vladislav Shpilevoy]

Reserve() function by definition should ensure that there is
enough space to store something. But heap reserve() always just
increases the capacity twice. Even if there was already enough
memory. Check for not necessary realloc was done out of this
function. This was wrong. The commit makes reserve() be real
reserve().

The commit is motivated not by pursue of justice, but by
forthcoming usage of reserve() in SWIM module code.
---
 src/lib/salad/heap.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/lib/salad/heap.h b/src/lib/salad/heap.h
index f267de3f1..31750216a 100644
--- a/src/lib/salad/heap.h
+++ b/src/lib/salad/heap.h
@@ -382,6 +382,8 @@ HEAP(sift_down)(heap_t *heap, struct heap_node *node)
 static inline int
 HEAP(reserve)(heap_t *heap)
 {
+	if (heap->capacity > heap->size)
+		return 0;
 	heap_off_t capacity = heap->capacity == 0 ? HEAP_INITIAL_CAPACITY :
 		heap->capacity << 1;
 	void *harr = realloc(heap->harr, sizeof(struct heap_node *) * capacity);
@@ -398,10 +400,8 @@ HEAP(reserve)(heap_t *heap)
 static inline int
 HEAP(insert)(heap_t *heap, heap_value_t *value)
 {
-	if (heap->size + 1 > heap->capacity) {
-		if (HEAP(reserve)(heap))
-			return -1;
-	}
+	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++);
-- 
2.17.2 (Apple Git-113)

Re: [tarantool-patches] [PATCH 1/3] salad: make heap struct more friendly to use

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/02/22 14:39]:
> 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.

OK to push.


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [tarantool-patches] [PATCH 3/3] salad: fix heap reserve() behaviour

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/02/22 14:39]:
> Reserve() function by definition should ensure that there is
> enough space to store something. But heap reserve() always just
> increases the capacity twice. Even if there was already enough
> memory. Check for not necessary realloc was done out of this
> function. This was wrong. The commit makes reserve() be real
> reserve().
> 

OK to push.

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [tarantool-patches] Re: [PATCH 3/3] salad: fix heap reserve() behaviour

[Vladislav Shpilevoy]

On 22/02/2019 21:31, Konstantin Osipov wrote:
> * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/02/22 14:39]:
>> Reserve() function by definition should ensure that there is
>> enough space to store something. But heap reserve() always just
>> increases the capacity twice. Even if there was already enough
>> memory. Check for not necessary realloc was done out of this
>> function. This was wrong. The commit makes reserve() be real
>> reserve().
>>
> 
> OK to push.
> 
> -- 
> Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
> http://tarantool.io - www.twitter.com/kostja_osipov
> 
Pushed to 2.1.

Re: [tarantool-patches] Re: [PATCH 1/3] salad: make heap struct more friendly to use

[Vladislav Shpilevoy]

On 22/02/2019 21:26, Konstantin Osipov wrote:
> * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/02/22 14:39]:
>> 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.
> 
> OK to push.
> 
> 
> -- 
> Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
> http://tarantool.io - www.twitter.com/kostja_osipov
> 
Pushed to 2.1.

Re: [PATCH 2/3] salad: do not touch struct heap_node.pos in user's code

[Vladimir Davydov]

On Fri, Feb 22, 2019 at 02:38:59PM +0300, Vladislav Shpilevoy wrote:
> The only goal of reading and writing heap_node.pos was checking
> if a node is now in a heap, or not. This commit encapsulates this
> logic into a couple of functions.

Awesome, thanks. Pushed to 2.1.

(You forgot to push the branch to GitHub so applied the patch from this email).