source: obarray.c @ 0f15f12

release-1.10release-1.4release-1.5release-1.6release-1.7release-1.8release-1.9
Last change on this file since 0f15f12 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
RevLine 
[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]16int 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]43const 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]51const 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
64void owl_obarray_init(owl_obarray *oa)
65{
66  owl_list_create(&(oa->strings));
67}
Note: See TracBrowser for help on using the repository browser.