- remove format_* functions that didn't need to be exported

- make SDN lists/queues also have a sorted companion which we can use
  for presence testing

1 files changed, 122 insertions, 91 deletions

diff --git a/src/format.c b/src/format.c
index 9b1bb2d..9f8074c 100644
--- a/src/format.c
+++ b/src/format.c
@@ -103,9 +103,19 @@ xmemdup(char *region, int size)
 	return ret;
 }
 
-/* Maintain a DN list, which is list of distinguished names. */
+/* Maintain a DN list, which is list of distinguished names, and a sorted copy
+ * which we can check for inclusion much faster. */
+static int
+compare_sdn(const void *a, const void *b)
+{
+	const struct slapi_dn **sa, **sb;
+	sa = (const struct slapi_dn **) a;
+	sb = (const struct slapi_dn **) b;
+	return strcmp(slapi_sdn_get_ndn(*sa), slapi_sdn_get_ndn(*sb));
+}
+
 void
-format_free_sdn_list(struct slapi_dn **list)
+format_free_sdn_list(struct slapi_dn **list, struct slapi_dn **list2)
 {
 	unsigned int i;
 	if (list != NULL) {
@@ -114,42 +124,59 @@ format_free_sdn_list(struct slapi_dn **list)
 		}
 		free(list);
 	}
+	free(list2);
 }
 
-struct slapi_dn **
-format_dup_sdn_list(struct slapi_dn **list)
+/* Turn shallow-copy list pointers into deep ones. */
+static void
+format_dup_sdn_list(struct slapi_dn ***list, struct slapi_dn ***list2)
 {
-	struct slapi_dn **ret;
+	struct slapi_dn **ret = NULL, **ret2 = NULL;
 	unsigned int i;
-	for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
+	for (i = 0;
+	     (list != NULL) && (*list != NULL) && ((*list)[i] != NULL);
+	     i++) {
 		continue;
 	}
-	ret = malloc((i + 1) * sizeof(struct slapi_dn*));
-	if (ret != NULL) {
-		for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
-			ret[i] = slapi_sdn_dup(list[i]);
+	if (i > 0) {
+		ret = malloc((i + 1) * sizeof(struct slapi_dn*));
+		ret2 = malloc((i + 1) * sizeof(struct slapi_dn*));
+		if ((ret != NULL) && (ret2 != NULL)) {
+			for (i = 0;
+			     (list2 != NULL) && (*list2 != NULL) && ((*list2)[i] != NULL);
+			     i++) {
+				ret[i] = slapi_sdn_dup((*list2)[i]);
+				ret2[i] = ret[i];
+			}
+			ret[i] = NULL;
+			ret2[i] = NULL;
+			*list = ret;
+			*list2 = ret2;
 		}
-		ret[i] = NULL;
 	}
-	return ret;
 }
 
-struct slapi_dn **
-format_make_sdn_list(char **list)
+/* Build a list from string DN values. */
+static struct slapi_dn **
+format_make_sdn_list(char **list, struct slapi_dn ***ret,
+		     struct slapi_dn ***ret2)
 {
-	struct slapi_dn **ret;
 	unsigned int i;
 	for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
 		continue;
 	}
-	ret = malloc((i + 1) * sizeof(struct slapi_dn*));
-	if (ret != NULL) {
+	*ret = malloc((i + 1) * sizeof(struct slapi_dn*));
+	*ret2 = malloc((i + 1) * sizeof(struct slapi_dn*));
+	if ((*ret != NULL) && (*ret2 != NULL)) {
 		for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
-			ret[i] = slapi_sdn_new_dn_byval(list[i]);
+			(*ret)[i] = slapi_sdn_new_dn_byval(list[i]);
+			(*ret2)[i] = (*ret)[i];
 		}
-		ret[i] = NULL;
+		(*ret)[i] = NULL;
+		(*ret2)[i] = NULL;
+		qsort((*ret2), i, sizeof(**ret2), &compare_sdn);
 	}
-	return ret;
+	return *ret;
 }
 
 /* Find the DN in a sorted list.  Return either where it is, or where it
@@ -199,66 +226,55 @@ format_bsearch_sdn_list(struct slapi_dn **list, struct slapi_dn *sdn,
 	return found;
 }
 
-static struct slapi_dn **
-format_add_sdn_list_maybe_sorted(struct slapi_dn ***list, const char *dn,
-				 bool_t sorted)
+void
+format_add_sdn_list(struct slapi_dn ***list, struct slapi_dn ***list2,
+		    const char *dn)
 {
-	struct slapi_dn **ret, *sdn;
+	struct slapi_dn **ret, **ret2, *sdn;
 	unsigned int len, point;
 
 	sdn = slapi_sdn_new_dn_byval(dn);
-	/* Figure out how long the current list is. */
+	/* Figure out the size of the list. */
 	for (len = 0;
 	     (list != NULL) && (*list != NULL) && ((*list)[len] != NULL);
 	     len++) {
-		/* If it's not sorted (because the list is being used as a
-		 * queue, which is pretty much always), we have to check every
-		 * entry anyway, so we might as well do it now. */
-		if (!sorted && (slapi_sdn_compare((*list)[len], sdn) == 0)) {
-			slapi_sdn_free(&sdn);
-			return *list;
-		}
 		continue;
 	}
