reactos/dll/win32/ole32/dictionary.c

   1 /* Simple dictionary implementation using a linked list.
   2  * FIXME: a skip list would be faster.
   3  *
   4  * Copyright 2005 Juan Lang
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  */
  20 #define WIN32_NO_STATUS
  21
  22 #include <assert.h>
  23 //#include <stdarg.h>
  24 //#include "windef.h"
  25 //#include "winbase.h"
  26 #include "dictionary.h"
  27 #include <wine/debug.h>
  28
  29 WINE_DEFAULT_DEBUG_CHANNEL(storage);
  30
  31 struct dictionary_entry
  32 {
  33     void *key;
  34     void *value;
  35     struct dictionary_entry *next;
  36 };
  37
  38 struct dictionary
  39 {
  40     comparefunc comp;
  41     destroyfunc destroy;
  42     void *extra;
  43     struct dictionary_entry *head;
  44     UINT num_entries;
  45 };
  46
  47 struct dictionary *dictionary_create(comparefunc c, destroyfunc d, void *extra)
  48 {
  49     struct dictionary *ret;
  50
  51     TRACE("(%p, %p, %p)\n", c, d, extra);
  52     if (!c)
  53         return NULL;
  54     ret = HeapAlloc(GetProcessHeap(), 0, sizeof(struct dictionary));
  55     if (ret)
  56     {
  57         ret->comp = c;
  58         ret->destroy = d;
  59         ret->extra = extra;
  60         ret->head = NULL;
  61         ret->num_entries = 0;
  62     }
  63     TRACE("returning %p\n", ret);
  64     return ret;
  65 }
  66
  67 void dictionary_destroy(struct dictionary *d)
  68 {
  69     TRACE("(%p)\n", d);
  70     if (d)
  71     {
  72         struct dictionary_entry *p;
  73
  74         for (p = d->head; p; )
  75         {
  76             struct dictionary_entry *next = p->next;
  77
  78             if (d->destroy)
  79                 d->destroy(p->key, p->value, d->extra);
  80             HeapFree(GetProcessHeap(), 0, p);
  81             p = next;
  82         }
  83         HeapFree(GetProcessHeap(), 0, d);
  84     }
  85 }
  86
  87 UINT dictionary_num_entries(struct dictionary *d)
  88 {
  89     return d ? d->num_entries : 0;
  90 }
  91
  92 /* Returns the address of the pointer to the node containing k.  (It returns
  93  * the address of either h->head or the address of the next member of the
  94  * prior node.  It's useful when you want to delete.)
  95  * Assumes h and prev are not NULL.
  96  */
  97 static struct dictionary_entry **dictionary_find_internal(struct dictionary *d,
  98  const void *k)
  99 {
 100     struct dictionary_entry **ret = NULL;
 101     struct dictionary_entry *p;
 102
 103     assert(d);
 104     /* special case for head containing the desired element */
 105     if (d->head && d->comp(k, d->head->key, d->extra) == 0)
 106         ret = &d->head;
 107     for (p = d->head; !ret && p && p->next; p = p->next)
 108     {
 109         if (d->comp(k, p->next->key, d->extra) == 0)
 110             ret = &p->next;
 111     }
 112     return ret;
 113 }
 114
 115 void dictionary_insert(struct dictionary *d, const void *k, const void *v)
 116 {
 117     struct dictionary_entry **prior;
 118
 119     TRACE("(%p, %p, %p)\n", d, k, v);
 120     if (!d)
 121         return;
 122     if ((prior = dictionary_find_internal(d, k)))
 123     {
 124         if (d->destroy)
 125             d->destroy((*prior)->key, (*prior)->value, d->extra);
 126         (*prior)->key = (void *)k;
 127         (*prior)->value = (void *)v;
 128     }
 129     else
 130     {
 131         struct dictionary_entry *elem = HeapAlloc(GetProcessHeap(), 0,
 132                                             sizeof(struct dictionary_entry));
 133
 134         if (!elem)
 135             return;
 136         elem->key = (void *)k;
 137         elem->value = (void *)v;
 138         elem->next = d->head;
 139         d->head = elem;
 140         d->num_entries++;
 141     }
 142 }
 143
 144 BOOL dictionary_find(struct dictionary *d, const void *k, void **value)
 145 {
 146     struct dictionary_entry **prior;
 147     BOOL ret = FALSE;
 148
 149     TRACE("(%p, %p, %p)\n", d, k, value);
 150     if (!d)
 151         return FALSE;
 152     if (!value)
 153         return FALSE;
 154     if ((prior = dictionary_find_internal(d, k)))
 155     {
 156         *value = (*prior)->value;
 157         ret = TRUE;
 158     }
 159     TRACE("returning %d (%p)\n", ret, *value);
 160     return ret;
 161 }
 162
 163 void dictionary_remove(struct dictionary *d, const void *k)
 164 {
 165     struct dictionary_entry **prior, *temp;
 166
 167     TRACE("(%p, %p)\n", d, k);
 168     if (!d)
 169         return;
 170     if ((prior = dictionary_find_internal(d, k)))
 171     {
 172         temp = *prior;
 173         if (d->destroy)
 174             d->destroy((*prior)->key, (*prior)->value, d->extra);
 175         *prior = (*prior)->next;
 176         HeapFree(GetProcessHeap(), 0, temp);
 177         d->num_entries--;
 178     }
 179 }
 180
 181 void dictionary_enumerate(struct dictionary *d, enumeratefunc e, void *closure)
 182 {
 183     struct dictionary_entry *p;
 184
 185     TRACE("(%p, %p, %p)\n", d, e, closure);
 186     if (!d)
 187         return;
 188     if (!e)
 189         return;
 190     for (p = d->head; p; p = p->next)
 191         if (!e(p->key, p->value, d->extra, closure))
 192             break;
 193 }