summaryrefslogtreecommitdiff
path: root/common
diff options
context:
space:
mode:
authorDmitri Pal <dpal@redhat.com>2009-09-15 15:14:18 -0400
committerStephen Gallagher <sgallagh@redhat.com>2009-10-05 10:32:07 -0400
commit26a9c1f22f31a87a83fbb59caea7c7565563f479 (patch)
tree30fead50d40fbdc3594563d0f78372a3dabbf45a /common
parent93b643607c3d9a0775faaeb08e404f703a4200f7 (diff)
downloadsssd-26a9c1f22f31a87a83fbb59caea7c7565563f479.tar.gz
sssd-26a9c1f22f31a87a83fbb59caea7c7565563f479.tar.bz2
sssd-26a9c1f22f31a87a83fbb59caea7c7565563f479.zip
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.
Diffstat (limited to 'common')
-rw-r--r--common/collection/collection.h3
-rw-r--r--common/collection/collection_iter.c49
-rw-r--r--common/collection/collection_priv.h3
-rw-r--r--common/collection/collection_ut.c172
4 files changed, 220 insertions, 7 deletions
diff --git a/common/collection/collection.h b/common/collection/collection.h
index b4bbb2a4..be1240ca 100644
--- a/common/collection/collection.h
+++ b/common/collection/collection.h
@@ -742,6 +742,9 @@ int col_get_iterator_depth(struct collection_iterator *iterator, int *depth);
*/
int col_get_item_depth(struct collection_iterator *iterator, int *depth);
+/* Pins down the iterator to loop around current point */
+void col_pin_iterator(struct collection_iterator *iterator);
+
/* FIXME - Do we need to be able to rewind iterator? */
/* Set collection class */
diff --git a/common/collection/collection_iter.c b/common/collection/collection_iter.c
index 4d7a9042..f66fc308 100644
--- a/common/collection/collection_iter.c
+++ b/common/collection/collection_iter.c
@@ -87,6 +87,8 @@ int col_bind_iterator(struct collection_iterator **iterator,
iter->stack_depth = 0;
iter->item_level = 0;
iter->flags = mode_flags;
+ iter->pin_level = 0;
+ iter->can_break = 0;
TRACE_INFO_NUMBER("Iterator flags", iter->flags);
@@ -110,6 +112,7 @@ int col_bind_iterator(struct collection_iterator **iterator,
header = (struct collection_header *)ci->data;
header->reference_count++;
iter->top = ci;
+ iter->pin = ci;
*(iter->stack) = ci;
iter->stack_depth++;
@@ -213,17 +216,29 @@ int col_iterate_collection(struct collection_iterator *iterator,
TRACE_INFO_NUMBER("Stack depth:", iterator->stack_depth);
- /* Are we done? */
if (iterator->stack_depth == 0) {
- TRACE_FLOW_STRING("We are done.", "");
- *item = NULL;
- return EOK;
+ /* Re-init so if we continue looping we start over */
+ iterator->stack[0] = iterator->top;
+ iterator->stack_depth++;
+ iterator->item_level = 0;
}
/* Is current item available */
current = iterator->stack[iterator->stack_depth - 1];
iterator->item_level = iterator->stack_depth - 1;
+ /* Are we done? */
+ if (((iterator->stack_depth - 1) == iterator->pin_level) &&
+ (iterator->pin == current)) {
+ if (iterator->can_break) {
+ TRACE_FLOW_STRING("We are done.", "");
+ *item = NULL;
+ iterator->can_break = 0;
+ return EOK;
+ }
+ else iterator->can_break = 1;
+ }
+
/* We are not done so check if we have an item */
if (current != NULL) {
@@ -357,6 +372,30 @@ int col_iterate_collection(struct collection_iterator *iterator,
}
}
- TRACE_FLOW_STRING("iterate_collection", "Exit");
+ TRACE_FLOW_STRING("col_iterate_collection", "Exit");
return EOK;
}
+
+
+/* Pins down the iterator to loop around this point */
+void col_pin_iterator(struct collection_iterator *iterator)
+{
+ TRACE_FLOW_STRING("col_iterator_add_pin", "Entry");
+
+ while ((iterator->stack[iterator->stack_depth - 1] == NULL) &&
+ (iterator->stack_depth)) {
+ iterator->stack_depth--;
+ }
+
+ if (iterator->stack_depth == 0) {
+ iterator->pin = iterator->top;
+ iterator->pin_level = 0;
+ }
+ else {
+ iterator->pin = iterator->stack[iterator->stack_depth - 1];
+ iterator->pin_level = iterator->stack_depth - 1;
+ }
+ iterator->can_break = 0;
+
+ TRACE_FLOW_STRING("col_iterator_add_pin", "Exit");
+}
diff --git a/common/collection/collection_priv.h b/common/collection/collection_priv.h
index 767514be..a8aa3669 100644
--- a/common/collection/collection_priv.h
+++ b/common/collection/collection_priv.h
@@ -60,6 +60,9 @@ struct collection_iterator {
unsigned item_level;
int flags;
struct collection_item *end_item;
+ struct collection_item *pin;
+ unsigned pin_level;
+ unsigned can_break;
};
diff --git a/common/collection/collection_ut.c b/common/collection/collection_ut.c
index c17f5bc7..5d0c5846 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;
}