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 }
192
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.