release-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change
on this file since 68c572a 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
|
Rev | Line | |
---|
[124aebc] | 1 | #include <stdlib.h> |
---|
| 2 | #include <string.h> |
---|
| 3 | #include "owl.h" |
---|
| 4 | |
---|
[db90f03] | 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 | |
---|
[af1920fd] | 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 | */ |
---|
[b1d5517] | 16 | int owl_obarray_lookup(const owl_obarray *oa, const char * key, const char ** val) /*noproto*/ |
---|
[124aebc] | 17 | { |
---|
| 18 | int first, last, mid; |
---|
[e19eb97] | 19 | const char * str; |
---|
[124aebc] | 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; |
---|
[4d86e06] | 27 | str = owl_list_get_element(&(oa->strings), mid); |
---|
[124aebc] | 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 | |
---|
[af1920fd] | 42 | /* Returns NULL if the string doesn't exist in the obarray */ |
---|
[b1d5517] | 43 | const char * owl_obarray_find(const owl_obarray *oa, const char * string) |
---|
[124aebc] | 44 | { |
---|
[e19eb97] | 45 | const char *v; |
---|
[124aebc] | 46 | owl_obarray_lookup(oa, string, &v); |
---|
| 47 | return v; |
---|
| 48 | } |
---|
| 49 | |
---|
[af1920fd] | 50 | /* Inserts the string into the obarray if it doesn't exist */ |
---|
[e19eb97] | 51 | const char * owl_obarray_insert(owl_obarray *oa, const char * string) |
---|
[124aebc] | 52 | { |
---|
[e19eb97] | 53 | const char *v; |
---|
[124aebc] | 54 | int i; |
---|
| 55 | i = owl_obarray_lookup(oa, string, &v); |
---|
| 56 | if(!v) { |
---|
[fa4562c] | 57 | char *v2 = owl_strdup(string); |
---|
| 58 | owl_list_insert_element(&(oa->strings), i, v2); |
---|
| 59 | return v2; |
---|
[124aebc] | 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.