Commit Diff

Commit:
b36429aba0124d4bc92ec4dd7b285ace7abfcaee
From:
Stefan Sperling <stsp@stsp.name>
Date:
Message:
reduce the amount of memcmp() calls via got_object_idset_add()
Actions:
Patch | Tree
commit - fd1d2703b833d6456b44614e09f14e3f8d7a826c
commit + b36429aba0124d4bc92ec4dd7b285ace7abfcaee
blob - da78aa18feeb760a6cb864f8a604b5ac2ccb3cad
blob + d0e80bc31edd85aea3d8e095d680ea7b47a23d0c
--- lib/commit_graph.c
+++ lib/commit_graph.c
@@ -289,11 +289,8 @@ advance_branch(struct got_commit_graph *graph,
 		qid = SIMPLEQ_FIRST(&commit->parent_ids);
 		if (qid == NULL)
 			return NULL;
-		err = got_object_idset_add(NULL, graph->open_branches, qid->id,
-		    node);
-		if (err && err->code != GOT_ERR_OBJ_EXISTS)
-			return err;
-		return NULL;
+		err = got_object_idset_add(graph->open_branches, qid->id, node);
+		return err;
 	}
 
 	/*
@@ -335,11 +332,9 @@ advance_branch(struct got_commit_graph *graph,
 			 * skip any other branches.
 			 */
 			if (got_object_id_cmp(merged_id, id) == 0) {
-				err = got_object_idset_add(NULL,
-				    graph->open_branches, qid->id, node);
-				if (err && err->code != GOT_ERR_OBJ_EXISTS)
-					return err;
-				return NULL;
+				err = got_object_idset_add(graph->open_branches,
+				    qid->id, node);
+				return err;
 			}
 		}
 
@@ -353,20 +348,20 @@ advance_branch(struct got_commit_graph *graph,
 				return NULL;
 			if (got_object_idset_get(graph->node_ids, qid->id))
 				return NULL; /* parent already traversed */
-			err = got_object_idset_add(NULL,
-			    graph->open_branches, qid->id, node);
-			if (err && err->code != GOT_ERR_OBJ_EXISTS)
-				return err;
-			return NULL;
+			if (got_object_idset_get(graph->open_branches, qid->id))
+				return NULL;
+			return got_object_idset_add(graph->open_branches,
+			    qid->id, node);
 		}
 	}
 
 	SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
 		if (got_object_idset_get(graph->node_ids, qid->id))
 			continue; /* parent already traversed */
-		err = got_object_idset_add(NULL, graph->open_branches,
-		    qid->id, node);
-		if (err && err->code != GOT_ERR_OBJ_EXISTS)
+		if (got_object_idset_get(graph->open_branches, qid->id))
+			continue;
+		err = got_object_idset_add(graph->open_branches, qid->id, node);
+		if (err)
 			return err;
 	}
 
@@ -412,10 +407,8 @@ add_node(struct got_commit_graph_node **new_node,
 		node->nparents++;
 	}
 
-	err = got_object_idset_add(NULL, graph->node_ids, &node->id, node);
+	err = got_object_idset_add(graph->node_ids, &node->id, node);
 	if (err) {
-		if (err->code == GOT_ERR_OBJ_EXISTS)
-			err = NULL;
 		free_node(node);
 		return err;
 	}
blob - a64e2b70f7d72a371e595432714264b0131f81a6
blob + aad920423825b71bc7a553e2af26982b93bed2f0
--- lib/got_lib_object_idset.h
+++ lib/got_lib_object_idset.h
@@ -19,8 +19,8 @@ struct got_object_idset;
 struct got_object_idset *got_object_idset_alloc(void);
 void got_object_idset_free(struct got_object_idset *);
 
-const struct got_error *got_object_idset_add(void **,
-    struct got_object_idset *, struct got_object_id *, void *);
+const struct got_error *got_object_idset_add(struct got_object_idset *,
+    struct got_object_id *, void *);
 void *got_object_idset_get(struct got_object_idset *, struct got_object_id *);
 const struct got_error *got_object_idset_remove(void **,
     struct got_object_idset *, struct got_object_id *);
blob - a2cbeccda124c5640483869d7736a983a3610b2b
blob + d61195221dd0e6e48a7d3cb654327b0fff7c2a19
--- lib/object_idset.c
+++ lib/object_idset.c
@@ -88,15 +88,12 @@ got_object_idset_free(struct got_object_idset *set)
 }
 
 const struct got_error *
