Add avl_for_each_elements_with_key_safe() macro and do some basic tests
authorHenning Rogge <henning.rogge@fkie.fraunhofer.de>
Tue, 15 May 2018 14:50:58 +0000 (16:50 +0200)
committerHenning Rogge <henning.rogge@fkie.fraunhofer.de>
Tue, 15 May 2018 14:50:58 +0000 (16:50 +0200)
include/oonf/libcommon/avl.h
src/tests/common/test_common_avl.c

index c8f7f38..8ef2115 100644 (file)
@@ -555,6 +555,29 @@ avl_is_node_added(const struct avl_node *node) {
     avl_last_element(tree, element, node_member), element, node_member, ptr)
 
 /**
+ * Loop over a block of elements of a tree with a certain key, used similar
+ * to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param start helper pointer to remember start of iteration
+ * @param iterator helper pointer to safe loop from element removal.
+ * @param key pointer to key
+ */
+#define avl_for_each_elements_with_key_safe(tree, element, node_member, start, iterator, key)                          \
+  for (start = element = avl_find_element(tree, key, element, node_member),                                            \
+       iterator = avl_next_element_safe(tree, element, node_member);                                                              \
+       element != NULL && &element->node_member.list != &(tree)->list_head &&                                          \
+       (element == start || element->node_member.follower);                                                            \
+       element = iterator, iterator = avl_next_element(iterator, node_member))
+
+/**
  * A special loop that removes all elements of the tree and cleans up the tree
  * root. The loop body is responsible to free the node elements of the tree.
  *
index 4f463c9..e476507 100644 (file)
@@ -627,7 +627,7 @@ static void test_remove_all_macro(bool do_random) {
   END_TEST();
 }
 
-static void test_for_each_key_macros(void) {
+static void test_for_each_key_macro(void) {
   struct tree_element *e, *p;
   uint32_t key;
   uint32_t i;
@@ -781,6 +781,160 @@ static void test_for_each_key_macros(void) {
   END_TEST();
 }
 
+static void test_for_each_key_safe_macro1(void) {
+  struct tree_element *e, *p, *it;
+  uint32_t key;
+  uint32_t i;
+  uint32_t result[4];
+
+  START_TEST();
+  avl_init(&head, avl_comp_uint32, true);
+
+  key = 3;
+  i = 0;
+  avl_for_each_elements_with_key_safe(&head, e, node, p, it, &key) {
+    CHECK_TRUE(false, "elements returned by loop over empty tree");
+  }
+
+  /* add node with value 4 (4,4,4) */
+  nodes[3].node.key = &nodes[3].value;
+  avl_insert(&head, &nodes[3].node);
+
+  /* add first duplicate with value 4 */
+  additional_node1.value = 4;
+  additional_node1.node.key = &additional_node1.value;
+  avl_insert(&head, &additional_node1.node);
+
+  /* add second duplicate with value 4 */
+  additional_node2.value = 4;
+  additional_node2.node.key = &additional_node2.value;
+  avl_insert(&head, &additional_node2.node);
+
+  key = 4;
+  result[0] = 0;
+  result[1] = 0;
+  result[2] = 0;
+  result[3] = 0;
+
+  avl_for_each_elements_with_key_safe(&head, e, node, p, it, &key) {
+    if (e == &nodes[3]) {
+      result[0]++;
+    }
+    else if (e == &additional_node1) {
+      result[1]++;
+    }
+    else if (e == &additional_node2) {
+      result[2]++;
+    }
+    else {
+      result[3]++;
+    }
+  }
+
+  CHECK_TRUE(result[0] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[0] <= 1, "First node with key=4 returned multiple times");
+  CHECK_TRUE(result[1] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[1] <= 1, "First node with key=4 returned multiple times");
+  CHECK_TRUE(result[2] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[2] <= 1, "First node with key=4 returned multiple times");
+
+  CHECK_TRUE(result[3] == 0, "Unknown node returned");
+
+  /* add node with value 3 (3,4,4,4) */
+  nodes[2].node.key = &nodes[2].value;
+  avl_insert(&head, &nodes[2].node);
+
+  key = 4;
+  i = 0;
+  result[0] = 0;
+  result[1] = 0;
+  result[2] = 0;
+  result[3] = 0;
+
+  avl_for_each_elements_with_key_safe(&head, e, node, p, it, &key) {
+    if (e == &nodes[3]) {
+      result[0]++;
+    }
+    else if (e == &additional_node1) {
+      result[1]++;
+    }
+    else if (e == &additional_node2) {
+      result[2]++;
+    }
+    else {
+      result[3]++;
+    }
+  }
+
+  CHECK_TRUE(result[0] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[0] <= 1, "First node with key=4 returned multiple times");
+  CHECK_TRUE(result[1] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[1] <= 1, "First node with key=4 returned multiple times");
+  CHECK_TRUE(result[2] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[2] <= 1, "First node with key=4 returned multiple times");
+
+  CHECK_TRUE(result[3] == 0, "Unknown node returned");
+
+  /* add node with value 5 (3,4,4,4,5) */
+  nodes[4].node.key = &nodes[4].value;
+  avl_insert(&head, &nodes[4].node);
+
+  key = 4;
+  i = 0;
+  result[0] = 0;
+  result[1] = 0;
+  result[2] = 0;
+  result[3] = 0;
+
+  avl_for_each_elements_with_key_safe(&head, e, node, p, it, &key) {
+    if (e == &nodes[3]) {
+      result[0]++;
+    }
+    else if (e == &additional_node1) {
+      result[1]++;
+    }
+    else if (e == &additional_node2) {
+      result[2]++;
+    }
+    else {
+      result[3]++;
+    }
+  }
+
+  CHECK_TRUE(result[0] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[0] <= 1, "First node with key=4 returned multiple times");
+  CHECK_TRUE(result[1] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[1] <= 1, "First node with key=4 returned multiple times");
+  CHECK_TRUE(result[2] >= 1, "First node with key=4 not returned");
+  CHECK_TRUE(result[2] <= 1, "First node with key=4 returned multiple times");
+
+  CHECK_TRUE(result[3] == 0, "Unknown node returned");
+
+  key = 3;
+  i = 0;
+  avl_for_each_elements_with_key_safe(&head, e, node, p, it, &key) {
+    i++;
+
+    switch (i) {
+      case 1:
+        CHECK_TRUE(e == &nodes[2], "First node with key=3 not returned first");
+        break;
+      default:
+        CHECK_TRUE(false, "More than one element with key=3 returned");
+        break;
+    }
+  }
+
+  CHECK_TRUE(i>0, "Less than one nodes returned");
+
+  key = 6;
+  avl_for_each_elements_with_key_safe(&head, e, node, p, it, &key) {
+    CHECK_TRUE(false, "Element returned by loop over non-existing key");
+  }
+
+  END_TEST();
+}
+
 static int
 compare_ints (const void *a, const void *b)
 {
@@ -886,7 +1040,10 @@ int main(int argc __attribute__ ((unused)), char **argv __attribute__ ((unused))
   do_tests(false);
   do_tests(true);
   test_random_insert();
-  test_for_each_key_macros();
+  test_for_each_key_macro();
+  test_for_each_key_safe_macro1();
+
+  //TODO: test removal in for_each_key_safe
 
   return FINISH_TESTING();
 }