dlls/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 #include <assert.h>
  21 #include <stdarg.h>
  22 #include "windef.h"
  23 #include "winbase.h"
  24 #include "dictionary.h"
  25 #include "wine/debug.h"
  26
  27 WINE_DEFAULT_DEBUG_CHANNEL(storage);
  28
  29 struct dictionary_entry
  30 {
  31     void *key;
  32     void *value;
  33     struct dictionary_entry *next;
  34 };
  35
  36 struct dictionary
  37 {
  38     comparefunc comp;
  39     destroyfunc destroy;
  40     void *extra;
  41     struct dictionary_entry *head;
  42     UINT num_entries;
  43 };
  44
  45 struct dictionary *dictionary_create(comparefunc c, destroyfunc d, void *extra)
  46 {
  47     struct dictionary *ret;
  48
  49     TRACE("(%p, %p, %p)\n", c, d, extra);
  50     if (!c)
  51         return NULL;
  52     ret = HeapAlloc(GetProcessHeap(), 0, sizeof(struct dictionary));
  53     if (ret)
  54     {
  55         ret->comp = c;
  56         ret->destroy = d;
  57         ret->extra = extra;
  58         ret->head = NULL;
  59         ret->num_entries = 0;
  60     }
  61     TRACE("returning %p\n", ret);
  62     return ret;
  63 }
  64
  65 void dictionary_destroy(struct dictionary *d)
  66 {
  67     TRACE("(%p)\n", d);
  68     if (d)
  69     {
  70         struct dictionary_entry *p;
  71
  72         for (p = d->head; p; )
  73         {
  74             struct dictionary_entry *next = p->next;
  75
  76             if (d->destroy)
  77                 d->destroy(p->key, p->value, d->extra);
  78             HeapFree(GetProcessHeap(), 0, p);
  79             p = next;
  80         }
  81         HeapFree(GetProcessHeap(), 0, d);
  82     }
  83 }
  84
  85 UINT dictionary_num_entries(struct dictionary *d)
  86 {
  87     return d ? d->num_entries : 0;
  88 }
  89
  90 /* Returns the address of the pointer to the node containing k.  (It returns
  91  * the address of either h->head or the address of the next member of the
  92  * prior node.  It's useful when you want to delete.)
  93  * Assumes h and prev are not NULL.
  94  */
  95 static struct dictionary_entry **dictionary_find_internal(struct dictionary *d,
  96  const void *k)
  97 {
  98     struct dictionary_entry **ret = NULL;
  99     struct dictionary_entry *p;
 100
 101     assert(d);
 102     /* special case for head containing the desired element */
 103     if (d->head && d->comp(k, d->head->key, d->extra) == 0)
 104         ret = &d->head;
 105     for (p = d->head; !ret && p && p->next; p = p->next)
 106     {
 107         if (d->comp(k, p->next->key, d->extra) == 0)
 108             ret = &p->next;
 109     }
 110     return ret;
 111 }
 112
 113 void dictionary_insert(struct dictionary *d, const void *k, const void *v)
 114 {
 115     struct dictionary_entry **prior;
 116
 117     TRACE("(%p, %p, %p)\n", d, k, v);
 118     if (!d)
 119         return;
 120     if ((prior = dictionary_find_internal(d, k)))
 121     {
 122         if (d->destroy)
 123             d->destroy((*prior)->key, (*prior)->value, d->extra);
 124         (*prior)->key = (void *)k;
 125         (*prior)->value = (void *)v;
 126     }
 127     else
 128     {
 129         struct dictionary_entry *elem = (struct dictionary_entry *)
 130          HeapAlloc(GetProcessHeap(), 0, sizeof(struct dictionary_entry));
 131
 132         if (!elem)
 133             return;
 134         elem->key = (void *)k;
 135         elem->value = (void *)v;
 136         elem->next = d->head;
 137         d->head = elem;
 138         d->num_entries++;
 139     }
 140 }
 141
 142 BOOL dictionary_find(struct dictionary *d, const void *k, void **value)
 143 {
 144     struct dictionary_entry **prior;
 145     BOOL ret = FALSE;
 146
 147     TRACE("(%p, %p, %p)\n", d, k, value);
 148     if (!d)
 149         return FALSE;
 150     if (!value)
 151         return FALSE;
 152     if ((prior = dictionary_find_internal(d, k)))
 153     {
 154         *value = (*prior)->value;
 155         ret = TRUE;
 156     }
 157     TRACE("returning %d (%p)\n", ret, *value);
 158     return ret;
 159 }
 160
 161 void dictionary_remove(struct dictionary *d, const void *k)
 162 {
 163     struct dictionary_entry **prior, *temp;
 164
 165     TRACE("(%p, %p)\n", d, k);
 166     if (!d)
 167         return;
 168     if ((prior = dictionary_find_internal(d, k)))
 169     {
 170         temp = *prior;
 171         if (d->destroy)
 172             d->destroy((*prior)->key, (*prior)->value, d->extra);
 173         *prior = (*prior)->next;
 174         HeapFree(GetProcessHeap(), 0, temp);
 175         d->num_entries--;
 176     }
 177 }
 178
 179 void dictionary_enumerate(struct dictionary *d, enumeratefunc e, void *closure)
 180 {
 181     struct dictionary_entry *p;
 182
 183     TRACE("(%p, %p, %p)\n", d, e, closure);
 184     if (!d)
 185         return;
 186     if (!e)
 187         return;
 188     for (p = d->head; p; p = p->next)
 189         if (!e(p->key, p->value, d->extra, closure))
 190             break;
 191 }