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