source: dict.c @ f75a9ca

release-1.10release-1.9
Last change on this file since f75a9ca 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
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
[1aee7d9]8#include "owl.h"
9
[7d4fbcd]10#define INITSIZE 30
[0f15f12]11#define GROWBY 3 / 2
[7d4fbcd]12
[4c7c21f]13void owl_dict_create(owl_dict *d) {
[7d4fbcd]14  d->size=0;
[96828e4]15  d->els=g_new(owl_dict_el, INITSIZE);
[7d4fbcd]16  d->avail=INITSIZE;
17}
18
[636b137]19int owl_dict_get_size(const owl_dict *d) {
[7d4fbcd]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. */
[636b137]26int _owl_dict_find_pos(const owl_dict *d, const char *k, int *pos) {
[2b37be2]27  int lo = 0, hi = d->size;
[7cd5878]28  while (lo < hi) {
[2b37be2]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) {
[7cd5878]32      hi = mid;
[2b37be2]33    } else if (cmp > 0) {
[7cd5878]34      lo = mid+1;
[2b37be2]35    } else {
36      *pos = mid;
37      return 1;
[7cd5878]38    }
[7d4fbcd]39  }
[7cd5878]40  *pos = lo;
[2b37be2]41  return 0;
[7d4fbcd]42}
43
44/* returns the value corresponding to key k */
[636b137]45void *owl_dict_find_element(const owl_dict *d, const char *k) {
[7d4fbcd]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
[ce68f23]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);
[7d4fbcd]58  int i;
[ce68f23]59  for (i = 0; i < d->size; i++) {
60    g_ptr_array_add(keys, g_strdup(d->els[i].k));
[7d4fbcd]61  }
[ce68f23]62  return keys;
[7d4fbcd]63}
64
[a1074de]65void owl_dict_noop_delete(void *x)
66{
[7d4fbcd]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
[a1074de]72   entry with the same key iff delete_on_replace!=NULL,
73   and will run delete_on_replace on the old element.
[7d4fbcd]74   Will return -2 if replace=NULL and match was found.
75*/
[a1074de]76int owl_dict_insert_element(owl_dict *d, const char *k, void *v, void (*delete_on_replace)(void *old))
77{
[7d4fbcd]78  int pos, found;
79  found = _owl_dict_find_pos(d, k, &pos);
[a1074de]80  if (found && delete_on_replace) {
81    delete_on_replace(d->els[pos].v);
[7d4fbcd]82    d->els[pos].v = v;
83    return(0);
[a1074de]84  } else if (found && !delete_on_replace) {
[7d4fbcd]85    return(-2);
86  } else {
[0f15f12]87    if (d->size + 1 > d->avail) {
88      int avail = MAX(d->avail * GROWBY, d->size + 1);
[35b6eb9]89      d->els = g_renew(owl_dict_el, d->els, avail);
[0f15f12]90      d->avail = avail;
[7d4fbcd]91      if (d->els==NULL) return(-1);
92    }
93    if (pos!=d->size) {
94      /* shift forward to leave us a slot */
[4d86e06]95      memmove(d->els+pos+1, d->els+pos, 
[7d4fbcd]96              sizeof(owl_dict_el)*(d->size-pos));
97    }
98    d->size++;
[fda61d3]99    d->els[pos].k = g_strdup(k);
[7d4fbcd]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. */
[6829afc]107CALLER_OWN void *owl_dict_remove_element(owl_dict *d, const char *k)
[d427f08]108{
[7d4fbcd]109  int i;
110  int pos, found;
111  void *v;
112  found = _owl_dict_find_pos(d, k, &pos);
113  if (!found) return(NULL);
[ddbbcffa]114  g_free(d->els[pos].k);
[7d4fbcd]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 */
[bf7aa1d]124void owl_dict_cleanup(owl_dict *d, void (*elefree)(void *))
125{
[7d4fbcd]126  int i;
127
128  for (i=0; i<d->size; i++) {
[ddbbcffa]129    g_free(d->els[i].k);
[7d4fbcd]130    if (elefree) (elefree)(d->els[i].v);
131  }
[ddbbcffa]132  if (d->els) g_free(d->els);
[7d4fbcd]133}
134
Note: See TracBrowser for help on using the repository browser.