source: dict.c @ 7967433

release-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since 7967433 was 0f15f12, checked in by Anders Kaseorg <andersk@mit.edu>, 15 years ago
owl_list_grow, owl_dict_insert_element: Don’t use fuzzy math. • Make sure to allocate at least as many elements as were requested. • Don’t use floating point math to compute the expansion amount. • In owl_dict_insert_element, reallocate using the right element size instead of relying on the GROWAT fudge factor (WTF?). Signed-off-by: Anders Kaseorg <andersk@mit.edu>
  • Property mode set to 100644
File size: 3.6 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
17int owl_dict_create(owl_dict *d) {
18  d->size=0;
[4d86e06]19  d->els=owl_malloc(INITSIZE*sizeof(owl_dict_el));
[7d4fbcd]20  d->avail=INITSIZE;
21  if (d->els==NULL) return(-1);
22  return(0);
23}
24
[636b137]25int owl_dict_get_size(const owl_dict *d) {
[7d4fbcd]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. */
[636b137]32int _owl_dict_find_pos(const owl_dict *d, const char *k, int *pos) {
[2b37be2]33  int lo = 0, hi = d->size;
[7cd5878]34  while (lo < hi) {
[2b37be2]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) {
[7cd5878]38      hi = mid;
[2b37be2]39    } else if (cmp > 0) {
[7cd5878]40      lo = mid+1;
[2b37be2]41    } else {
42      *pos = mid;
43      return 1;
[7cd5878]44    }
[7d4fbcd]45  }
[7cd5878]46  *pos = lo;
[2b37be2]47  return 0;
[7d4fbcd]48}
49
50/* returns the value corresponding to key k */
[636b137]51void *owl_dict_find_element(const owl_dict *d, const char *k) {
[7d4fbcd]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/* creates a list and fills it in with keys.  duplicates the keys,
61 * so they will need to be freed by the caller. */
[636b137]62int owl_dict_get_keys(const owl_dict *d, owl_list *l) {
[7d4fbcd]63  int i;
64  char *dupk;
65  if (owl_list_create(l)) return(-1);
66  for (i=0; i<d->size; i++) {
67    if ((dupk = owl_strdup(d->els[i].k)) == NULL) return(-1);
[4d86e06]68    owl_list_append_element(l, dupk);
[7d4fbcd]69  }
70  return(0);
71}
72
73void owl_dict_noop_free(void *x) {
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 free_on_replace!=NULL,
80   and will run free_on_replace on the old element.
81   Will return -2 if replace=NULL and match was found.
82*/
[e19eb97]83int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*free_on_replace)(void *old)) {
[7d4fbcd]84  int pos, found;
85  char *dupk;
86  found = _owl_dict_find_pos(d, k, &pos);
87  if (found && free_on_replace) {
88    free_on_replace(d->els[pos].v);
89    d->els[pos].v = v;
90    return(0);
91  } else if (found && !free_on_replace) {
92    return(-2);
93  } else {
[0f15f12]94    if (d->size + 1 > d->avail) {
95      int avail = MAX(d->avail * GROWBY, d->size + 1);
96      d->els = owl_realloc(d->els, avail * sizeof(owl_dict_el));
97      d->avail = avail;
[7d4fbcd]98      if (d->els==NULL) return(-1);
99    }
100    if ((dupk = owl_strdup(k)) == NULL) return(-1);
101    if (pos!=d->size) {
102      /* shift forward to leave us a slot */
[4d86e06]103      memmove(d->els+pos+1, d->els+pos, 
[7d4fbcd]104              sizeof(owl_dict_el)*(d->size-pos));
105    }
106    d->size++;
107    d->els[pos].k = dupk;
108    d->els[pos].v = v;   
109    return(0);
110  }
111}
112
113/* Doesn't free the value of the element, but does
114 * return it so the caller can free it. */
[e19eb97]115void *owl_dict_remove_element(owl_dict *d, const char *k) {
[7d4fbcd]116  int i;
117  int pos, found;
118  void *v;
119  found = _owl_dict_find_pos(d, k, &pos);
120  if (!found) return(NULL);
121  owl_free(d->els[pos].k);
122  v = d->els[pos].v;
123  for (i=pos; i<d->size-1; i++) {
124    d->els[i]=d->els[i+1];
125  }
126  d->size--;
127  return(v);
128}
129
130/* elefree should free the value as well */
131void owl_dict_free_all(owl_dict *d, void (*elefree)(void *)) {
132  int i;
133
134  for (i=0; i<d->size; i++) {
135    owl_free(d->els[i].k);
136    if (elefree) (elefree)(d->els[i].v);
137  }
138  if (d->els) owl_free(d->els);
139}
140
141void owl_dict_free_simple(owl_dict *d) {
142  owl_dict_free_all(d, NULL);
143}
144
Note: See TracBrowser for help on using the repository browser.