-got_object_idset_add(void **existing_data,
-    struct got_object_idset *set, struct got_object_id *id, void *data)
+got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
+    void *data)
 {
-	struct got_object_idset_element *new, *entry;
+	struct got_object_idset_element *new;
 	uint8_t i = id->sha1[0];
 
-	if (existing_data)
-		*existing_data = NULL;
-
 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
 		return got_error(GOT_ERR_NO_SPACE);
 
@@ -107,43 +104,10 @@ got_object_idset_add(void **existing_data,
 	memcpy(&new->id, id, sizeof(new->id));
 	new->data = data;
 
-	if (TAILQ_EMPTY(&set->entries[i])) {
-		TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
-		set->nelem[i]++;
-		set->totelem++;
-		return NULL;
-	}
-
-	/*
-	 * Keep the list sorted by ID so that iterations of
-	 * the set occur in a predictable order.
-	 */
-	TAILQ_FOREACH(entry, &set->entries[i], entry) {
-		int cmp = got_object_id_cmp(&new->id, &entry->id);
-		struct got_object_idset_element *next;
-
-		if (cmp == 0) {
-			free(new);
-			if (existing_data)
-				*existing_data = entry->data;
-			return got_error(GOT_ERR_OBJ_EXISTS);
-		} else if (cmp < 0) {
-			TAILQ_INSERT_BEFORE(entry, new, entry);
-			set->nelem[i]++;
-			set->totelem++;
-			return NULL;
-		}
-
-		next = TAILQ_NEXT(entry, entry);
-		if (next == NULL) {
-			TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
-			set->nelem[i]++;
-			set->totelem++;
-			return NULL;
-		}
-	}
-
-	return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
+	TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
+	set->nelem[i]++;
+	set->totelem++;
+	return NULL;
 }
 
 void *
blob - 7d0f1de6e8cf560b249da09dd3332bcf8bfa4f6e
blob + a3971bd5c547500d7cbab66beb3118d1d59f4169
--- regress/idset/idset_test.c
+++ regress/idset/idset_test.c
@@ -54,17 +54,13 @@ static const char *id_str2 = "222222222222222222222222
 static const char *id_str3 = "ffffffffffffffffffffffffffffffffffffffff";
 static struct got_object_id id1, id2, id3;
 static const char *data1 = "data1", *data2 = "data2", *data3 = "data3";
-static int iter_count;
 
 static void
 idset_cb(struct got_object_id *id, void *data, void *arg) {
-	if (iter_count == 0 &&
-	    (got_object_id_cmp(id, &id1) != 0 || data != (void *)data1))
-		abort();
-	if (iter_count == 1 &&
-	    (got_object_id_cmp(id, &id3) != 0 || data != (void *)data3))
-		abort();
-	iter_count++;
+	if ((got_object_id_cmp(id, &id1) == 0 && data == (void *)data1) ||
+	    (got_object_id_cmp(id, &id3) == 0 && data == (void *)data3))
+		return;
+	abort();
 }
 
 static int
@@ -72,7 +68,6 @@ idset_add_remove_iter(void)
 {
 	const struct got_error *err = NULL;
 	struct got_object_idset *set;
-	void *existing_data;
 
 	set = got_object_idset_alloc();
 	if (set == NULL) {
@@ -97,13 +92,9 @@ idset_add_remove_iter(void)
 		goto done;
 	}
 
-	err = got_object_idset_add(&existing_data, set, &id1, (void *)data1);
+	err = got_object_idset_add(set, &id1, (void *)data1);
 	if (err)
 		goto done;
-	if (existing_data != NULL) {
-		err = got_error(GOT_ERR_BAD_OBJ_DATA);
-		goto done;
-	}
 	if (got_object_idset_num_elements(set) != 1) {
 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
 		goto done;
@@ -114,24 +105,9 @@ idset_add_remove_iter(void)
 		goto done;
 	}
 
-	err = got_object_idset_add(&existing_data, set, &id2, (void *)data2);
+	err = got_object_idset_add(set, &id2, (void *)data2);
 	if (err)
 		goto done;
-	if (existing_data != NULL) {
-		err = got_error(GOT_ERR_BAD_OBJ_DATA);
-		goto done;
-	}
-	err = got_object_idset_add(&existing_data, set, &id2, NULL);
-	if (existing_data == NULL) {
-		err = got_error(GOT_ERR_BAD_OBJ_DATA);
-		goto done;
-	}
-	if (err->code != GOT_ERR_OBJ_EXISTS)
-		goto done;
-	err = got_object_idset_add(NULL, set, &id2, NULL);
-	if (err->code != GOT_ERR_OBJ_EXISTS)
-		goto done;
-	err = NULL;
 
 	if (!got_object_idset_contains(set, &id1)) {
 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
@@ -146,7 +122,7 @@ idset_add_remove_iter(void)
 		goto done;
 	}
 
-	err = got_object_idset_add(NULL, set, &id3, (void *)data3);
+	err = got_object_idset_add(set, &id3, (void *)data3);
 	if (err)
 		goto done;