COLLECTION Making iterations pinnable

This is a feature that helps ELAPI.
It makes lookup of the fields that need
to be resolved for every event a bit faster.
The idea is to be able to put a 'pin'
into a specific place while iterating
the collection and make this place a new
"wrap around" place for the collection.
This means that next time you
iterate this collection you will start
iterating from the next item and
the item you got before pin will be last
in your iteration cycle.
Here is the example:
Assume you have two collections that you need
to compare and perform some action on collection
1 based on the presense of the item in collection 2.
Collection1 = A, B, C, D, E. F
Collection2 = A, C, F
The usual approach is to try A from collection 1
against A, B, C from collection 2. "A" will be found
right away. But to find "F" it has to be compared
to "A" and "C" first. The fact that the collections
are to some extent ordered can in some cases
help to reduce the number of comparisons.
If we found "C" in the list we can put a "pin"
into the collection there causing the iterator
to warp at this "pin" point. Since "D" and "E"
are not in the second collection we will have
to make same amount of comparisons in traditional
or "pinned" case to not find them.
To find "F" in pinned case there will be just one
comparison.
Traditional case = 1 + 3 + 2 + 3 + 3 + 3 = 15
Pinned case = 1 + 3 + 1 + 3 + 3 + 1 = 12
It is a 20% comparison reduction.

1 files changed, 170 insertions, 2 deletions

diff --git a/common/collection/collection_ut.c b/common/collection/collection_ut.c
index c17f5bc7b..5d0c58463 100644
--- a/common/collection/collection_ut.c
+++ b/common/collection/collection_ut.c
@@ -593,6 +593,7 @@ int iterator_test(void)
     int depth = 0;
     int idepth = 0;
     int len = 0;
+    int i;
 
     printf("\n\n==== ITERATOR TEST ====\n\n");
 
@@ -1015,8 +1016,6 @@ int iterator_test(void)
         return error;
     }
 
-    col_destroy_collection(peer);
-
     printf("\n\nIterate up test:\n\n");
 
     do {
@@ -1026,6 +1025,7 @@ int iterator_test(void)
         if (error) {
             printf("Error (iterate): %d\n", error);
             col_unbind_iterator(iterator);
+            col_destroy_collection(peer);
             return error;
         }
 
@@ -1065,6 +1065,174 @@ int iterator_test(void)
     while(1);
 
     col_unbind_iterator(iterator);
+
+    /* Bind iterator again in flat mode */
+    error =  col_bind_iterator(&iterator, peer, COL_TRAVERSE_FLAT | COL_TRAVERSE_END);
+    if (error) {
+        printf("Error (bind): %d\n", error);
+        col_destroy_collection(peer);
+        return error;
+    }
+
+    printf("\n\nCircled looping:\n\n");
+
+    for (i = 0; i < 200; i++) {
+        /* Loop through a collection */
+        error = col_iterate_collection(iterator, &item);
+        if (error) {
+            printf("Error (iterate): %d\n", error);
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return error;
+        }
+
+        /* Are we done ? */
+        if (item == NULL) printf("Reached end.\n\n");
+        else {
+            depth = 0;
+            col_get_item_depth(iterator, &depth);
+            printf("%*s", depth * 4, "");
+            col_debug_item(item);
+        }
+    }
+
+    /* Do not forget to unbind iterator - otherwise there will be a leak */
+    col_unbind_iterator(iterator);
+
+    /* Bind iterator again in flat mode */
+    error =  col_bind_iterator(&iterator, peer, COL_TRAVERSE_FLAT | COL_TRAVERSE_END);
+    if (error) {
+        printf("Error (bind): %d\n", error);
+        col_destroy_collection(peer);
+        return error;
+    }
+
+    printf("\n\nCircled looping with pin:\n\n");
+
+    do {
+        /* Loop through a collection */
+        error = col_iterate_collection(iterator, &item);
+        if (error) {
+            printf("Error (iterate): %d\n", error);
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return error;
+        }
+
+        if (strcmp(col_get_item_property(item, NULL), "queue") == 0) {
+            /* Make it a new looping point */
+            col_pin_iterator(iterator);
+            printf("Found pin point.\n\n");
+            break;
+        }
+        /* Are we done ? */
+        if (item == NULL) {
+            printf("Unexpected end.\n\n");
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return EINVAL;
+        }
+        else {
+            depth = 0;
+            col_get_item_depth(iterator, &depth);
+            printf("%*s", depth * 4, "");
+            col_debug_item(item);
+        }
+    }
+    while(1);
+
+    /* Second loop around the pin point */
+    for (i = 0; i < 200; i++) {
+        /* Loop through a collection */
+        error = col_iterate_collection(iterator, &item);
+        if (error) {
+            printf("Error (iterate): %d\n", error);
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return error;
+        }
+
+        /* Are we done ? */
+        if (item == NULL) printf("Reached end.\n\n");
+        else {
+            depth = 0;
+            col_get_item_depth(iterator, &depth);
+            printf("%*s", depth * 4, "");
+            col_debug_item(item);
+        }
+    }
+
+    /* Do not forget to unbind iterator - otherwise there will be a leak */
+    col_unbind_iterator(iterator);
+
+
+    /* Bind iterator again in flat mode */
+    error =  col_bind_iterator(&iterator, peer, COL_TRAVERSE_DEFAULT | COL_TRAVERSE_END);
+    if (error) {
+        printf("Error (bind): %d\n", error);
+        col_destroy_collection(peer);
+        return error;
+    }
+
+    printf("\n\nCircled looping with pin (default):\n\n");
+
+    do {
+        /* Loop through a collection */
+        error = col_iterate_collection(iterator, &item);
+        if (error) {
+            printf("Error (iterate): %d\n", error);
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return error;
+        }
+
+        if (strcmp(col_get_item_property(item, NULL), "queue") == 0) {
+            /* Make it a new looping point */
+            col_pin_iterator(iterator);
+            printf("Found pin point.\n\n");
+            break;
+        }
+        /* Are we done ? */
+        if (item == NULL) {
+            printf("Unexpected end.\n\n");
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return EINVAL;
+        }
+        else {
+            depth = 0;
+            col_get_item_depth(iterator, &depth);
+            printf("%*s", depth * 4, "");
+            col_debug_item(item);
+        }
+    }
+    while(1);
+
+    /* Second loop around the pin point */
+    for (i = 0; i < 200; i++) {
+        /* Loop through a collection */
+        error = col_iterate_collection(iterator, &item);
+        if (error) {
+            printf("Error (iterate): %d\n", error);
+            col_destroy_collection(peer);
+            col_unbind_iterator(iterator);
+            return error;
+        }
+
+        /* Are we done ? */
+        if (item == NULL) printf("Reached end.\n\n");
+        else {
+            depth = 0;
+            col_get_item_depth(iterator, &depth);
+            printf("%*s", depth * 4, "");
+            col_debug_item(item);
+        }
+    }
+
+    /* Do not forget to unbind iterator - otherwise there will be a leak */
+    col_unbind_iterator(iterator);
+    col_destroy_collection(peer);
+
     return EOK;
 }