source: obarray.c @ 601733d

barnowl_perlaimdebianrelease-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since 601733d was af1920fd, checked in by Alejandro R. Sedeño <asedeno@mit.edu>, 13 years ago
Portability - removing C++ style comments.
  • Property mode set to 100644
File size: 2.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 */
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 = (char*)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    v = owl_strdup(string);
58    owl_list_insert_element(&(oa->strings), i, v);
59  }
60  return v;
61}
62
63void owl_obarray_init(owl_obarray *oa)
64{
65  owl_list_create(&(oa->strings));
66}
67
68/**************************************************************************/
69/************************* REGRESSION TESTS *******************************/
70/**************************************************************************/
71
72#ifdef OWL_INCLUDE_REG_TESTS
73
74#include "test.h"
75
76int owl_obarray_regtest(void) {
77  int numfailed = 0;
78  char *p,*p2;
79
80  owl_obarray oa;
81  owl_obarray_init(&oa);
82
83  printf("# BEGIN testing owl_obarray\n");
84
85  p = owl_obarray_insert(&oa, "test");
86  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test"));
87  p2 = owl_obarray_insert(&oa, "test");
88  FAIL_UNLESS("returned string is equal", p2 && !strcmp(p2, "test"));
89  FAIL_UNLESS("returned the same string", p2 && p == p2);
90
91  p = owl_obarray_insert(&oa, "test2");
92  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test2"));
93  p2 = owl_obarray_find(&oa, "test2");
94  FAIL_UNLESS("returned the same string", p2 && !strcmp(p2, "test2"));
95
96  p = owl_obarray_find(&oa, "nothere");
97  FAIL_UNLESS("Didn't find a string that isn't there", p == NULL);
98
99  printf("# END testing owl_obarray (%d failures)\n", numfailed);
100
101  return numfailed;
102}
103
104#endif /* OWL_INCLUDE_REG_TESTS */
Note: See TracBrowser for help on using the repository browser.