source: obarray.c @ fa4562c

release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since fa4562c was fa4562c, checked in by Anders Kaseorg <andersk@mit.edu>, 9 years ago
Prepare code for adding const qualifiers for char * and void *. Signed-off-by: Anders Kaseorg <andersk@mit.edu>
  • Property mode set to 100644
File size: 2.7 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 */
16int owl_obarray_lookup(owl_obarray *oa, char * key, char ** val) /*noproto*/
17{
18  int first, last, mid;
19  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 */
43char * owl_obarray_find(owl_obarray *oa, char * string)
44{
45  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 */
51char * owl_obarray_insert(owl_obarray *oa, char * string)
52{
53  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}
68
69/**************************************************************************/
70/************************* REGRESSION TESTS *******************************/
71/**************************************************************************/
72
73#ifdef OWL_INCLUDE_REG_TESTS
74
75#include "test.h"
76
77int owl_obarray_regtest(void) {
78  int numfailed = 0;
79  char *p,*p2;
80
81  owl_obarray oa;
82  owl_obarray_init(&oa);
83
84  printf("# BEGIN testing owl_obarray\n");
85
86  p = owl_obarray_insert(&oa, "test");
87  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test"));
88  p2 = owl_obarray_insert(&oa, "test");
89  FAIL_UNLESS("returned string is equal", p2 && !strcmp(p2, "test"));
90  FAIL_UNLESS("returned the same string", p2 && p == p2);
91
92  p = owl_obarray_insert(&oa, "test2");
93  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test2"));
94  p2 = owl_obarray_find(&oa, "test2");
95  FAIL_UNLESS("returned the same string", p2 && !strcmp(p2, "test2"));
96
97  p = owl_obarray_find(&oa, "nothere");
98  FAIL_UNLESS("Didn't find a string that isn't there", p == NULL);
99
100  printf("# END testing owl_obarray (%d failures)\n", numfailed);
101
102  return numfailed;
103}
104
105#endif /* OWL_INCLUDE_REG_TESTS */
Note: See TracBrowser for help on using the repository browser.