source: obarray.c @ a387d12e

barnowl_perlaimdebianrelease-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since a387d12e was db90f03, checked in by Nelson Elhage <nelhage@mit.edu>, 18 years ago
r19159@phanatique: nelhage | 2007-02-28 22:31:17 -0500 We don't need to free message keys any more. r19160@phanatique: nelhage | 2007-02-28 22:31:37 -0500 Some explanatory comments in obarray
  • 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.
15int owl_obarray_lookup(owl_obarray *oa, char * key, char ** val) /*noproto*/
16{
17  int first, last, mid;
18  char * str;
19  int cmp;
20
21  mid = 0;
22  first = 0;
23  last = owl_list_get_size(&(oa->strings)) - 1;
24  while(first <= last) {
25    mid = first + (last - first)/2;
26    str = (char*)owl_list_get_element(&(oa->strings), mid);
27    cmp = strcmp(key, str);
28    if(cmp == 0) {
29      *val = str;
30      return mid;
31    } else if(cmp < 0) {
32      first = mid + 1;
33    } else {
34      last = mid - 1;
35    }
36  }
37  *val = NULL;
38  return mid;
39}
40
41// Returns NULL if the string doesn't exist in the obarray
42char * owl_obarray_find(owl_obarray *oa, char * string)
43{
44  char *v;
45  owl_obarray_lookup(oa, string, &v);
46  return v;
47}
48
49// Inserts the string into the obarray if it doesn't exist
50char * owl_obarray_insert(owl_obarray *oa, char * string)
51{
52  char *v;
53  int i;
54  i = owl_obarray_lookup(oa, string, &v);
55  if(!v) {
56    v = owl_strdup(string);
57    owl_list_insert_element(&(oa->strings), i, v);
58  }
59  return v;
60}
61
62void owl_obarray_init(owl_obarray *oa)
63{
64  owl_list_create(&(oa->strings));
65}
66
67/**************************************************************************/
68/************************* REGRESSION TESTS *******************************/
69/**************************************************************************/
70
71#ifdef OWL_INCLUDE_REG_TESTS
72
73#include "test.h"
74
75int owl_obarray_regtest(void) {
76  int numfailed = 0;
77  char *p,*p2;
78
79  owl_obarray oa;
80  owl_obarray_init(&oa);
81
82  printf("BEGIN testing owl_obarray\n");
83
84  p = owl_obarray_insert(&oa, "test");
85  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test"));
86  p2 = owl_obarray_insert(&oa, "test");
87  FAIL_UNLESS("returned string is equal", p2 && !strcmp(p2, "test"));
88  FAIL_UNLESS("returned the same string", p2 && p == p2);
89
90  p = owl_obarray_insert(&oa, "test2");
91  FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test2"));
92  p2 = owl_obarray_find(&oa, "test2");
93  FAIL_UNLESS("returned the same string", p2 && !strcmp(p2, "test2"));
94
95  p = owl_obarray_find(&oa, "nothere");
96  FAIL_UNLESS("Didn't find a string that isn't there", p == NULL);
97
98  printf("END testing owl_obarray (%d failures)\n", numfailed);
99
100  return numfailed;
101}
102
103#endif /* OWL_INCLUDE_REG_TESTS */
Note: See TracBrowser for help on using the repository browser.