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