[FFmpeg-devel] [PATCH 5/5] lavu/dict: add hashtable index.

[Clément Bœsch]

---
 libavutil/dict.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 84 insertions(+), 9 deletions(-)

diff --git a/libavutil/dict.c b/libavutil/dict.c
index 7a92c56..fd1176c 100644
--- a/libavutil/dict.c
+++ b/libavutil/dict.c
@@ -25,37 +25,78 @@
 #include "internal.h"
 #include "mem.h"
 
+#define HASH_TABLE_LEN 512
+
+struct node {
+    int array_id;
+    struct node *next;
+};
+
 struct AVDictionary {
     int count;
     AVDictionaryEntry *elems;
+    struct node *hashtable[HASH_TABLE_LEN];
 };
 
+static uint32_t get_hash(const char *key)
+{
+    uint32_t hash = 0;
+    while (*key)
+        hash = (hash<<5) ^ (hash>>27) ^ av_toupper(*key++);
+    return hash % HASH_TABLE_LEN;
+}
+
 int av_dict_count(const AVDictionary *m)
 {
     return m ? m->count : 0;
 }
 
+static inline int entry_cmp(const char *s, const char *key, int flags)
+{
+    unsigned i;
+
+    if(flags & AV_DICT_MATCH_CASE) for(i=0;            s[i]  ==            key[i]  && key[i]; i++);
+    else                           for(i=0; av_toupper(s[i]) == av_toupper(key[i]) && key[i]; i++);
+    if(key[i])
+        return -1;
+    if(s[i] && !(flags & AV_DICT_IGNORE_SUFFIX))
+        return -1;
+    return 0;
+}
+
+static inline struct node *get_node(const AVDictionary *m, const char *key, int flags)
+{
+    struct node *node = m->hashtable[get_hash(key)];
+
+    while (node) {
+        if (!entry_cmp(m->elems[node->array_id].key, key, flags))
+            return node;
+        node = node->next;
+    }
+    return NULL;
+}
+
 AVDictionaryEntry *
 av_dict_get(AVDictionary *m, const char *key, const AVDictionaryEntry *prev, int flags)
 {
-    unsigned int i, j;
-
     if(!m)
         return NULL;
 
+    if(prev || (flags & AV_DICT_IGNORE_SUFFIX)){
+        unsigned i;
+    /* TODO: reindent */
     if(prev) i= prev - m->elems + 1;
     else     i= 0;
 
     for(; i<m->count; i++){
-        const char *s= m->elems[i].key;
-        if(flags & AV_DICT_MATCH_CASE) for(j=0;            s[j]  ==            key[j]  && key[j]; j++);
-        else                           for(j=0; av_toupper(s[j]) == av_toupper(key[j]) && key[j]; j++);
-        if(key[j])
-            continue;
-        if(s[j] && !(flags & AV_DICT_IGNORE_SUFFIX))
-            continue;
+        if(!entry_cmp(m->elems[i].key, key, flags))
         return &m->elems[i];
     }
+    }else{
+        const struct node *node = get_node(m, key, flags);
+        if(node)
+            return &m->elems[node->array_id];
+    }
     return NULL;
 }
 
@@ -64,13 +105,27 @@ int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags
     AVDictionary      *m = *pm;
     AVDictionaryEntry *tag = av_dict_get(m, key, NULL, flags);
     char *oldval = NULL;
+    int add_index_entry = 1;
 
     if(!m)
         m = *pm = av_mallocz(sizeof(*m));
 
     if(tag) {
+        int old_id;
+        struct node *node;
+
         if (flags & AV_DICT_DONT_OVERWRITE)
             return 0;
+
+        /* entry already exists: that one and the last one in the array will be
+         * toggled, so the hashtable needs some adjustments as well. */
+        add_index_entry = 0;
+        node = get_node(m, tag->key, flags);
+        old_id = node->array_id;
+        node->array_id = m->count - 1;
+        node = get_node(m, m->elems[m->count - 1].key, flags);
+        node->array_id = old_id;
+
         if (flags & AV_DICT_APPEND)
             oldval = tag->value;
         else
@@ -102,6 +157,16 @@ int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags
             e->value = newval;
         } else
             e->value = av_strdup(value);
+
+        if (add_index_entry) {
+            struct node **index = &m->hashtable[get_hash(e->key)];
+            struct node *node = av_mallocz(sizeof(*node));
+            if (!node)
+                return AVERROR(ENOMEM);
+            node->array_id = m->count - 1;
+            node->next = *index;
+            *index = node;
+        }
     }
     if (!m->count) {
         av_free(m->elems);
@@ -163,10 +228,20 @@ void av_dict_free(AVDictionary **pm)
     AVDictionary *m = *pm;
 
     if (m) {
+        unsigned i;
+
         while(m->count--) {
             av_free(m->elems[m->count].key);
             av_free(m->elems[m->count].value);
         }
+        for (i = 0; i < HASH_TABLE_LEN; i++) {
+            struct node *tmp, *node = m->hashtable[i];
+            while (node) {
+                tmp = node;
+                node = node->next;
+                av_freep(&tmp);
+            }
+        }
         av_free(m->elems);
     }
     av_freep(pm);
-- 
1.8.2.1