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

[Clément Bœsch]

On Sun, Apr 14, 2013 at 03:07:58AM +0200, Clément Bœsch wrote:
> ---
>  libavutil/dict.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 84 insertions(+), 9 deletions(-)
> 

New version fixing a bug with av_dict_set and value=NULL

-- 
Clément B.
-------------- next part --------------
From a4b09dd6703b1f73bff3fcce15f8ef55946ecee4 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Cl=C3=A9ment=20B=C5=93sch?= <ubitux at gmail.com>
Date: Sun, 14 Apr 2013 03:05:00 +0200
Subject: [PATCH 5/5] lavu/dict: add hashtable index.

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

diff --git a/libavutil/dict.c b/libavutil/dict.c
index 7a92c56..99af10f 100644
--- a/libavutil/dict.c
+++ b/libavutil/dict.c
@@ -25,37 +25,76 @@
 #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;
+
+    for (node = m->hashtable[get_hash(key)]; node; node = node->next)
+        if (!entry_cmp(m->elems[node->array_id].key, key, flags))
+            return node;
+    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;
 }
 
@@ -69,8 +108,28 @@ int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags
         m = *pm = av_mallocz(sizeof(*m));
 
     if(tag) {
+        uint32_t id;
+        struct node *node, *ref_to_last, *prev = NULL;
+
         if (flags & AV_DICT_DONT_OVERWRITE)
             return 0;
+
+        /* make the reference to the last entry in the array (ref_to_last)
+         * focus on the array id of tag (last entry is going to move in place
+         * of tag, and tag will be recreated later at the end of the array if
+         * value is !NULL), and drop the reference to the current entry */
+        id = get_hash(key);
+        for (node = m->hashtable[id]; node; node = node->next) {
+            if (!entry_cmp(m->elems[node->array_id].key, key, flags))
+                break;
+            prev = node;
+        }
+        ref_to_last = get_node(m, m->elems[m->count - 1].key, flags);
+        ref_to_last->array_id = node->array_id;
+        if (!prev) m->hashtable[id] = node->next;
+        else       prev->next       = node->next;
+        av_freep(&node);
+
         if (flags & AV_DICT_APPEND)
             oldval = tag->value;
         else
@@ -83,6 +142,7 @@ int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags
         m->count--;
     }
     if (value) {
+        struct node **index, *node;
         AVDictionaryEntry *e = &m->elems[m->count++];
 
         if (flags & AV_DICT_DONT_STRDUP_KEY) {
@@ -102,6 +162,15 @@ int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags
             e->value = newval;
         } else
             e->value = av_strdup(value);
+
+        /* reference the entry in the hash table */
+        index = &m->hashtable[get_hash(e->key)];
+        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 +232,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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 490 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20130414/67507505/attachment.asc>