Kannel: Open Source WAP and SMS gateway  $Revision: 5037 $
dict.c
Go to the documentation of this file.
1 /* ====================================================================
2  * The Kannel Software License, Version 1.0
3  *
4  * Copyright (c) 2001-2016 Kannel Group
5  * Copyright (c) 1998-2001 WapIT Ltd.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Kannel Group (http://www.kannel.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Kannel" and "Kannel Group" must not be used to
28  * endorse or promote products derived from this software without
29  * prior written permission. For written permission, please
30  * contact org@kannel.org.
31  *
32  * 5. Products derived from this software may not be called "Kannel",
33  * nor may "Kannel" appear in their name, without prior written
34  * permission of the Kannel Group.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS
40  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
41  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
42  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
43  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
44  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
45  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
46  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  *
49  * This software consists of voluntary contributions made by many
50  * individuals on behalf of the Kannel Group. For more information on
51  * the Kannel Group, please see <http://www.kannel.org/>.
52  *
53  * Portions of this software are based upon software originally written at
54  * WapIT Ltd., Helsinki, Finland for the Kannel project.
55  */
56 
57 /*
58  * dict.c - lookup data structure using octet strings as keys
59  *
60  * The Dict is implemented as a simple hash table. In the future, it
61  * might be interesting to use a trie instead.
62  *
63  * Lars Wirzenius, based on code by Tuomas Luttinen
64  */
65 
66 
67 #include "gwlib.h"
68 
69 
70 /*
71  * The hash table stores key/value -pairs in a List.
72  */
73 
74 typedef struct Item Item;
75 struct Item {
77  void *value;
78 };
79 
80 
81 static Item *item_create(Octstr *key, void *value)
82 {
83  Item *item;
84 
85  item = gw_malloc(sizeof(*item));
86  item->key = octstr_duplicate(key);
87  item->value = value;
88  return item;
89 }
90 
91 static void item_destroy(void *item)
92 {
93  Item *p;
94 
95  p = item;
96  octstr_destroy(p->key);
97  gw_free(p);
98 }
99 
100 
101 static int item_has_key(void *item, void *key)
102 {
103  return octstr_compare(key, ((Item *) item)->key) == 0;
104 }
105 
106 
107 /*
108  * The dictionary itself is a very simple hash table.
109  * `tab' is an array of Lists of Items, in which empty Lists may be
110  * represented as NULL. `size' is the number of elements allocated
111  * for the array, and `key_count' is the number of Items currently
112  * in the table. `key_count' is kept up to date by the put and remove
113  * functions, and is used to make dict_key_count() faster.
114  */
115 
116 struct Dict {
118  long size;
119  long key_count;
120  void (*destroy_value)(void *);
122 };
123 
124 
125 static void lock(Dict *dict)
126 {
127  mutex_lock(dict->lock);
128 }
129 
130 
131 static void unlock(Dict *dict)
132 {
133  mutex_unlock(dict->lock);
134 }
135 
136 
137 static long key_to_index(Dict *dict, Octstr *key)
138 {
139  return octstr_hash_key(key) % dict->size;
140 }
141 
142 static int handle_null_value(Dict *dict, Octstr *key, void *value)
143 {
144  if (value == NULL) {
145  value = dict_remove(dict, key);
146  if (dict->destroy_value != NULL)
147  dict->destroy_value(value);
148  return 1;
149  }
150 
151  return 0;
152 }
153 
154 static int dict_put_true(Dict *dict, Octstr *key, void *value)
155 {
156  Item *p;
157  long i;
158  int item_unique;
159 
160  item_unique = 0;
161  lock(dict);
162  i = key_to_index(dict, key);
163 
164  if (dict->tab[i] == NULL) {
165  dict->tab[i] = gwlist_create();
166  p = NULL;
167  } else {
168  p = gwlist_search(dict->tab[i], key, item_has_key);
169  }
170 
171  if (p == NULL) {
172  p = item_create(key, value);
173  gwlist_append(dict->tab[i], p);
174  dict->key_count++;
175  item_unique = 1;
176  } else {
177  if (dict->destroy_value != NULL)
178  dict->destroy_value(value);
179  item_unique = 0;
180  }
181 
182  unlock(dict);
183 
184  return item_unique;
185 }
186 
187 /*
188  * And finally, the public functions.
189  */
190 
191 
192 Dict *dict_create(long size_hint, void (*destroy_value)(void *))
193 {
194  Dict *dict;
195  long i;
196 
197  dict = gw_malloc(sizeof(*dict));
198 
199  /*
200  * Hash tables tend to work well until they are fill to about 50%.
201  */
202  dict->size = size_hint * 2;
203 
204  dict->tab = gw_malloc(sizeof(dict->tab[0]) * dict->size);
205  for (i = 0; i < dict->size; ++i)
206  dict->tab[i] = NULL;
207  dict->lock = mutex_create();
208  dict->destroy_value = destroy_value;
209  dict->key_count = 0;
210 
211  return dict;
212 }
213 
214 
215 void dict_destroy(Dict *dict)
216 {
217  long i;
218  Item *p;
219 
220  if (dict == NULL)
221  return;
222 
223  for (i = 0; i < dict->size; ++i) {
224  if (dict->tab[i] == NULL)
225  continue;
226 
227  while ((p = gwlist_extract_first(dict->tab[i])) != NULL) {
228  if (dict->destroy_value != NULL)
229  dict->destroy_value(p->value);
230  item_destroy(p);
231  }
232  gwlist_destroy(dict->tab[i], NULL);
233  }
234  mutex_destroy(dict->lock);
235  gw_free(dict->tab);
236  gw_free(dict);
237 }
238 
239 
240 void dict_put(Dict *dict, Octstr *key, void *value)
241 {
242  long i;
243  Item *p;
244 
245  if (value == NULL) {
246  value = dict_remove(dict, key);
247  if (dict->destroy_value != NULL)
248  dict->destroy_value(value);
249  return;
250  }
251 
252  lock(dict);
253  i = key_to_index(dict, key);
254  if (dict->tab[i] == NULL) {
255  dict->tab[i] = gwlist_create();
256  p = NULL;
257  } else
258  p = gwlist_search(dict->tab[i], key, item_has_key);
259  if (p == NULL) {
260  p = item_create(key, value);
261  gwlist_append(dict->tab[i], p);
262  dict->key_count++;
263  } else {
264  if (dict->destroy_value != NULL)
265  dict->destroy_value(p->value);
266  p->value = value;
267  }
268  unlock(dict);
269 }
270 
271 int dict_put_once(Dict *dict, Octstr *key, void *value)
272 {
273  int ret;
274 
275  ret = 1;
276  if (handle_null_value(dict, key, value))
277  return 1;
278  if (dict_put_true(dict, key, value)) {
279  ret = 1;
280  } else {
281  ret = 0;
282  }
283  return ret;
284 }
285 
286 void *dict_get(Dict *dict, Octstr *key)
287 {
288  long i;
289  Item *p;
290  void *value;
291 
292  lock(dict);
293  i = key_to_index(dict, key);
294  if (dict->tab[i] == NULL)
295  p = NULL;
296  else
297  p = gwlist_search(dict->tab[i], key, item_has_key);
298  if (p == NULL)
299  value = NULL;
300  else
301  value = p->value;
302  unlock(dict);
303  return value;
304 }
305 
306 
307 void *dict_remove(Dict *dict, Octstr *key)
308 {
309  long i;
310  Item *p;
311  void *value;
312  List *list;
313 
314  lock(dict);
315  i = key_to_index(dict, key);
316  if (dict->tab[i] == NULL)
317  list = NULL;
318  else
319  list = gwlist_extract_matching(dict->tab[i], key, item_has_key);
320  gw_assert(list == NULL || gwlist_len(list) == 1);
321  if (list == NULL)
322  value = NULL;
323  else {
324  p = gwlist_get(list, 0);
325  gwlist_destroy(list, NULL);
326  value = p->value;
327  item_destroy(p);
328  dict->key_count--;
329  }
330  unlock(dict);
331  return value;
332 }
333 
334 
335 long dict_key_count(Dict *dict)
336 {
337  long result;
338 
339  lock(dict);
340  result = dict->key_count;
341  unlock(dict);
342 
343  return result;
344 }
345 
346 
348 {
349  List *list;
350  Item *item;
351  long i, j;
352 
353  list = gwlist_create();
354 
355  lock(dict);
356  for (i = 0; i < dict->size; ++i) {
357  if (dict->tab[i] == NULL)
358  continue;
359  for (j = 0; j < gwlist_len(dict->tab[i]); ++j) {
360  item = gwlist_get(dict->tab[i], j);
361  gwlist_append(list, octstr_duplicate(item->key));
362  }
363  }
364  unlock(dict);
365 
366  return list;
367 }
368 
369 
370 Dict *dict_duplicate(Dict *dict, void *(*duplicate_value)(void *))
371 {
372  Item *item;
373  long i, j;
374  Dict *dup;
375 
376  lock(dict);
377  dup = dict_create(dict->size, dict->destroy_value);
378  for (i = 0; i < dict->size; ++i) {
379  if (dict->tab[i] == NULL)
380  continue;
381  for (j = 0; j < gwlist_len(dict->tab[i]); ++j) {
382  item = gwlist_get(dict->tab[i], j);
383  dict_put(dup, item->key, duplicate_value(item->value));
384  }
385  }
386  unlock(dict);
387 
388  return dup;
389 }
390 
391 
392 long dict_traverse(Dict *dict, void (*func)(Octstr *, void *, void *), void *data)
393 {
394  Item *item;
395  long i, j, r = 0;
396 
397  lock(dict);
398  for (i = 0; i < dict->size; ++i) {
399  if (dict->tab[i] == NULL)
400  continue;
401  for (j = 0; j < gwlist_len(dict->tab[i]); ++j) {
402  item = gwlist_get(dict->tab[i], j);
403  func(item->key, item->value, data);
404  r++;
405  }
406  }
407  unlock(dict);
408 
409  return r;
410 }
411 
412 
413 long dict_traverse_sorted(Dict *dict, int (*cmp)(const void *, const void *),
414  void (*func)(Octstr *, void *, void *), void *data)
415 {
416  Item *item;
417  long i, j, r = 0;
418  List *l;
419 
420  l = gwlist_create();
421  lock(dict);
422 
423  /* We need to aggregate a list of all item elements first. */
424  for (i = 0; i < dict->size; ++i) {
425  if (dict->tab[i] == NULL)
426  continue;
427  for (j = 0; j < gwlist_len(dict->tab[i]); ++j) {
428  gwlist_append(l, gwlist_get(dict->tab[i], j));
429  }
430  }
431 
432  /* Now we can sort the list. */
433  gwlist_sort(l, cmp);
434 
435  /* And traverse the list. */
436  r = gwlist_len(l);
437  while ((item = gwlist_consume(l)) != NULL) {
438  func(item->key, item->value, data);
439  }
440 
441  unlock(dict);
442  gwlist_destroy(l, NULL);
443 
444  return r;
445 }
Dict * dict_create(long size_hint, void(*destroy_value)(void *))
Definition: dict.c:192
Mutex * lock
Definition: dict.c:121
void * gwlist_search(List *list, void *pattern, int(*cmp)(void *, void *))
Definition: list.c:486
static Item * item_create(Octstr *key, void *value)
Definition: dict.c:81
void dict_put(Dict *dict, Octstr *key, void *value)
Definition: dict.c:240
void gwlist_append(List *list, void *item)
Definition: list.c:179
#define mutex_unlock(m)
Definition: thread.h:136
Octstr * key
Definition: dict.c:76
long gwlist_len(List *list)
Definition: list.c:166
long dict_traverse(Dict *dict, void(*func)(Octstr *, void *, void *), void *data)
Definition: dict.c:392
#define mutex_create()
Definition: thread.h:96
void * gwlist_get(List *list, long pos)
Definition: list.c:292
void gwlist_sort(List *list, int(*cmp)(const void *, const void *))
Definition: list.c:576
static void unlock(Dict *dict)
Definition: dict.c:131
List * gwlist_extract_matching(List *list, void *pat, gwlist_item_matches_t *cmp)
Definition: list.c:322
void * value
Definition: dict.c:77
List ** tab
Definition: dict.c:117
void * dict_remove(Dict *dict, Octstr *key)
Definition: dict.c:307
long key_count
Definition: dict.c:119
void * gwlist_extract_first(List *list)
Definition: list.c:305
static int item_has_key(void *item, void *key)
Definition: dict.c:101
static long key_to_index(Dict *dict, Octstr *key)
Definition: dict.c:137
void * dict_get(Dict *dict, Octstr *key)
Definition: dict.c:286
Definition: dict.c:116
#define octstr_duplicate(ostr)
Definition: octstr.h:187
long size
Definition: dict.c:118
long dict_key_count(Dict *dict)
Definition: dict.c:335
unsigned long octstr_hash_key(Octstr *ostr)
Definition: octstr.c:2521
void octstr_destroy(Octstr *ostr)
Definition: octstr.c:322
gw_assert(wtls_machine->packet_to_send!=NULL)
void mutex_destroy(Mutex *mutex)
Definition: thread.c:97
static int dict_put_true(Dict *dict, Octstr *key, void *value)
Definition: dict.c:154
Dict * dict_duplicate(Dict *dict, void *(*duplicate_value)(void *))
Definition: dict.c:370
void dict_destroy(Dict *dict)
Definition: dict.c:215
long dict_traverse_sorted(Dict *dict, int(*cmp)(const void *, const void *), void(*func)(Octstr *, void *, void *), void *data)
Definition: dict.c:413
Definition: octstr.c:118
void * gwlist_consume(List *list)
Definition: list.c:427
List * dict_keys(Dict *dict)
Definition: dict.c:347
#define gwlist_create()
Definition: list.h:136
static int handle_null_value(Dict *dict, Octstr *key, void *value)
Definition: dict.c:142
Definition: thread.h:76
int dict_put_once(Dict *dict, Octstr *key, void *value)
Definition: dict.c:271
static void item_destroy(void *item)
Definition: dict.c:91
#define mutex_lock(m)
Definition: thread.h:130
static void lock(Dict *dict)
Definition: dict.c:125
Definition: list.c:102
void(* destroy_value)(void *)
Definition: dict.c:120
int octstr_compare(const Octstr *ostr1, const Octstr *ostr2)
Definition: octstr.c:869
void gwlist_destroy(List *list, gwlist_item_destructor_t *destructor)
Definition: list.c:145
See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.