commit b36429aba0124d4bc92ec4dd7b285ace7abfcaee from: Stefan Sperling date: Mon Nov 05 00:44:27 2018 UTC reduce the amount of memcmp() calls via got_object_idset_add() 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;