wined3d: Don't record dirty areas in a readonly lock.
[wine] / 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 = HeapAlloc(GetProcessHeap(), 0,
130                                             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 }