source: dict.c @ c266281

release-1.8release-1.9
Last change on this file since c266281 was ce68f23, checked in by David Benjamin <davidben@mit.edu>, 10 years ago
Make owl_dict_get_keys return a GPtrArray Almost all the remaining uses of owl_list are tightly coupled into this one giant blob.
  • Property mode set to 100644
File size: 3.4 KB
RevLine 
[7d4fbcd]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.
[7cd5878]5 * O(log n) on searches
[7d4fbcd]6 */
7
8#include <stdlib.h>
9#include <string.h>
10#include <unistd.h>
[1aee7d9]11#include "owl.h"
12
[7d4fbcd]13
14#define INITSIZE 30
[0f15f12]15#define GROWBY 3 / 2
[7d4fbcd]16
[4c7c21f]17void owl_dict_create(owl_dict *d) {
[7d4fbcd]18  d->size=0;
[96828e4]19  d->els=g_new(owl_dict_el, INITSIZE);
[7d4fbcd]20  d->avail=INITSIZE;
21}
22
[636b137]23int owl_dict_get_size(const owl_dict *d) {
[7d4fbcd]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. */
[636b137]30int _owl_dict_find_pos(const owl_dict *d, const char *k, int *pos) {
[2b37be2]31  int lo = 0, hi = d->size;
[7cd5878]32  while (lo < hi) {
[2b37be2]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) {
[7cd5878]36      hi = mid;
[2b37be2]37    } else if (cmp > 0) {
[7cd5878]38      lo = mid+1;
[2b37be2]39    } else {
40      *pos = mid;
41      return 1;
[7cd5878]42    }
[7d4fbcd]43  }
[7cd5878]44  *pos = lo;
[2b37be2]45  return 0;
[7d4fbcd]46}
47
48/* returns the value corresponding to key k */
[636b137]49void *owl_dict_find_element(const owl_dict *d, const char *k) {
[7d4fbcd]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
[ce68f23]58/* Returns a GPtrArray of dictionary keys. Duplicates the keys, so
59 * they will need to be freed by the caller with g_free. */
60CALLER_OWN GPtrArray *owl_dict_get_keys(const owl_dict *d) {
61  GPtrArray *keys = g_ptr_array_sized_new(d->size);
[7d4fbcd]62  int i;
[ce68f23]63  for (i = 0; i < d->size; i++) {
64    g_ptr_array_add(keys, g_strdup(d->els[i].k));
[7d4fbcd]65  }
[ce68f23]66  return keys;
[7d4fbcd]67}
68
[a1074de]69void owl_dict_noop_delete(void *x)
70{
[7d4fbcd]71  return;
72}
73
74/* Returns 0 on success.  Will copy the key but make
75   a reference to the value.  Will clobber an existing
[a1074de]76   entry with the same key iff delete_on_replace!=NULL,
77   and will run delete_on_replace on the old element.
[7d4fbcd]78   Will return -2 if replace=NULL and match was found.
79*/
[a1074de]80int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*delete_on_replace)(void *old))
81{
[7d4fbcd]82  int pos, found;
83  found = _owl_dict_find_pos(d, k, &pos);
[a1074de]84  if (found && delete_on_replace) {
85    delete_on_replace(d->els[pos].v);
[7d4fbcd]86    d->els[pos].v = v;
87    return(0);
[a1074de]88  } else if (found && !delete_on_replace) {
[7d4fbcd]89    return(-2);
90  } else {
[0f15f12]91    if (d->size + 1 > d->avail) {
92      int avail = MAX(d->avail * GROWBY, d->size + 1);
[35b6eb9]93      d->els = g_renew(owl_dict_el, d->els, avail);
[0f15f12]94      d->avail = avail;
[7d4fbcd]95      if (d->els==NULL) return(-1);
96    }
97    if (pos!=d->size) {
98      /* shift forward to leave us a slot */
[4d86e06]99      memmove(d->els+pos+1, d->els+pos, 
[7d4fbcd]100              sizeof(owl_dict_el)*(d->size-pos));
101    }
102    d->size++;
[fda61d3]103    d->els[pos].k = g_strdup(k);
[7d4fbcd]104    d->els[pos].v = v;   
105    return(0);
106  }
107}
108
109/* Doesn't free the value of the element, but does
110 * return it so the caller can free it. */
[6829afc]111CALLER_OWN void *owl_dict_remove_element(owl_dict *d, const char *k)
[d427f08]112{
[7d4fbcd]113  int i;
114  int pos, found;
115  void *v;
116  found = _owl_dict_find_pos(d, k, &pos);
117  if (!found) return(NULL);
[ddbbcffa]118  g_free(d->els[pos].k);
[7d4fbcd]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 */
[bf7aa1d]128void owl_dict_cleanup(owl_dict *d, void (*elefree)(void *))
129{
[7d4fbcd]130  int i;
131
132  for (i=0; i<d->size; i++) {
[ddbbcffa]133    g_free(d->els[i].k);
[7d4fbcd]134    if (elefree) (elefree)(d->els[i].v);
135  }
[ddbbcffa]136  if (d->els) g_free(d->els);
[7d4fbcd]137}
138
Note: See TracBrowser for help on using the repository browser.