[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 | } |
---|
| 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; |
---|
[e19eb97] | 79 | const char *p,*p2; |
---|
[124aebc] | 80 | |
---|
| 81 | owl_obarray oa; |
---|
| 82 | owl_obarray_init(&oa); |
---|
| 83 | |
---|
[535d68b] | 84 | printf("# BEGIN testing owl_obarray\n"); |
---|
[124aebc] | 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 | |
---|
[535d68b] | 100 | printf("# END testing owl_obarray (%d failures)\n", numfailed); |
---|
[124aebc] | 101 | |
---|
| 102 | return numfailed; |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | #endif /* OWL_INCLUDE_REG_TESTS */ |
---|