source: dict.c @ 7d4fbcd

barnowl_perlaimdebianowlrelease-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since 7d4fbcd was 7d4fbcd, checked in by James M. Kretchmar <kretch@mit.edu>, 22 years ago
Initial check in
  • Property mode set to 100644
File size: 5.5 KB
Line 
1/* Dictionary data abstraction. 
2 * Maps from strings to pointers.
3 * Stores as a sorted list of key/value pairs.
4 * O(n) on inserts and deletes.
5 * O(n) on searches, although it should switch to a binary search for O(log n)
6 */
7
8#include "owl.h"
9#include <stdlib.h>
10#include <string.h>
11#include <unistd.h>
12
13#define INITSIZE 30
14#define GROWAT 2
15#define GROWBY 1.5
16
17int owl_dict_create(owl_dict *d) {
18  d->size=0;
19  d->els=(owl_dict_el *)owl_malloc(INITSIZE*sizeof(owl_dict_el));
20  d->avail=INITSIZE;
21  if (d->els==NULL) return(-1);
22  return(0);
23}
24
25int owl_dict_get_size(owl_dict *d) {
26  return(d->size);
27}
28
29/* Finds the position of an element with key k, or of the element where
30 * this element would logically go, and stores the index in pos.
31 * TODO: optimize to do a binary search.
32 * Returns 1 if found, else 0. */
33int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
34  int i;
35  for (i=0; (i<d->size) && strcmp(k,d->els[i].k)>0; i++);
36  *pos = i;
37  if (i>=d->size || strcmp(k,d->els[i].k)) {
38    return(0);
39  } else {
40    return(1);
41  }
42}
43
44/* returns the value corresponding to key k */
45void *owl_dict_find_element(owl_dict *d, char *k) {
46  int found, pos;
47  found = _owl_dict_find_pos(d, k, &pos);
48  if (!found) {
49    return(NULL);
50  }
51  return(d->els[pos].v);
52}
53
54/* creates a list and fills it in with keys.  duplicates the keys,
55 * so they will need to be freed by the caller. */
56int owl_dict_get_keys(owl_dict *d, owl_list *l) {
57  int i;
58  char *dupk;
59  if (owl_list_create(l)) return(-1);
60  for (i=0; i<d->size; i++) {
61    if ((dupk = owl_strdup(d->els[i].k)) == NULL) return(-1);
62    owl_list_append_element(l, (void*)dupk);
63  }
64  return(0);
65}
66
67void owl_dict_noop_free(void *x) {
68  return;
69}
70
71/* Returns 0 on success.  Will copy the key but make
72   a reference to the value.  Will clobber an existing
73   entry with the same key iff free_on_replace!=NULL,
74   and will run free_on_replace on the old element.
75   Will return -2 if replace=NULL and match was found.
76*/
77int owl_dict_insert_element(owl_dict *d, char *k, void *v, void (*free_on_replace)(void *old)) {
78  int pos, found;
79  char *dupk;
80  found = _owl_dict_find_pos(d, k, &pos);
81  if (found && free_on_replace) {
82    free_on_replace(d->els[pos].v);
83    d->els[pos].v = v;
84    return(0);
85  } else if (found && !free_on_replace) {
86    return(-2);
87  } else {
88    if ((d->size+1) > (d->avail/GROWAT)) {
89      d->els=owl_realloc(d->els, d->avail*GROWBY*sizeof(void *));
90      d->avail=d->avail*GROWBY;
91      if (d->els==NULL) return(-1);
92    }
93    if ((dupk = owl_strdup(k)) == NULL) return(-1);
94    if (pos!=d->size) {
95      /* shift forward to leave us a slot */
96      memmove((void*)(d->els+pos+1), (void*)(d->els+pos), 
97              sizeof(owl_dict_el)*(d->size-pos));
98    }
99    d->size++;
100    d->els[pos].k = dupk;
101    d->els[pos].v = v;   
102    return(0);
103  }
104}
105
106/* Doesn't free the value of the element, but does
107 * return it so the caller can free it. */
108void *owl_dict_remove_element(owl_dict *d, char *k) {
109  int i;
110  int pos, found;
111  void *v;
112  found = _owl_dict_find_pos(d, k, &pos);
113  if (!found) return(NULL);
114  owl_free(d->els[pos].k);
115  v = d->els[pos].v;
116  for (i=pos; i<d->size-1; i++) {
117    d->els[i]=d->els[i+1];
118  }
119  d->size--;
120  return(v);
121}
122
123/* elefree should free the value as well */
124void owl_dict_free_all(owl_dict *d, void (*elefree)(void *)) {
125  int i;
126
127  for (i=0; i<d->size; i++) {
128    owl_free(d->els[i].k);
129    if (elefree) (elefree)(d->els[i].v);
130  }
131  if (d->els) owl_free(d->els);
132}
133
134void owl_dict_free_simple(owl_dict *d) {
135  owl_dict_free_all(d, NULL);
136}
137
138
139
140/************* REGRESSION TESTS **************/
141#ifdef OWL_INCLUDE_REG_TESTS
142
143#define FAIL_UNLESS(desc,pred) printf("\t%-4s: %s\n", (pred)?"ok":(numfailed++,"FAIL"), desc)
144
145int owl_dict_regtest(void) {
146  owl_dict d;
147  owl_list l;
148  int numfailed=0;
149  char *av="aval", *bv="bval", *cv="cval", *dv="dval";
150
151  printf("BEGIN testing owl_dict\n");
152  FAIL_UNLESS("create", 0==owl_dict_create(&d));
153  FAIL_UNLESS("insert b", 0==owl_dict_insert_element(&d, "b", (void*)bv, owl_dict_noop_free));
154  FAIL_UNLESS("insert d", 0==owl_dict_insert_element(&d, "d", (void*)dv, owl_dict_noop_free));
155  FAIL_UNLESS("insert a", 0==owl_dict_insert_element(&d, "a", (void*)av, owl_dict_noop_free));
156  FAIL_UNLESS("insert c", 0==owl_dict_insert_element(&d, "c", (void*)cv, owl_dict_noop_free));
157  FAIL_UNLESS("reinsert d (no replace)", -2==owl_dict_insert_element(&d, "d", (void*)dv, 0));
158  FAIL_UNLESS("find a", (void*)av==owl_dict_find_element(&d, "a"));
159  FAIL_UNLESS("find b", (void*)bv==owl_dict_find_element(&d, "b"));
160  FAIL_UNLESS("find c", (void*)cv==owl_dict_find_element(&d, "c"));
161  FAIL_UNLESS("find d", (void*)dv==owl_dict_find_element(&d, "d"));
162  FAIL_UNLESS("find e (non-existent)", NULL==owl_dict_find_element(&d, "e"));
163  FAIL_UNLESS("remove d", (void*)dv==owl_dict_remove_element(&d, "d"));
164  FAIL_UNLESS("find d (post-removal)", NULL==owl_dict_find_element(&d, "d"));
165
166  FAIL_UNLESS("get_size", 3==owl_dict_get_size(&d));
167  FAIL_UNLESS("get_keys", 0==owl_dict_get_keys(&d, &l));
168  FAIL_UNLESS("get_keys result size", 3==owl_list_get_size(&l));
169 
170  /* these assume the returned keys are sorted */
171  FAIL_UNLESS("get_keys result val",0==strcmp("a",owl_list_get_element(&l,0)));
172  FAIL_UNLESS("get_keys result val",0==strcmp("b",owl_list_get_element(&l,1)));
173  FAIL_UNLESS("get_keys result val",0==strcmp("c",owl_list_get_element(&l,2)));
174
175  owl_list_free_all(&l, owl_free);
176  owl_dict_free_all(&d, NULL);
177
178  if (numfailed) printf("*** WARNING: failures encountered with owl_dict\n");
179  printf("END testing owl_dict (%d failures)\n", numfailed);
180  return(numfailed);
181}
182
183#endif /* OWL_INCLUDE_REG_TESTS */
Note: See TracBrowser for help on using the repository browser.