source: obarray.c @ e7dc035

barnowl_perlaimdebianrelease-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since e7dc035 was 124aebc, checked in by Nelson Elhage <nelhage@mit.edu>, 18 years ago
Adding owl_obarray for interning strings
  • Property mode set to 100644
File size: 2.4 KB
Line 
1#include <stdlib.h>
2#include <string.h>
3#include "owl.h"
4
5// Lookup a key in the obarray. If the key exists, return its index,
6// and the interned value in *val. Otherwise, return the index it
7// should be inserted at.
8int owl_obarray_lookup(owl_obarray *oa, char * key, char ** val) /*noproto*/
9{
10  int first, last, mid;
11  char * str;
12  int cmp;
13
14  mid = 0;
15  first = 0;
16  last = owl_list_get_size(&(oa->strings)) - 1;
17  while(first <= last) {
18    mid = first + (last - first)/2;
19    str = (char*)owl_list_get_element(&(oa->strings), mid);
20    cmp = strcmp(key, str);
21    if(cmp == 0) {
22      *val = str;
23      return mid;
24    } else if(cmp < 0) {
25      first = mid + 1;
26    } else {
27      last = mid - 1;
28    }
29  }
30  *val = NULL;
31  return mid;
32}
33
34// Returns NULL if the string doesn't exist in the obarray
35char * owl_obarray_find(owl_obarray *oa, char * string)
36{
37  char *v;
38  owl_obarray_lookup(oa, string, &v);
39  return v;
40}
41
42// Inserts the string into the obarray if it doesn't exist
43char * owl_obarray_insert(owl_obarray *oa, char * string)
44{
45  char *v;
46  int i;
47  i = owl_obarray_lookup(oa, string, &v);
48  if(!v) {
49    v = owl_strdup(string);
50    owl_list_insert_element(&(oa->strings), i, v);
51  }
52  return v;
53}
54
55void owl_obarray_init(owl_obarray *oa)
56{
57  owl_list_create(&(oa->strings));
58}
59
60/**************************************************************************/
61/************************* REGRESSION TESTS *******************************/
62/**************************************************************************/
63
64#ifdef OWL_INCLUDE_REG_TESTS
65
66#include "test.h"
67
68int owl_obarray_regtest(void) {
69  int numfailed = 0;
70  char *p,*p2;
71
72  owl_obarray oa;
73  owl_obarray_init(&oa);
74
75  printf("BEGIN testing owl_obarray\n");
76
77  p = owl_obarray_insert(&oa, "test");
78  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test"));
79  p2 = owl_obarray_insert(&oa, "test");
80  FAIL_UNLESS("returned string is equal", p2 && !strcmp(p2, "test"));
81  FAIL_UNLESS("returned the same string", p2 && p == p2);
82
83  p = owl_obarray_insert(&oa, "test2");
84  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test2"));
85  p2 = owl_obarray_find(&oa, "test2");
86  FAIL_UNLESS("returned the same string", p2 && !strcmp(p2, "test2"));
87
88  p = owl_obarray_find(&oa, "nothere");
89  FAIL_UNLESS("Didn't find a string that isn't there", p == NULL);
90
91  printf("END testing owl_obarray (%d failures)\n", numfailed);
92
93  return numfailed;
94}
95
96#endif /* OWL_INCLUDE_REG_TESTS */
Note: See TracBrowser for help on using the repository browser.