source: dict.c @ 478dc8e

release-1.10release-1.9
Last change on this file since 478dc8e was f271129, checked in by Jason Gross <jgross@mit.edu>, 13 years ago
Fix up headers The additions to owl.h and some of the removals were done by Alejandro Sedeño <asedeno@mit.edu> in commit 77a0258b3919468fc9d7f7602588ac427ab36e6c. Notes: * I think owl.c lost the need for sys/time.h when we punted select() in favor of glib's main loop. * We don't actually need to include things like stdarg.h, stdio.h, glib/gstdio.h, glib-object.h. I think they get indirectly included via owl.h and/or glib.h. They're left in (or added in to) the files that use functions/types from them. * I'm not entirely sure what sys/socket.h is doing in message.c. It is there from the initial commit. I suspect it might have had something to do with the call to getnameinfo. message.c compiles without it, but http://pubs.opengroup.org/onlinepubs/009695399/functions/getnameinfo.html suggests that we're supposed to include it? *shrugs* I'm leaving it in, for now. (Rather, I'll leave one copy of the #include in.)
  • 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 "owl.h"
9
10#define INITSIZE 30
11#define GROWBY 3 / 2
12
13void owl_dict_create(owl_dict *d) {
14  d->size=0;
15  d->els=g_new(owl_dict_el, INITSIZE);
16  d->avail=INITSIZE;
17}
18
19int owl_dict_get_size(const owl_dict *d) {
20  return(d->size);
21}
22
23/* Finds the position of an element with key k, or of the element where
24 * this element would logically go, and stores the index in pos.
25 * Returns 1 if found, else 0. */
26int _owl_dict_find_pos(const owl_dict *d, const char *k, int *pos) {
27  int lo = 0, hi = d->size;
28  while (lo < hi) {
29    int mid = (lo + hi)/2; /* lo goes up and we can't hit hi, so no +1 */
30    int cmp = strcmp(k, d->els[mid].k);
31    if (cmp < 0) {
32      hi = mid;
33    } else if (cmp > 0) {
34      lo = mid+1;
35    } else {
36      *pos = mid;
37      return 1;
38    }
39  }
40  *pos = lo;
41  return 0;
42}
43
44/* returns the value corresponding to key k */
45void *owl_dict_find_element(const owl_dict *d, const 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/* Returns a GPtrArray of dictionary keys. Duplicates the keys, so
55 * they will need to be freed by the caller with g_free. */
56CALLER_OWN GPtrArray *owl_dict_get_keys(const owl_dict *d) {
57  GPtrArray *keys = g_ptr_array_sized_new(d->size);
58  int i;
59  for (i = 0; i < d->size; i++) {
60    g_ptr_array_add(keys, g_strdup(d->els[i].k));
61  }
62  return keys;
63}
64
65void owl_dict_noop_delete(void *x)
66{
67  return;
68}
69
70/* Returns 0 on success.  Will copy the key but make
71   a reference to the value.  Will clobber an existing
72   entry with the same key iff delete_on_replace!=NULL,
73   and will run delete_on_replace on the old element.
74   Will return -2 if replace=NULL and match was found.
75*/
76int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*delete_on_replace)(void *old))
77{
78  int pos, found;
79  found = _owl_dict_find_pos(d, k, &pos);
80  if (found && delete_on_replace) {
81    delete_on_replace(d->els[pos].v);
82    d->els[pos].v = v;
83    return(0);
84  } else if (found && !delete_on_replace) {
85    return(-2);
86  } else {
87    if (d->size + 1 > d->avail) {
88      int avail = MAX(d->avail * GROWBY, d->size + 1);
89      d->els = g_renew(owl_dict_el, d->els, avail);
90      d->avail = avail;
91      if (d->els==NULL) return(-1);
92    }
93    if (pos!=d->size) {
94      /* shift forward to leave us a slot */
95      memmove(d->els+pos+1, d->els+pos, 
96              sizeof(owl_dict_el)*(d->size-pos));
97    }
98    d->size++;
99    d->els[pos].k = g_strdup(k);
100    d->els[pos].v = v;   
101    return(0);
102  }
103}
104
105/* Doesn't free the value of the element, but does
106 * return it so the caller can free it. */
107CALLER_OWN void *owl_dict_remove_element(owl_dict *d, const char *k)
108{
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  g_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_cleanup(owl_dict *d, void (*elefree)(void *))
125{
126  int i;
127
128  for (i=0; i<d->size; i++) {
129    g_free(d->els[i].k);
130    if (elefree) (elefree)(d->els[i].v);
131  }
132  if (d->els) g_free(d->els);
133}
134
Note: See TracBrowser for help on using the repository browser.