ReactOS  0.4.13-dev-92-gf251225
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 
36 struct dictionary
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);
78  HeapFree(GetProcessHeap(), 0, p);
79  p = next;
80  }
81  HeapFree(GetProcessHeap(), 0, d);
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 
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  {
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;
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 }
void dictionary_remove(struct dictionary *d, const void *k)
Definition: dictionary.c:161
#define TRUE
Definition: types.h:120
void(* destroyfunc)(void *k, void *v, void *extra)
Definition: dictionary.h:40
BOOL dictionary_find(struct dictionary *d, const void *k, void **value)
Definition: dictionary.c:142
comparefunc comp
Definition: dictionary.c:38
UINT dictionary_num_entries(struct dictionary *d)
Definition: dictionary.c:85
destroyfunc destroy
Definition: dictionary.c:39
void dictionary_enumerate(struct dictionary *d, enumeratefunc e, void *closure)
Definition: dictionary.c:179
#define assert(x)
Definition: debug.h:53
struct dictionary * dictionary_create(comparefunc c, destroyfunc d, void *extra)
Definition: dictionary.c:45
struct dictionary_entry * next
Definition: dictionary.c:33
BOOL(* enumeratefunc)(const void *k, const void *v, void *extra, void *closure)
Definition: dictionary.h:45
unsigned int BOOL
Definition: ntddk_ex.h:94
#define e
Definition: ke_i.h:82
static size_t elem
Definition: string.c:68
smooth NULL
Definition: ftsmooth.c:416
static struct dictionary_entry ** dictionary_find_internal(struct dictionary *d, const void *k)
Definition: dictionary.c:95
int(* comparefunc)(const void *a, const void *b, void *extra)
Definition: dictionary.h:35
#define TRACE(s)
Definition: solgame.cpp:4
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
Definition: id3.c:18
#define d
Definition: ke_i.h:81
Definition: dictionary.c:29
const GLubyte * c
Definition: glext.h:8905
#define for
Definition: utility.h:88
int ret
void dictionary_insert(struct dictionary *d, const void *k, const void *v)
Definition: dictionary.c:113
struct dictionary_entry * head
Definition: dictionary.c:41
static unsigned __int64 next
Definition: rand_nt.c:6
const GLdouble * v
Definition: gl.h:2040
static calc_node_t temp
Definition: rpn_ieee.c:38
void dictionary_destroy(struct dictionary *d)
Definition: dictionary.c:65
unsigned int UINT
Definition: ndis.h:50
UINT num_entries
Definition: dictionary.c:42
struct define * next
Definition: wpp.c:35
void * value
Definition: dictionary.c:32
#define c
Definition: ke_i.h:80
void * key
Definition: dictionary.c:31
void * extra
Definition: dictionary.c:40
GLfloat GLfloat p
Definition: glext.h:8902
int k
Definition: mpi.c:3369
WINE_DEFAULT_DEBUG_CHANNEL(storage)
#define HeapFree(x, y, z)
Definition: compat.h:394