-	if (sorted) {
-		/* If it's sorted, we can search for the entry or figure out
-		 * where to insert the new one. */
-		if (format_bsearch_sdn_list(*list, sdn, len, &point)) {
-			slapi_sdn_free(&sdn);
-			return *list;
-		}
-	} else {
-		/* We're appending. */
-		point = len;
+	/* Search the sorted list. */
+	if (format_bsearch_sdn_list(*list2, sdn, len, &point)) {
+		slapi_sdn_free(&sdn);
+		return;
 	}
+	/* Append the entry to the unsorted list, insert it into the sorted
+	 * list. */
 	ret = malloc((len + 2) * sizeof(struct slapi_dn*));
-	if (ret != NULL) {
-		/* Copy pointers to entries before the insertion point. */
-		memcpy(ret, *list, point * sizeof(ret[0]));
+	ret2 = malloc((len + 2) * sizeof(struct slapi_dn*));
+	if ((ret != NULL) && (ret2 != NULL)) {
+		/* Copy pointers to existing entries. */
+		memcpy(ret, *list, len * sizeof(sdn));
 		/* The new entry. */
-		ret[point] = sdn;
-		/* If there are any after the insertion point, add them. */
-		if (len > point) {
-			memcpy(ret + point + 1, (*list) + point,
-			       (len - point) * sizeof(ret[0]));
-		}
+		ret[len] = sdn;
+		/* The end of the list. */
 		ret[len + 1] = NULL;
 		free(*list);
-		*list = ret;
+		/* Copy pointers to lesser entries. */
+		if (point > 0) {
+			memcpy(ret2, *list2, point * sizeof(sdn));
+		}
+		/* The new entry. */
+		ret2[point] = sdn;
+		/* The rest of the list. */
+		if (len > point) {
+			memcpy(ret2 + point + 1,
+			       (*list2) + point,
+			       (len - point) * sizeof(sdn));
+		}
+		ret2[len + 1] = NULL;
+		free(*list2);
 	}
-	return *list;
-}
-
-struct slapi_dn **
-format_add_sdn_list(struct slapi_dn ***list, const char *dn)
-{
-	return format_add_sdn_list_maybe_sorted(list, dn, FALSE);
-}
-
-struct slapi_dn **
-format_add_sdn_list_sorted(struct slapi_dn ***list, const char *dn)
-{
-	return format_add_sdn_list_maybe_sorted(list, dn, TRUE);
+	*list = ret;
+	*list2 = ret2;
+	return;
 }
 
 static int
@@ -278,14 +294,12 @@ format_check_entry(const char *dn, char *filter, void *identity)
 	}
 }
 
-static struct slapi_dn **
-format_add_filtered_sdn_list(struct slapi_dn ***list, const char *dn,
-			     char *filter, void *identity)
+static void
+format_add_filtered_sdn_list(struct slapi_dn ***list, struct slapi_dn ***list2,
+			     const char *dn, char *filter, void *identity)
 {
 	if (format_check_entry(dn, filter, identity) == 0) {
-		return format_add_sdn_list(list, dn);
-	} else {
-		return *list;
+		format_add_sdn_list(list, list2, dn);
 	}
 }
 
@@ -306,7 +320,8 @@ format_free_ref_attr_list(struct format_ref_attr_list **list)
 				if (link->filter != NULL) {
 					slapi_filter_free(link->filter, TRUE);
 				}
