source: dict.c @ 0fa0745

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