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 | */ |
---|
16 | int owl_obarray_lookup(const owl_obarray *oa, const char * key, const char ** val) /*noproto*/ |
---|
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 */ |
---|
43 | const 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 */ |
---|
51 | const 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 | |
---|
64 | void 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 | |
---|
77 | int owl_obarray_regtest(void) { |
---|
78 | int numfailed = 0; |
---|
79 | const 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 */ |
---|