-				format_free_sdn_list(link->base_sdn_list);
+				format_free_sdn_list(link->base_sdn_list,
+						     link->base_sdn_list2);
 			}
 			free(list[i]->links);
 			free(list[i]->set);
@@ -369,8 +384,11 @@ format_dup_ref_attr_list(struct format_ref_attr_list **list)
 					}
 				}
 				sdn_list = list[i]->links[j].base_sdn_list;
-				ret[i]->links[j].base_sdn_list =
-					format_dup_sdn_list(sdn_list);
+				ret[i]->links[j].base_sdn_list = sdn_list;
+				sdn_list = list[i]->links[j].base_sdn_list2;
+				ret[i]->links[j].base_sdn_list2 = sdn_list;
+				format_dup_sdn_list(&ret[i]->links[j].base_sdn_list,
+						    &ret[i]->links[j].base_sdn_list2);
 				ret[i]->n_links++;
 			}
 			ret[i]->group = strdup(list[i]->group);
@@ -488,6 +506,7 @@ format_add_ref_attr_list(struct format_ref_attr_list ***list,
 				}
 			}
 			ret[i]->links[j].base_sdn_list = NULL;
+			ret[i]->links[j].base_sdn_list2 = NULL;
 		}
 		ret[i]->group = strdup(group);
 		ret[i]->set = strdup(set);
@@ -670,12 +689,8 @@ format_add_bv_list(struct berval ***bvlist, const struct berval *bv)
 	if (bvlist == NULL) {
 		return;
 	}
