[124aebc] | 1 | #include <stdlib.h> |
---|
| 2 | #include <string.h> |
---|
| 3 | #include "owl.h" |
---|
| 4 | |
---|
| 5 | // Lookup a key in the obarray. If the key exists, return its index, |
---|
| 6 | // and the interned value in *val. Otherwise, return the index it |
---|
| 7 | // should be inserted at. |
---|
| 8 | int owl_obarray_lookup(owl_obarray *oa, char * key, char ** val) /*noproto*/ |
---|
| 9 | { |
---|
| 10 | int first, last, mid; |
---|
| 11 | char * str; |
---|
| 12 | int cmp; |
---|
| 13 | |
---|
| 14 | mid = 0; |
---|
| 15 | first = 0; |
---|
| 16 | last = owl_list_get_size(&(oa->strings)) - 1; |
---|
| 17 | while(first <= last) { |
---|
| 18 | mid = first + (last - first)/2; |
---|
| 19 | str = (char*)owl_list_get_element(&(oa->strings), mid); |
---|
| 20 | cmp = strcmp(key, str); |
---|
| 21 | if(cmp == 0) { |
---|
| 22 | *val = str; |
---|
| 23 | return mid; |
---|
| 24 | } else if(cmp < 0) { |
---|
| 25 | first = mid + 1; |
---|
| 26 | } else { |
---|
| 27 | last = mid - 1; |
---|
| 28 | } |
---|
| 29 | } |
---|
| 30 | *val = NULL; |
---|
| 31 | return mid; |
---|
| 32 | } |
---|
| 33 | |
---|
| 34 | // Returns NULL if the string doesn't exist in the obarray |
---|
| 35 | char * owl_obarray_find(owl_obarray *oa, char * string) |
---|
| 36 | { |
---|
| 37 | char *v; |
---|
| 38 | owl_obarray_lookup(oa, string, &v); |
---|
| 39 | return v; |
---|
| 40 | } |
---|
| 41 | |
---|
| 42 | // Inserts the string into the obarray if it doesn't exist |
---|
| 43 | char * owl_obarray_insert(owl_obarray *oa, char * string) |
---|
| 44 | { |
---|
| 45 | char *v; |
---|
| 46 | int i; |
---|
| 47 | i = owl_obarray_lookup(oa, string, &v); |
---|
| 48 | if(!v) { |
---|
| 49 | v = owl_strdup(string); |
---|
| 50 | owl_list_insert_element(&(oa->strings), i, v); |
---|
| 51 | } |
---|
| 52 | return v; |
---|
| 53 | } |
---|
| 54 | |
---|
| 55 | void owl_obarray_init(owl_obarray *oa) |
---|
| 56 | { |
---|
| 57 | owl_list_create(&(oa->strings)); |
---|
| 58 | } |
---|
| 59 | |
---|
| 60 | /**************************************************************************/ |
---|
| 61 | /************************* REGRESSION TESTS *******************************/ |
---|
| 62 | /**************************************************************************/ |
---|
| 63 | |
---|
| 64 | #ifdef OWL_INCLUDE_REG_TESTS |
---|
| 65 | |
---|
| 66 | #include "test.h" |
---|
| 67 | |
---|
| 68 | int owl_obarray_regtest(void) { |
---|
| 69 | int numfailed = 0; |
---|
| 70 | char *p,*p2; |
---|
| 71 | |
---|
| 72 | owl_obarray oa; |
---|
| 73 | owl_obarray_init(&oa); |
---|
| 74 | |
---|
| 75 | printf("BEGIN testing owl_obarray\n"); |
---|
| 76 | |
---|
| 77 | p = owl_obarray_insert(&oa, "test"); |
---|
| 78 | FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test")); |
---|
| 79 | p2 = owl_obarray_insert(&oa, "test"); |
---|
| 80 | FAIL_UNLESS("returned string is equal", p2 && !strcmp(p2, "test")); |
---|
| 81 | FAIL_UNLESS("returned the same string", p2 && p == p2); |
---|
| 82 | |
---|
| 83 | p = owl_obarray_insert(&oa, "test2"); |
---|
| 84 | FAIL_UNLESS("returned string is equal", p && !strcmp(p, "test2")); |
---|
| 85 | p2 = owl_obarray_find(&oa, "test2"); |
---|
| 86 | FAIL_UNLESS("returned the same string", p2 && !strcmp(p2, "test2")); |
---|
| 87 | |
---|
| 88 | p = owl_obarray_find(&oa, "nothere"); |
---|
| 89 | FAIL_UNLESS("Didn't find a string that isn't there", p == NULL); |
---|
| 90 | |
---|
| 91 | printf("END testing owl_obarray (%d failures)\n", numfailed); |
---|
| 92 | |
---|
| 93 | return numfailed; |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | #endif /* OWL_INCLUDE_REG_TESTS */ |
---|