source: dict.c @ b343c2c

release-1.8release-1.9
Last change on this file since b343c2c was d427f08, checked in by Nelson Elhage <nelhage@mit.edu>, 10 years ago
Use G_GNUC_WARN_UNUSED_RESULT Have gcc warn us when we ignore the result of a function that requires the caller to free the result, or an initilization function that can fail. This might help (slightly) with preventing leaks and segfaults. Additionally changed some functions that should never fail to not return values. (The owl_list_* functions changed only fail if list->size < 0, which we assume is not the case elsewhere.)
  • 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
17void owl_dict_create(owl_dict *d) {
18  d->size=0;
19  d->els=g_new(owl_dict_el, INITSIZE);
20  d->avail=INITSIZE;
21}
22
23int owl_dict_get_size(const owl_dict *d) {
24  return(d->size);
25}
26
27/* Finds the position of an element with key k, or of the element where
28 * this element would logically go, and stores the index in pos.
29 * Returns 1 if found, else 0. */
30int _owl_dict_find_pos(const owl_dict *d, const char *k, int *pos) {
31  int lo = 0, hi = d->size;
32  while (lo < hi) {
33    int mid = (lo + hi)/2; /* lo goes up and we can't hit hi, so no +1 */
34    int cmp = strcmp(k, d->els[mid].k);
35    if (cmp < 0) {
36      hi = mid;
37    } else if (cmp > 0) {
38      lo = mid+1;
39    } else {
40      *pos = mid;
41      return 1;
42    }
43  }
44  *pos = lo;
45  return 0;
46}
47
48/* returns the value corresponding to key k */
49void *owl_dict_find_element(const owl_dict *d, const char *k) {
50  int found, pos;
51  found = _owl_dict_find_pos(d, k, &pos);
52  if (!found) {
53    return(NULL);
54  }
55  return(d->els[pos].v);
56}
57
58/* Appends dictionary keys to a list.  Duplicates the keys,
59 * so they will need to be freed by the caller. */
60void owl_dict_get_keys(const owl_dict *d, owl_list *l) {
61  int i;
62  for (i=0; i<d->size; i++) {
63    owl_list_append_element(l, g_strdup(d->els[i].k));
64  }
65}
66
67void owl_dict_noop_delete(void *x)
68{
69  return;
70}
71
72/* Returns 0 on success.  Will copy the key but make
73   a reference to the value.  Will clobber an existing
74   entry with the same key iff delete_on_replace!=NULL,
75   and will run delete_on_replace on the old element.
76   Will return -2 if replace=NULL and match was found.
77*/
78int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*delete_on_replace)(void *old))
79{
80  int pos, found;
81  found = _owl_dict_find_pos(d, k, &pos);
82  if (found && delete_on_replace) {
83    delete_on_replace(d->els[pos].v);
84    d->els[pos].v = v;
85    return(0);
86  } else if (found && !delete_on_replace) {
87    return(-2);
88  } else {
89    if (d->size + 1 > d->avail) {
90      int avail = MAX(d->avail * GROWBY, d->size + 1);
91      d->els = g_renew(owl_dict_el, d->els, avail);
92      d->avail = avail;
93      if (d->els==NULL) return(-1);
94    }
95    if (pos!=d->size) {
96      /* shift forward to leave us a slot */
97      memmove(d->els+pos+1, d->els+pos, 
98              sizeof(owl_dict_el)*(d->size-pos));
99    }
100    d->size++;
101    d->els[pos].k = g_strdup(k);
102    d->els[pos].v = v;   
103    return(0);
104  }
105}
106
107/* Doesn't free the value of the element, but does
108 * return it so the caller can free it. */
109G_GNUC_WARN_UNUSED_RESULT void *owl_dict_remove_element(owl_dict *d, const char *k)
110{
111  int i;
112  int pos, found;
113  void *v;
114  found = _owl_dict_find_pos(d, k, &pos);
115  if (!found) return(NULL);
116  g_free(d->els[pos].k);
117  v = d->els[pos].v;
118  for (i=pos; i<d->size-1; i++) {
119    d->els[i]=d->els[i+1];
120  }
121  d->size--;
122  return(v);
123}
124
125/* elefree should free the value as well */
126void owl_dict_cleanup(owl_dict *d, void (*elefree)(void *))
127{
128  int i;
129
130  for (i=0; i<d->size; i++) {
131    g_free(d->els[i].k);
132    if (elefree) (elefree)(d->els[i].v);
133  }
134  if (d->els) g_free(d->els);
135}
136
Note: See TracBrowser for help on using the repository browser.