Commit 62320860b1210d1645d15c185c575d265601cb5a
2019-09-26T14:43:19
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
diff --git a/src/config_entries.c b/src/config_entries.c
index 4a24006..2d6cab2 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;
}