ReactOS 0.4.15-dev-8109-gd7be748
dictionary.c
Go to the documentation of this file.
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
28
30{
31 void *key;
32 void *value;
34};
35
37{
40 void *extra;
43};
44
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
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);
79 p = next;
80 }
82 }
83}
84
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 */
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
113void 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 {
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
142BOOL 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
161void 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;
175 d->num_entries--;
176 }
177}
178
179void 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}
#define WINE_DEFAULT_DEBUG_CHANNEL(t)
Definition: precomp.h:23
BOOL(* enumeratefunc)(const void *k, const void *v, void *extra, void *closure)
Definition: dictionary.h:45
void(* destroyfunc)(void *k, void *v, void *extra)
Definition: dictionary.h:40
int(* comparefunc)(const void *a, const void *b, void *extra)
Definition: dictionary.h:35
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define GetProcessHeap()
Definition: compat.h:736
#define HeapAlloc
Definition: compat.h:733
#define HeapFree(x, y, z)
Definition: compat.h:735
BOOL dictionary_find(struct dictionary *d, const void *k, void **value)
Definition: dictionary.c:142
void dictionary_enumerate(struct dictionary *d, enumeratefunc e, void *closure)
Definition: dictionary.c:179
void dictionary_remove(struct dictionary *d, const void *k)
Definition: dictionary.c:161
static struct dictionary_entry ** dictionary_find_internal(struct dictionary *d, const void *k)
Definition: dictionary.c:95
void dictionary_destroy(struct dictionary *d)
Definition: dictionary.c:65
void dictionary_insert(struct dictionary *d, const void *k, const void *v)
Definition: dictionary.c:113
struct dictionary * dictionary_create(comparefunc c, destroyfunc d, void *extra)
Definition: dictionary.c:45
UINT dictionary_num_entries(struct dictionary *d)
Definition: dictionary.c:85
#define assert(x)
Definition: debug.h:53
unsigned int BOOL
Definition: ntddk_ex.h:94
const GLdouble * v
Definition: gl.h:2040
const GLubyte * c
Definition: glext.h:8905
GLfloat GLfloat p
Definition: glext.h:8902
@ extra
Definition: id3.c:95
#define d
Definition: ke_i.h:81
#define e
Definition: ke_i.h:82
#define c
Definition: ke_i.h:80
static size_t elem
Definition: string.c:68
int k
Definition: mpi.c:3369
unsigned int UINT
Definition: ndis.h:50
static unsigned __int64 next
Definition: rand_nt.c:6
static calc_node_t temp
Definition: rpn_ieee.c:38
#define TRACE(s)
Definition: solgame.cpp:4
struct define * next
Definition: compiler.c:65
Definition: dictionary.c:30
struct dictionary_entry * next
Definition: dictionary.c:33
void * key
Definition: dictionary.c:31
void * value
Definition: dictionary.c:32
comparefunc comp
Definition: dictionary.c:38
UINT num_entries
Definition: dictionary.c:42
struct dictionary_entry * head
Definition: dictionary.c:41
destroyfunc destroy
Definition: dictionary.c:39
void * extra
Definition: dictionary.c:40
Definition: pdh_main.c:94
int ret