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