+#define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
+
+char *strings[] = {
+ "a", "ab", "absque", "coram", "de",
+ "palam", "clam", "cum", "ex", "e",
+ "sine", "tenus", "pro", "prae",
+ "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
+ "penguin", "blancmange", "pangolin", "whale", "hedgehog",
+ "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
+ "murfl", "spoo", "breen", "flarn", "octothorpe",
+ "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
+ "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
+ "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
+ "wand", "ring", "amulet"
+};
+
+#define NSTR lenof(strings)
+
+int findtest(void) {
+ const static int rels[] = {
+ REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
+ };
+ const static char *const relnames[] = {
+ "EQ", "GE", "LE", "LT", "GT"
+ };
+ int i, j, rel, index;
+ char *p, *ret, *realret, *realret2;
+ int lo, hi, mid, c;
+
+ for (i = 0; i < NSTR; i++) {
+ p = strings[i];
+ for (j = 0; j < sizeof(rels)/sizeof(*rels); j++) {
+ rel = rels[j];
+
+ lo = 0; hi = arraylen-1;
+ while (lo <= hi) {
+ mid = (lo + hi) / 2;
+ c = strcmp(p, array[mid]);
+ if (c < 0)
+ hi = mid-1;
+ else if (c > 0)
+ lo = mid+1;
+ else
+ break;
+ }
+
+ if (c == 0) {
+ if (rel == REL234_LT)
+ ret = (mid > 0 ? array[--mid] : NULL);
+ else if (rel == REL234_GT)
+ ret = (mid < arraylen-1 ? array[++mid] : NULL);
+ else
+ ret = array[mid];
+ } else {
+ assert(lo == hi+1);
+ if (rel == REL234_LT || rel == REL234_LE) {
+ mid = hi;
+ ret = (hi >= 0 ? array[hi] : NULL);
+ } else if (rel == REL234_GT || rel == REL234_GE) {
+ mid = lo;
+ ret = (lo < arraylen ? array[lo] : NULL);
+ } else
+ ret = NULL;
+ }
+
+ realret = findrelpos234(tree, p, NULL, rel, &index);
+ if (realret != ret) {
+ error("find(\"%s\",%s) gave %s should be %s",
+ p, relnames[j], realret, ret);
+ }
+ if (realret && index != mid) {
+ error("find(\"%s\",%s) gave %d should be %d",
+ p, relnames[j], index, mid);
+ }
+ if (realret && rel == REL234_EQ) {
+ realret2 = index234(tree, index);
+ if (realret2 != realret) {
+ error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
+ p, relnames[j], realret, index, index, realret2);
+ }
+ }
+#if 0
+ printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
+ realret, index);
+#endif
+ }
+ }
+
+ realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
+ if (arraylen && (realret != array[0] || index != 0)) {
+ error("find(NULL,GT) gave %s(%d) should be %s(0)",
+ realret, index, array[0]);
+ } else if (!arraylen && (realret != NULL)) {
+ error("find(NULL,GT) gave %s(%d) should be NULL",
+ realret, index);
+ }
+
+ realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
+ if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
+ error("find(NULL,LT) gave %s(%d) should be %s(0)",
+ realret, index, array[arraylen-1]);
+ } else if (!arraylen && (realret != NULL)) {
+ error("find(NULL,LT) gave %s(%d) should be NULL",
+ realret, index);
+ }
+}
+