-int main(void) {
- tree234 *t = newtree234(cmp);
-
- add234(t, "Richard");
- add234(t, "Of");
- add234(t, "York");
- add234(t, "Gave");
- add234(t, "Battle");
- add234(t, "In");
- add234(t, "Vain");
- add234(t, "Rabbits");
- add234(t, "On");
- add234(t, "Your");
- add234(t, "Garden");
- add234(t, "Bring");
- add234(t, "Invisible");
- add234(t, "Vegetables");
-
- ptree(t);
- del234(t, find234(t, "Richard", NULL));
- ptree(t);
- del234(t, find234(t, "Of", NULL));
- ptree(t);
- del234(t, find234(t, "York", NULL));
- ptree(t);
- del234(t, find234(t, "Gave", NULL));
- ptree(t);
- del234(t, find234(t, "Battle", NULL));
- ptree(t);
- del234(t, find234(t, "In", NULL));
- ptree(t);
- del234(t, find234(t, "Vain", NULL));
- ptree(t);
- del234(t, find234(t, "Rabbits", NULL));
- ptree(t);
- del234(t, find234(t, "On", NULL));
- ptree(t);
- del234(t, find234(t, "Your", NULL));
- ptree(t);
- del234(t, find234(t, "Garden", NULL));
- ptree(t);
- del234(t, find234(t, "Bring", NULL));
- ptree(t);
- del234(t, find234(t, "Invisible", NULL));
- ptree(t);
- del234(t, find234(t, "Vegetables", NULL));
- ptree(t);
+#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);
+ }
+}
+
+int main(void)
+{
+ int in[NSTR];
+ int i, j, k;
+ unsigned seed = 0;
+
+ for (i = 0; i < NSTR; i++)
+ in[i] = 0;
+ array = NULL;
+ arraylen = arraysize = 0;
+ tree = newtree234(mycmp);
+ cmp = mycmp;
+
+ verify();
+ for (i = 0; i < 10000; i++) {
+ j = randomnumber(&seed);
+ j %= NSTR;
+ printf("trial: %d\n", i);
+ if (in[j]) {
+ printf("deleting %s (%d)\n", strings[j], j);
+ deltest(strings[j]);
+ in[j] = 0;
+ } else {
+ printf("adding %s (%d)\n", strings[j], j);
+ addtest(strings[j]);
+ in[j] = 1;
+ }
+ findtest();
+ }
+
+ while (arraylen > 0) {
+ j = randomnumber(&seed);
+ j %= arraylen;
+ deltest(array[j]);
+ }
+
+ freetree234(tree);
+
+ /*
+ * Now try an unsorted tree. We don't really need to test
+ * delpos234 because we know del234 is based on it, so it's
+ * already been tested in the above sorted-tree code; but for
+ * completeness we'll use it to tear down our unsorted tree
+ * once we've built it.
+ */
+ tree = newtree234(NULL);
+ cmp = NULL;
+ verify();
+ for (i = 0; i < 1000; i++) {
+ printf("trial: %d\n", i);
+ j = randomnumber(&seed);
+ j %= NSTR;
+ k = randomnumber(&seed);
+ k %= count234(tree) + 1;
+ printf("adding string %s at index %d\n", strings[j], k);
+ addpostest(strings[j], k);
+ }
+ while (count234(tree) > 0) {
+ printf("cleanup: tree size %d\n", count234(tree));
+ j = randomnumber(&seed);
+ j %= count234(tree);
+ printf("deleting string %s from index %d\n", array[j], j);
+ delpostest(j);
+ }
+
+ return 0;