source: dict.c @ fda61d3

release-1.8release-1.9
Last change on this file since fda61d3 was fda61d3, checked in by David Benjamin <davidben@mit.edu>, 10 years ago
g_strdup and g_new0 never fail Remove pointless failure checks cluttering the code.
  • Property mode set to 100644
File size: 3.3 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  for (i=0; i<d->size; i++) {
65    owl_list_append_element(l, g_strdup(d->els[i].k));
66  }
67  return(0);
68}
69
70void owl_dict_noop_delete(void *x)
71{
72  return;
73}
74
75/* Returns 0 on success.  Will copy the key but make
76   a reference to the value.  Will clobber an existing
77   entry with the same key iff delete_on_replace!=NULL,
78   and will run delete_on_replace on the old element.
79   Will return -2 if replace=NULL and match was found.
80*/
81int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*delete_on_replace)(void *old))
82{
83  int pos, found;
84  found = _owl_dict_find_pos(d, k, &pos);
85  if (found && delete_on_replace) {
86    delete_on_replace(d->els[pos].v);
87    d->els[pos].v = v;
88    return(0);
89  } else if (found && !delete_on_replace) {
90    return(-2);
91  } else {
92    if (d->size + 1 > d->avail) {
93      int avail = MAX(d->avail * GROWBY, d->size + 1);
94      d->els = g_renew(owl_dict_el, d->els, avail);
95      d->avail = avail;
96      if (d->els==NULL) return(-1);
97    }
98    if (pos!=d->size) {
99      /* shift forward to leave us a slot */
100      memmove(d->els+pos+1, d->els+pos, 
101              sizeof(owl_dict_el)*(d->size-pos));
102    }
103    d->size++;
104    d->els[pos].k = g_strdup(k);
105    d->els[pos].v = v;   
106    return(0);
107  }
108}
109
110/* Doesn't free the value of the element, but does
111 * return it so the caller can free it. */
112void *owl_dict_remove_element(owl_dict *d, const char *k) {
113  int i;
114  int pos, found;
115  void *v;
116  found = _owl_dict_find_pos(d, k, &pos);
117  if (!found) return(NULL);
118  g_free(d->els[pos].k);
119  v = d->els[pos].v;
120  for (i=pos; i<d->size-1; i++) {
121    d->els[i]=d->els[i+1];
122  }
123  d->size--;
124  return(v);
125}
126
127/* elefree should free the value as well */
128void owl_dict_cleanup(owl_dict *d, void (*elefree)(void *))
129{
130  int i;
131
132  for (i=0; i<d->size; i++) {
133    g_free(d->els[i].k);
134    if (elefree) (elefree)(d->els[i].v);
135  }
136  if (d->els) g_free(d->els);
137}
138
Note: See TracBrowser for help on using the repository browser.