-	if (*bvlist != NULL) {
-		for (i = 0; (*bvlist)[i] != NULL; i++) {
-			continue;
-		}
-	} else {
-		i = 0;
+	for (i = 0; (*bvlist != NULL) && ((*bvlist)[i] != NULL); i++) {
+		continue;
 	}
 	list = malloc((i + 2) * sizeof(struct berval *));
 	if (list != NULL) {
@@ -1179,7 +1194,7 @@ format_deref_rx(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 {
 	int i, j, k, argc;
 	Slapi_Entry *entry;
-	Slapi_DN **these, **next;
+	Slapi_DN **these, **these2, **next, **next2;
 	Slapi_ValueSet *values;
 	Slapi_Value *value;
 	int disposition, buffer_flags;
@@ -1197,9 +1212,10 @@ format_deref_rx(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 
 	/* Follow the chain: set up the first link. */
 	these = NULL;
+	these2 = NULL;
 	choices = NULL;
 	dn = slapi_entry_get_dn(e);
-	format_add_sdn_list(&these, dn);
+	format_add_sdn_list(&these, &these2, dn);
 
 	/* For the first N-1 links, read the contents of the named attribute
 	 * from each entry we're examining at this point, and use the values
@@ -1208,6 +1224,7 @@ format_deref_rx(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	 * caller. */
 	for (i = 0; (these != NULL) && (i < list->n_links); i++) {
 		next = NULL;
+		next2 = NULL;
 		attrs[0] = list->links[i].attribute;
 		attrs[1] = NULL;
 		/* Walk the set of entries for this iteration. */
@@ -1221,6 +1238,7 @@ format_deref_rx(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 					"\"%s\" for \"%s\"\n",
 					fname, slapi_dn_parent(dn), attrs[0]);
 			format_add_sdn_list(&list->links[i].base_sdn_list,
+					    &list->links[i].base_sdn_list2,
 					    slapi_dn_parent(dn));
 			/* Pull up the named entry. */
 			entry = NULL;
@@ -1268,13 +1286,13 @@ format_deref_rx(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 					}
 					/* Let's visit the named entry this
 					 * time, in case we're nesting. */
-					format_add_filtered_sdn_list(&these,
+					format_add_filtered_sdn_list(&these, &these2,
 								     cvalue,
 								     list->links[i + 1].filter_str,
 								     state->plugin_identity);
 					/* We need to visit the named entry
 					 * next time. */
-					format_add_filtered_sdn_list(&next,
+					format_add_filtered_sdn_list(&next, &next2,
 								     cvalue,
 								     list->links[i + 1].filter_str,
 								     state->plugin_identity);
@@ -1302,13 +1320,15 @@ format_deref_rx(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 		}
 		/* Replace the list of entries we're examining now with the
 		 * list of entries we need to examine next. */
-		format_free_sdn_list(these);
+		format_free_sdn_list(these, these2);
 		these = next;
+		these2 = next2;
 		next = NULL;
+		next2 = NULL;
 	}
 
 	/* Clean up and return any values we found. */
-	format_free_sdn_list(these);
+	format_free_sdn_list(these, these2);
 	if (choices != NULL) {
 		format_add_choice(outbuf_choices, outbuf, &choices);
 		return 0;
@@ -1626,7 +1646,7 @@ struct format_referred_r_entry_cbdata {
 	struct plugin_state *state;
 	char *attribute;
 	struct berval ***choices;
-	Slapi_DN ***sdn_list;
+	Slapi_DN ***sdn_list, ***sdn_list2;
 };
 
 static int
@@ -1643,7 +1663,8 @@ format_referred_r_entry_cb(Slapi_Entry *e, void *cbdata_ptr)
 	/* Note that we visited this entry. */
 	slapi_log_error(SLAPI_LOG_PLUGIN, cbdata->state->plugin_desc->spd_id,
 			"search matched entry \"%s\"\n", slapi_entry_get_dn(e));
-	format_add_sdn_list(cbdata->sdn_list, slapi_entry_get_dn(e));
+	format_add_sdn_list(cbdata->sdn_list, cbdata->sdn_list2,
+			    slapi_entry_get_dn(e));
 	sdn = slapi_entry_get_sdn(e);
 
 	/* If we're also being asked to pull values out of the entry... */
@@ -1704,6 +1725,7 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	int i, j, k, ret, argc, attrs_list_length;
 	Slapi_PBlock *local_pb;
 	Slapi_DN **these_bases, **next_bases, **these_entries, **next_entries;
+	Slapi_DN **these_entries2, **next_entries2;
 	struct berval **choices;
 	struct format_referred_r_entry_cbdata entry_cbdata;
 	struct format_ref_attr_list *list;
@@ -1780,6 +1802,7 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 			       &set_bases, &set_filter);
 	for (i = 0; (set_bases != NULL) && (set_bases[i] != NULL); i++) {
 		format_add_sdn_list(&(list->links[0].base_sdn_list),
+				    &(list->links[0].base_sdn_list2),
 				    set_bases[i]);
 	}
 	backend_free_set_config(set_bases, set_filter);
@@ -1790,6 +1813,7 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 		     (set_bases != NULL) && (set_bases[j] != NULL);
 		     j++) {
 			format_add_sdn_list(&(list->links[i + 1].base_sdn_list),
+					    &(list->links[i + 1].base_sdn_list2),
 					    set_bases[j]);
 		}
 		backend_free_set_config(set_bases, set_filter);
@@ -1798,9 +1822,12 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	/* Walk the chain, searching for entries which refer to entries at
 	 * this point in the chain. */
 	these_entries = NULL;
-	format_add_sdn_list(&these_entries, slapi_entry_get_dn(e));
+	these_entries2 = NULL;
+	format_add_sdn_list(&these_entries, &these_entries2,
+			    slapi_entry_get_dn(e));
 	choices = NULL;
 	next_entries = NULL;
+	next_entries2 = NULL;
 	attrs[0] = attr;
 	attrs[1] = NULL;
 	for (i = 0; i < list->n_links - 1; i++) {
@@ -1851,6 +1878,7 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 				entry_cbdata.attribute = attr;
 				entry_cbdata.choices = &choices;
 				entry_cbdata.sdn_list = &these_entries;
+				entry_cbdata.sdn_list2 = &these_entries2;
 				slapi_search_internal_callback_pb(local_pb,
 								  &entry_cbdata,
 								  NULL,
@@ -1889,6 +1917,7 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 				entry_cbdata.attribute = attr;
 				entry_cbdata.choices = &choices;
 				entry_cbdata.sdn_list = &next_entries;
+				entry_cbdata.sdn_list2 = &next_entries2;
 				slapi_search_internal_callback_pb(local_pb,
 								  &entry_cbdata,
 								  NULL,
@@ -1899,11 +1928,13 @@ format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 			free(tndn);
 		}
 		/* Set up for the next iteration. */
-		format_free_sdn_list(these_entries);
+		format_free_sdn_list(these_entries, these_entries2);
 		these_entries = next_entries;
+		these_entries2 = next_entries2;
 		next_entries = NULL;
+		next_entries2 = NULL;
 	}
-	format_free_sdn_list(these_entries);
+	format_free_sdn_list(these_entries, these_entries2);
 
 	slapi_pblock_destroy(local_pb);
 	format_free_parsed_args(argv);