source: dict.c @ 249bbbe

release-1.10release-1.8release-1.9
Last change on this file since 249bbbe was f25df21, checked in by David Benjamin <davidben@mit.edu>, 13 years ago
Don't call owl_list_create in owl_dict_get_keys Until we get rid of this owl_list thing altogether, there should be a convention as to who initializes the thing. Otherwise, we leak memory from people initializing it too many times. Whoever reviews this probably wants to look over this very carefully in case I missed one of the owl_list_creates. Also kill the various wrappers over owl_list_cleanup as they are not the inverse of any operation.
  • Property mode set to 100644
File size: 3.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 GROWBY 3 / 2
16
17int owl_dict_create(owl_dict *d) {
18  d->size=0;
19  d->els=g_new(owl_dict_el, INITSIZE);
20  d->avail=INITSIZE;
21  if (d->els==NULL) return(-1);
22  return(0);
23}
24
25int owl_dict_get_size(const 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 * Returns 1 if found, else 0. */
32int _owl_dict_find_pos(const owl_dict *d, const char *k, int *pos) {
33  int lo = 0, hi = d->size;
34  while (lo < hi) {
35    int mid = (lo + hi)/2; /* lo goes up and we can't hit hi, so no +1 */
36    int cmp = strcmp(k, d->els[mid].k);
37    if (cmp < 0) {
38      hi = mid;
39    } else if (cmp > 0) {
40      lo = mid+1;
41    } else {
42      *pos = mid;
43      return 1;
44    }
45  }
46  *pos = lo;
47  return 0;
48}
49
50/* returns the value corresponding to key k */
51void *owl_dict_find_element(const owl_dict *d, const char *k) {
52  int found, pos;
53  found = _owl_dict_find_pos(d, k, &pos);
54  if (!found) {
55    return(NULL);
56  }
57  return(d->els[pos].v);
58}
59
60/* Appends dictionary keys to a list.  Duplicates the keys,
61 * so they will need to be freed by the caller. */
62int owl_dict_get_keys(const owl_dict *d, owl_list *l) {
63  int i;
64  char *dupk;
65  for (i=0; i<d->size; i++) {
66    if ((dupk = g_strdup(d->els[i].k)) == NULL) return(-1);
67    owl_list_append_element(l, dupk);
68  }
69  return(0);
70}
71
72void owl_dict_noop_delete(void *x)
73{
74  return;
75}
76
77/* Returns 0 on success.  Will copy the key but make
78   a reference to the value.  Will clobber an existing
79   entry with the same key iff delete_on_replace!=NULL,
80   and will run delete_on_replace on the old element.
81   Will return -2 if replace=NULL and match was found.
82*/
83int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*delete_on_replace)(void *old))
84{
85  int pos, found;
86  char *dupk;
87  found = _owl_dict_find_pos(d, k, &pos);
88  if (found && delete_on_replace) {
89    delete_on_replace(d->els[pos].v);
90    d->els[pos].v = v;
91    return(0);
92  } else if (found && !delete_on_replace) {
93    return(-2);
94  } else {
95    if (d->size + 1 > d->avail) {
96      int avail = MAX(d->avail * GROWBY, d->size + 1);
97      d->els = g_renew(owl_dict_el, d->els, avail);
98      d->avail = avail;
99      if (d->els==NULL) return(-1);
100    }
101    if ((dupk = g_strdup(k)) == NULL) return(-1);
102    if (pos!=d->size) {
103      /* shift forward to leave us a slot */
104      memmove(d->els+pos+1, d->els+pos, 
105              sizeof(owl_dict_el)*(d->size-pos));
106    }
107    d->size++;
108    d->els[pos].k = dupk;
109    d->els[pos].v = v;   
110    return(0);
111  }
112}
113
114/* Doesn't free the value of the element, but does
115 * return it so the caller can free it. */
116void *owl_dict_remove_element(owl_dict *d, const char *k) {
117  int i;
118  int pos, found;
119  void *v;
120  found = _owl_dict_find_pos(d, k, &pos);
121  if (!found) return(NULL);
122  g_free(d->els[pos].k);
123  v = d->els[pos].v;
124  for (i=pos; i<d->size-1; i++) {
125    d->els[i]=d->els[i+1];
126  }
127  d->size--;
128  return(v);
129}
130
131/* elefree should free the value as well */
132void owl_dict_cleanup(owl_dict *d, void (*elefree)(void *))
133{
134  int i;
135
136  for (i=0; i<d->size; i++) {
137    g_free(d->els[i].k);
138    if (elefree) (elefree)(d->els[i].v);
139  }
140  if (d->els) g_free(d->els);
141}
142
Note: See TracBrowser for help on using the repository browser.