source: obarray.c @ 72634c5

release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since 72634c5 was e9c6fc8, checked in by Anders Kaseorg <andersk@mit.edu>, 12 years ago
Replace /* noproto */ comments with static. Signed-off-by: Anders Kaseorg <andersk@mit.edu>
  • Property mode set to 100644
File size: 1.6 KB
Line 
1#include <stdlib.h>
2#include <string.h>
3#include "owl.h"
4
5/*
6 * At the moment, the obarray is represented as a sorted list of
7 * strings. I judge this a reasonable tradeoff between simplicity and
8 * reasonable efficient lookup (insertion should be comparatively
9 * rare)
10 */
11
12/* Helper method: Lookup a key in the obarray. If the key exists,
13 * return its index, and the interned value in *val. Otherwise, return
14 * the index it should be inserted at.
15 */
16static int owl_obarray_lookup(const owl_obarray *oa, const char *key, const char **val)
17{
18  int first, last, mid;
19  const char * str;
20  int cmp;
21
22  mid = 0;
23  first = 0;
24  last = owl_list_get_size(&(oa->strings)) - 1;
25  while(first <= last) {
26    mid = first + (last - first)/2;
27    str = owl_list_get_element(&(oa->strings), mid);
28    cmp = strcmp(key, str);
29    if(cmp == 0) {
30      *val = str;
31      return mid;
32    } else if(cmp < 0) {
33      first = mid + 1;
34    } else {
35      last = mid - 1;
36    }
37  }
38  *val = NULL;
39  return mid;
40}
41
42/* Returns NULL if the string doesn't exist in the obarray */
43const char * owl_obarray_find(const owl_obarray *oa, const char * string)
44{
45  const char *v;
46  owl_obarray_lookup(oa, string, &v);
47  return v;
48}
49
50/* Inserts the string into the obarray if it doesn't exist */
51const char * owl_obarray_insert(owl_obarray *oa, const char * string)
52{
53  const char *v;
54  int i;
55  i = owl_obarray_lookup(oa, string, &v);
56  if(!v) {
57    char *v2 = owl_strdup(string);
58    owl_list_insert_element(&(oa->strings), i, v2);
59    return v2;
60  }
61  return v;
62}
63
64void owl_obarray_init(owl_obarray *oa)
65{
66  owl_list_create(&(oa->strings));
67}
Note: See TracBrowser for help on using the repository browser.