release-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change
on this file since cc1eeac was
8bce750,
checked in by Nelson Elhage <nelhage@mit.edu>, 15 years ago
|
Move all regression tests into tester.c.
|
-
Property mode set to
100644
|
File size:
1.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 | */ |
---|
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 | } |
---|
Note: See
TracBrowser
for help on using the repository browser.