config_entries: only keep track of a single entry list

Whenever adding a configuration entry to the config entries structure,
we allocate two list heads:

    - The first list head is added to the global list of config entries
      in order to be able to iterate over configuration entries in the
      order they were originally added.

    - The second list head is added to the map of entries in order to
      efficiently look up an entry by its name. If no entry with the
      same name exists in the map, then we add the new entry to the map
      directly. Otherwise, we append the new entry's list head to the
      pre-existing entry's list in order to keep track of multivars.

While the former usecase is perfectly sound, the second usecase can be
optimized. The only reason why we keep track of multivar entries in
another separate list is to be able to determine whether an entry is
unique or not by seeing whether its `next` pointer is set. So we keep
track of a complete list of multivar entries just to have a single bit
of information of whether it has other multivar entries with the same
entry name.

We can completely get rid of this secondary list by just adding a
`first` field to the list structure itself. When executing
`git_config_entries_append`, we will then simply check whether the
configuration map already has an entry with the same name -- if so, we
will set the `first` to zero to indicate that it is not the initial
entry anymore. Instead of a second list head in the map, we can thus now
directly store the list head of the first global list inside of the map
and just refer to that bit.

Note that the more obvious solution would be to store a `unique` field
instead of a `first` field. But as we will only ever inspect the `first`
field of the _last_ entry that has been moved into the map, these are
semantically equivalent in that case.

Having a `first` field also allows for a minor optimization: for
multivar values, we can free the `name` field of all entries that are
_not_ first and have them point to the name of the first entry instead.

1 files changed, 22 insertions, 73 deletions

diff --git a/src/config_entries.c b/src/config_entries.c
index 4a24006f4..2d6cab25d 100644
--- a/src/config_entries.c
+++ b/src/config_entries.c
@@ -11,6 +11,7 @@ typedef struct config_entry_list {
 	struct config_entry_list *next;
 	struct config_entry_list *last;
 	git_config_entry *entry;
+	bool first;
 } config_entry_list;
 
 typedef struct config_entries_iterator {
@@ -25,31 +26,6 @@ struct git_config_entries {
 	config_entry_list *list;
 };
 
-static void config_entry_list_free(config_entry_list *list)
-{
-	config_entry_list *next;
-
-	while (list != NULL) {
-		next = list->next;
-
-		git__free((char*) list->entry->name);
-		git__free((char *) list->entry->value);
-		git__free(list->entry);
-		git__free(list);
-
-		list = next;
-	};
-}
-
-static void config_entry_list_append(config_entry_list **list, config_entry_list *entry)
-{
-	if (*list)
-		(*list)->last->next = entry;
-	else
-		*list = entry;
-	(*list)->last = entry;
-}
-
 int git_config_entries_new(git_config_entries **out)
 {
 	git_config_entries *entries;
@@ -127,12 +103,14 @@ static void config_entries_free(git_config_entries *entries)
 {
 	config_entry_list *list = NULL, *next;
 
-	git_strmap_foreach_value(entries->map, list, config_entry_list_free(list));
 	git_strmap_free(entries->map);
 
 	list = entries->list;
 	while (list != NULL) {
 		next = list->next;
+		git__free((char *) list->entry->name);
+		git__free((char *) list->entry->value);
+		git__free(list->entry);
 		git__free(list);
 		list = next;
 	}
@@ -148,46 +126,21 @@ void git_config_entries_free(git_config_entries *entries)
 
 int git_config_entries_append(git_config_entries *entries, git_config_entry *entry)
 {
-	config_entry_list *existing, *var;
-	int error = 0;
-
-	var = git__calloc(1, sizeof(config_entry_list));
-	GIT_ERROR_CHECK_ALLOC(var);
-	var->entry = entry;
-
-	if ((existing = git_strmap_get(entries->map, entry->name)) == NULL) {
-		/*
-		 * We only ever inspect `last` from the first config
-		 * entry in a multivar. In case where this new entry is
-		 * the first one in the entry map, it will also be the
-		 * last one at the time of adding it, which is
-		 * why we set `last` here to itself. Otherwise we
-		 * do not have to set `last` and leave it set to
-		 * `NULL`.
-		 */
-		var->last = var;
-
-		error = git_strmap_set(entries->map, entry->name, var);
-	} else {
-		config_entry_list_append(&existing, var);
-	}
-
-	var = git__calloc(1, sizeof(config_entry_list));
-	GIT_ERROR_CHECK_ALLOC(var);
-	var->entry = entry;
-	config_entry_list_append(&entries->list, var);
-
-	return error;
-}
+	config_entry_list *head;
 
-static int config_entry_get(config_entry_list **out, git_config_entries *entries, const char *key)
-{
-	config_entry_list *list;
+	head = git__calloc(1, sizeof(config_entry_list));
+	GIT_ERROR_CHECK_ALLOC(head);
+	head->entry = entry;
+	head->first = (git_strmap_get(entries->map, entry->name) == NULL);
 
-	if ((list = git_strmap_get(entries->map, key)) == NULL)
-		return GIT_ENOTFOUND;
+	if (entries->list)
+		entries->list->last->next = head;
+	else
+		entries->list = head;
+	entries->list->last = head;
 
-	*out = list;
+	if (git_strmap_set(entries->map, entry->name, head) < 0)
+		return -1;
 
 	return 0;
 }
@@ -195,24 +148,20 @@ static int config_entry_get(config_entry_list **out, git_config_entries *entries
 int git_config_entries_get(git_config_entry **out, git_config_entries *entries, const char *key)
 {
 	config_entry_list *entry;
-	int error;
-
-	if ((error = config_entry_get(&entry, entries, key)) < 0)
-		return error;
-	*out = entry->last->entry;
-
+	if ((entry = git_strmap_get(entries->map, key)) == NULL)
+		return GIT_ENOTFOUND;
+	*out = entry->entry;
 	return 0;
 }
 
 int git_config_entries_get_unique(git_config_entry **out, git_config_entries *entries, const char *key)
 {
 	config_entry_list *entry;
-	int error;
 
-	if ((error = config_entry_get(&entry, entries, key)) < 0)
-		return error;
+	if ((entry = git_strmap_get(entries->map, key)) == NULL)
+		return GIT_ENOTFOUND;
 
-	if (entry->next != NULL) {
+	if (!entry->first) {
 		git_error_set(GIT_ERROR_CONFIG, "entry is not unique due to being a multivar");
 		return -1;
 	}