+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);
+ }
+}
+
+int main(void)
+{