source: dict.c @ 488ebf6

owl
Last change on this file since 488ebf6 was fa00c5c, checked in by James M. Kretchmar <kretch@mit.edu>, 15 years ago
Correct license.
  • Property mode set to 100644
File size: 6.5 KB
Line 
1/* Copyright (c) 2002,2003,2004,2009 James M. Kretchmar
2 *
3 * This file is part of Owl.
4 *
5 * Owl is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * Owl is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with Owl.  If not, see <http://www.gnu.org/licenses/>.
17 *
18 * ---------------------------------------------------------------
19 *
20 * As of Owl version 2.1.12 there are patches contributed by
21 * developers of the branched BarnOwl project, Copyright (c)
22 * 2006-2009 The BarnOwl Developers. All rights reserved.
23 */
24
25/* Dictionary data abstraction. 
26 * Maps from strings to pointers.
27 * Stores as a sorted list of key/value pairs.
28 * O(n) on inserts and deletes.
29 * O(n) on searches, although it should switch to a binary search for O(log n)
30 */
31
32#include <stdlib.h>
33#include <string.h>
34#include <unistd.h>
35#include "owl.h"
36
37static const char fileIdent[] = "$Id$";
38
39
40#define INITSIZE 30
41#define GROWAT 2
42#define GROWBY 1.5
43
44int owl_dict_create(owl_dict *d) {
45  d->size=0;
46  d->els=(owl_dict_el *)owl_malloc(INITSIZE*sizeof(owl_dict_el));
47  d->avail=INITSIZE;
48  if (d->els==NULL) return(-1);
49  return(0);
50}
51
52int owl_dict_get_size(owl_dict *d) {
53  return(d->size);
54}
55
56/* Finds the position of an element with key k, or of the element where
57 * this element would logically go, and stores the index in pos.
58 * TODO: optimize to do a binary search.
59 * Returns 1 if found, else 0. */
60int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
61  int i;
62  for (i=0; (i<d->size) && strcmp(k,d->els[i].k)>0; i++);
63  *pos = i;
64  if (i>=d->size || strcmp(k,d->els[i].k)) {
65    return(0);
66  } else {
67    return(1);
68  }
69}
70
71/* returns the value corresponding to key k */
72void *owl_dict_find_element(owl_dict *d, char *k) {
73  int found, pos;
74  found = _owl_dict_find_pos(d, k, &pos);
75  if (!found) {
76    return(NULL);
77  }
78  return(d->els[pos].v);
79}
80
81/* creates a list and fills it in with keys.  duplicates the keys,
82 * so they will need to be freed by the caller. */
83int owl_dict_get_keys(owl_dict *d, owl_list *l) {
84  int i;
85  char *dupk;
86  if (owl_list_create(l)) return(-1);
87  for (i=0; i<d->size; i++) {
88    if ((dupk = owl_strdup(d->els[i].k)) == NULL) return(-1);
89    owl_list_append_element(l, (void*)dupk);
90  }
91  return(0);
92}
93
94void owl_dict_noop_free(void *x) {
95  return;
96}
97
98/* Returns 0 on success.  Will copy the key but make
99   a reference to the value.  Will clobber an existing
100   entry with the same key iff free_on_replace!=NULL,
101   and will run free_on_replace on the old element.
102   Will return -2 if replace=NULL and match was found.
103*/
104int owl_dict_insert_element(owl_dict *d, char *k, void *v, void (*free_on_replace)(void *old)) {
105  int pos, found;
106  char *dupk;
107  found = _owl_dict_find_pos(d, k, &pos);
108  if (found && free_on_replace) {
109    free_on_replace(d->els[pos].v);
110    d->els[pos].v = v;
111    return(0);
112  } else if (found && !free_on_replace) {
113    return(-2);
114  } else {
115    if ((d->size+1) > (d->avail/GROWAT)) {
116      d->els=owl_realloc(d->els, d->avail*GROWBY*sizeof(void *));
117      d->avail=d->avail*GROWBY;
118      if (d->els==NULL) return(-1);
119    }
120    if ((dupk = owl_strdup(k)) == NULL) return(-1);
121    if (pos!=d->size) {
122      /* shift forward to leave us a slot */
123      memmove((void*)(d->els+pos+1), (void*)(d->els+pos), 
124              sizeof(owl_dict_el)*(d->size-pos));
125    }
126    d->size++;
127    d->els[pos].k = dupk;
128    d->els[pos].v = v;   
129    return(0);
130  }
131}
132
133/* Doesn't free the value of the element, but does
134 * return it so the caller can free it. */
135void *owl_dict_remove_element(owl_dict *d, char *k) {
136  int i;
137  int pos, found;
138  void *v;
139  found = _owl_dict_find_pos(d, k, &pos);
140  if (!found) return(NULL);
141  owl_free(d->els[pos].k);
142  v = d->els[pos].v;
143  for (i=pos; i<d->size-1; i++) {
144    d->els[i]=d->els[i+1];
145  }
146  d->size--;
147  return(v);
148}
149
150/* elefree should free the value as well */
151void owl_dict_free_all(owl_dict *d, void (*elefree)(void *)) {
152  int i;
153
154  for (i=0; i<d->size; i++) {
155    owl_free(d->els[i].k);
156    if (elefree) (elefree)(d->els[i].v);
157  }
158  if (d->els) owl_free(d->els);
159}
160
161void owl_dict_free_simple(owl_dict *d) {
162  owl_dict_free_all(d, NULL);
163}
164
165
166
167/************* REGRESSION TESTS **************/
168#ifdef OWL_INCLUDE_REG_TESTS
169
170#define FAIL_UNLESS(desc,pred) printf("\t%-4s: %s\n", (pred)?"ok":(numfailed++,"FAIL"), desc)
171
172int owl_dict_regtest(void) {
173  owl_dict d;
174  owl_list l;
175  int numfailed=0;
176  char *av="aval", *bv="bval", *cv="cval", *dv="dval";
177
178  printf("BEGIN testing owl_dict\n");
179  FAIL_UNLESS("create", 0==owl_dict_create(&d));
180  FAIL_UNLESS("insert b", 0==owl_dict_insert_element(&d, "b", (void*)bv, owl_dict_noop_free));
181  FAIL_UNLESS("insert d", 0==owl_dict_insert_element(&d, "d", (void*)dv, owl_dict_noop_free));
182  FAIL_UNLESS("insert a", 0==owl_dict_insert_element(&d, "a", (void*)av, owl_dict_noop_free));
183  FAIL_UNLESS("insert c", 0==owl_dict_insert_element(&d, "c", (void*)cv, owl_dict_noop_free));
184  FAIL_UNLESS("reinsert d (no replace)", -2==owl_dict_insert_element(&d, "d", (void*)dv, 0));
185  FAIL_UNLESS("find a", (void*)av==owl_dict_find_element(&d, "a"));
186  FAIL_UNLESS("find b", (void*)bv==owl_dict_find_element(&d, "b"));
187  FAIL_UNLESS("find c", (void*)cv==owl_dict_find_element(&d, "c"));
188  FAIL_UNLESS("find d", (void*)dv==owl_dict_find_element(&d, "d"));
189  FAIL_UNLESS("find e (non-existent)", NULL==owl_dict_find_element(&d, "e"));
190  FAIL_UNLESS("remove d", (void*)dv==owl_dict_remove_element(&d, "d"));
191  FAIL_UNLESS("find d (post-removal)", NULL==owl_dict_find_element(&d, "d"));
192
193  FAIL_UNLESS("get_size", 3==owl_dict_get_size(&d));
194  FAIL_UNLESS("get_keys", 0==owl_dict_get_keys(&d, &l));
195  FAIL_UNLESS("get_keys result size", 3==owl_list_get_size(&l));
196 
197  /* these assume the returned keys are sorted */
198  FAIL_UNLESS("get_keys result val",0==strcmp("a",owl_list_get_element(&l,0)));
199  FAIL_UNLESS("get_keys result val",0==strcmp("b",owl_list_get_element(&l,1)));
200  FAIL_UNLESS("get_keys result val",0==strcmp("c",owl_list_get_element(&l,2)));
201
202  owl_list_free_all(&l, owl_free);
203  owl_dict_free_all(&d, NULL);
204
205  if (numfailed) printf("*** WARNING: failures encountered with owl_dict\n");
206  printf("END testing owl_dict (%d failures)\n", numfailed);
207  return(numfailed);
208}
209
210#endif /* OWL_INCLUDE_REG_TESTS */
Note: See TracBrowser for help on using the repository browser.