test/avltest.c

   1 /*
   2     Copyright © 2008 The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     Desc: Test AVL balanced tree interface.
   6     Lang: english
   7 */
   8 #define  DEBUG  1
   9 #include <aros/debug.h>
  10
  11 #include <exec/memory.h>
  12 #include <dos/dos.h>
  13 #include <dos/exall.h>
  14 #include <dos/datetime.h>
  15 #include <proto/dos.h>
  16 #include <proto/utility.h>
  17 #include <utility/tagitem.h>
  18 #include <utility/utility.h>
  19
  20 #include <proto/alib.h>
  21 #include <proto/exec.h>
  22 #include <proto/dos.h>
  23
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <stdlib.h>
  27 #include <memory.h>
  28
  29 static const char version[] = "$VER: avltest.c 45.0 (25.2.2008)\n";
  30
  31 #define MAX(x, y) ((x)>(y) ? (x) : (y))
  32 #define RCOUNT (100000)
  33
  34 struct testnode {
  35         struct AVLNode node;
  36
  37         int key;
  38 };
  39
  40 void *mempool;
  41 struct AVLNode *root;
  42 int *shuffle;
  43
  44 AROS_UFH2S(LONG, nodecmp_int,
  45           AROS_UFHA(const struct AVLNode *, avlnode1,  A0),
  46           AROS_UFHA(const struct AVLNode *, avlnode2,  A1))
  47 {
  48         AROS_USERFUNC_INIT;
  49
  50         const struct testnode *n1 = (const struct testnode *)avlnode1;
  51         const struct testnode *n2 = (const struct testnode *)avlnode2;
  52
  53         return n1->key - n2->key;
  54
  55         AROS_USERFUNC_EXIT;
  56 }
  57
  58 static LONG nodecmp_int2(const struct AVLNode * avlnode1, const struct AVLNode *avlnode2)
  59 {
  60         const struct testnode *n1 = (const struct testnode *)avlnode1;
  61         const struct testnode *n2 = (const struct testnode *)avlnode2;
  62
  63         fflush(stdout);
  64
  65         return n1->key - n2->key;
  66 }
  67
  68 AROS_UFH2S(LONG, keycmp_int,
  69           AROS_UFHA(const struct AVLNode *, avlnode,  A0),
  70           AROS_UFHA(AVLKey,                 avlkey,   A1))
  71 {
  72         AROS_USERFUNC_INIT;
  73
  74         int key = (int)avlkey;
  75         const struct testnode *n = (const struct testnode *)avlnode;
  76
  77         return n->key - key;
  78
  79         AROS_USERFUNC_EXIT;
  80 }
  81
  82
  83 static int checkbalance(struct AVLNode *root)
  84 {
  85     int left, right;
  86
  87     if (root == NULL)
  88         return 0;
  89
  90     left = checkbalance(root->avl_link[0]);
  91     right = checkbalance(root->avl_link[1]);
  92
  93     if (right- left != root->avl_balance) {
  94         printf("** Tree not balanced at %p\n", root);
  95         DeletePool(mempool);
  96         exit(1);
  97
  98     }
  99
 100     return MAX(left, right)+1;
 101 }
 102
 103 static void dumporder(struct AVLNode *root)
 104 {
 105     struct AVLNode *scan = AVL_FindFirstNode(root);
 106
 107     printf("keys in order:\n");
 108     while (scan != NULL) {
 109         struct testnode *s = (struct testnode *)scan;
 110
 111         printf(" %d\n", s->key);
 112         scan = AVL_FindNextNodeByAddress(scan);
 113     }
 114 }
 115
 116 static void dumprorder(struct AVLNode *root)
 117 {
 118     struct AVLNode *scan = AVL_FindLastNode(root);
 119
 120     printf("keys in reverse order:\n");
 121     while (scan != NULL) {
 122         struct testnode *s = (struct testnode *)scan;
 123
 124         printf(" %d\n", s->key);
 125         scan = AVL_FindPrevNodeByAddress(scan);
 126     }
 127 }
 128
 129 struct testnode *newnode()
 130 {
 131     struct testnode *node = AllocPooled(mempool, sizeof(struct testnode));
 132
 133     if (node == NULL) {
 134         fprintf(stdout, "AllocPooled failed\n");
 135         fflush(stdout);
 136         DeletePool(mempool);
 137         free(shuffle);
 138         exit(EXIT_FAILURE);
 139     }
 140
 141     return node;
 142 }
 143
 144 struct AVLNode *resetTree()
 145 {
 146     if (mempool)
 147         DeletePool(mempool);
 148     mempool = CreatePool(0, sizeof(struct testnode)*32, sizeof(struct testnode)*32);
 149
 150     if (mempool == NULL) {
 151         fprintf(stdout, "CreatePool failed\n");
 152         fflush(stdout);
 153         exit(EXIT_FAILURE);
 154     }
 155
 156     return NULL;
 157 }
 158
 159 int main(int argc, char **argv)
 160 {
 161     int i;
 162
 163     shuffle = malloc(sizeof(shuffle[0]) * RCOUNT);
 164     if (shuffle == NULL)
 165         return EXIT_FAILURE;
 166
 167     root = resetTree();
 168
 169     for (i =0;i<10;i++) {
 170         struct testnode *n;
 171
 172         n = newnode();
 173         n->key = i;
 174
 175         printf("Add node %d\n", i);
 176         AVL_AddNode(&root, &n->node, nodecmp_int2);
 177     }
 178
 179     dumporder(root);
 180     dumprorder(root);
 181
 182     printf("remove by key\n");
 183     for (i = 0;i<10;i++) {
 184         AVL_RemNodeByKey(&root, (AVLKey)i, keycmp_int);
 185     }
 186
 187     dumporder(root);
 188     dumprorder(root);
 189
 190     printf("find next node by key\n");
 191     root = resetTree();
 192     for (i =0;i<20;i+=2) {
 193         struct testnode *n;
 194
 195         n = newnode();
 196         n->key = i;
 197
 198         printf("Add node %d\n", i);
 199         AVL_AddNode(&root, &n->node, nodecmp_int);
 200     }
 201
 202     for (i =0;i<20;i++) {
 203         struct testnode *n = (struct testnode *)AVL_FindNextNodeByKey(root, (AVLKey)i, keycmp_int);
 204         int next;
 205
 206         printf("next node %d = %d\n", i, n ? n->key : -1);
 207
 208         if ((i % 2) == 0)
 209             next = i;
 210         else
 211             next = i + 1;
 212
 213         if ((n != NULL && n->key != next)
 214             || (n == NULL && i != 19))
 215             printf("next node by key is wrong!  got %d expected %d\n", (n == NULL ? -1 : n->key), i+1);
 216     }
 217
 218     root = resetTree();
 219     root = NULL;
 220     printf("insert reverse order\n");
 221     for (i =9;i>=0;i--) {
 222         struct testnode *n;
 223
 224         n = newnode();
 225         n->key = i;
 226
 227         AVL_AddNode(&root, &n->node, nodecmp_int);
 228     }
 229
 230     dumporder(root);
 231     dumprorder(root);
 232
 233     printf("remove by key\n");
 234     for (i = 0;i<10;i++) {
 235         AVL_RemNodeByKey(&root, (AVLKey)i, keycmp_int);
 236     }
 237
 238     dumporder(root);
 239     dumprorder(root);
 240
 241     // root should now be empty
 242     if (root != NULL) {
 243         printf("tree not empty!?");
 244     }
 245
 246     root = resetTree();
 247     srandom(0);
 248     printf("insert random order\n");
 249     for (i = 0;i<RCOUNT;i++)
 250         shuffle[i] = i;
 251     for (i = 0;i<RCOUNT;i++) {
 252         int f = random() % RCOUNT;
 253         int t = random() % RCOUNT;
 254         int tmp;
 255
 256         tmp = shuffle[f];
 257         shuffle[f] = shuffle[t];
 258         shuffle[t] = tmp;
 259     }
 260     //for (i=0;i<RCOUNT;i++) {
 261     //printf(" %d\n", shuffle[i]);
 262     //}
 263
 264     for (i=0;i<RCOUNT;i++) {
 265         struct testnode *n;
 266
 267         n = newnode();
 268         n->key = shuffle[i];
 269
 270         AVL_AddNode(&root, &n->node, nodecmp_int);
 271     }
 272
 273     //dumporder(root);
 274     //dumprorder(root);
 275
 276     srandom(1);
 277     root = resetTree();
 278
 279     printf("remove random order\n");
 280     for (i = 0;i<RCOUNT;i++) {
 281         struct testnode *n;
 282
 283         shuffle[i] = i;
 284
 285         n = newnode();
 286         n->key = i;
 287
 288         AVL_AddNode(&root, &n->node, nodecmp_int);
 289         if ((i % 256) == 0)
 290             checkbalance(root);
 291     }
 292     for (i = 0;i<RCOUNT;i++) {
 293         int f = random() % RCOUNT;
 294         int t = random() % RCOUNT;
 295         int tmp;
 296
 297         tmp = shuffle[f];
 298         shuffle[f] = shuffle[t];
 299         shuffle[t] = tmp;
 300     }
 301
 302     for (i=0;i<RCOUNT;i++) {
 303         AVL_RemNodeByKey(&root, (AVLKey)shuffle[i], keycmp_int);
 304         if ((i % 256) == 0)
 305             checkbalance(root);
 306     }
 307
 308     DeletePool(mempool);
 309     free(shuffle);
 310
 311     return EXIT_SUCCESS;
 312 }
 313