tests/unit/unit1309.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2011, 2017, Daniel Stenberg, <daniel@haxx.se>, et al.
   9  *
  10  * This software is licensed as described in the file COPYING, which
  11  * you should have received as part of this distribution. The terms
  12  * are also available at https://curl.haxx.se/docs/copyright.html.
  13  *
  14  * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  15  * copies of the Software, and permit persons to whom the Software is
  16  * furnished to do so, under the terms of the COPYING file.
  17  *
  18  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19  * KIND, either express or implied.
  20  *
  21  ***************************************************************************/
  22 #include "curlcheck.h"
  23
  24 #include "splay.h"
  25 #include "warnless.h"
  26
  27
  28 static CURLcode unit_setup(void)
  29 {
  30   return CURLE_OK;
  31 }
  32
  33 static void unit_stop(void)
  34 {
  35
  36 }
  37
  38 static void splayprint(struct Curl_tree * t, int d, char output)
  39 {
  40   struct Curl_tree *node;
  41   int i;
  42   int count;
  43   if(t == NULL)
  44     return;
  45
  46   splayprint(t->larger, d + 1, output);
  47   for(i = 0; i<d; i++)
  48     if(output)
  49       printf("  ");
  50
  51   if(output) {
  52     printf("%ld.%ld[%d]", (long)t->key.tv_sec,
  53            (long)t->key.tv_usec, i);
  54   }
  55
  56   for(count = 0, node = t->samen; node != t; node = node->samen, count++)
  57     ;
  58
  59   if(output) {
  60     if(count)
  61       printf(" [%d more]\n", count);
  62     else
  63       printf("\n");
  64   }
  65
  66   splayprint(t->smaller, d + 1, output);
  67 }
  68
  69 UNITTEST_START
  70
  71 /* number of nodes to add to the splay tree */
  72 #define NUM_NODES 50
  73
  74   struct Curl_tree *root, *removed;
  75   struct Curl_tree nodes[NUM_NODES*3];
  76   int rc;
  77   int i, j;
  78   struct curltime tv_now = {0, 0};
  79   root = NULL;              /* the empty tree */
  80
  81   /* add nodes */
  82   for(i = 0; i < NUM_NODES; i++) {
  83     struct curltime key;
  84     size_t payload;
  85
  86     key.tv_sec = 0;
  87     key.tv_usec = (541*i)%1023;
  88     payload = (size_t) key.tv_usec;
  89
  90     /* for simplicity */
  91     nodes[i].payload = CURLX_INTEGER_TO_POINTER_CAST(payload);
  92     root = Curl_splayinsert(key, root, &nodes[i]);
  93   }
  94
  95   puts("Result:");
  96   splayprint(root, 0, 1);
  97
  98   for(i = 0; i < NUM_NODES; i++) {
  99     int rem = (i + 7)%NUM_NODES;
 100     printf("Tree look:\n");
 101     splayprint(root, 0, 1);
 102     printf("remove pointer %d, payload %ld\n", rem,
 103            CURLX_POINTER_TO_INTEGER_CAST(nodes[rem].payload));
 104     rc = Curl_splayremovebyaddr(root, &nodes[rem], &root);
 105     if(rc) {
 106       /* failed! */
 107       printf("remove %d failed!\n", rem);
 108       fail("remove");
 109     }
 110   }
 111
 112   fail_unless(root == NULL, "tree not empty after removing all nodes");
 113
 114   /* rebuild tree */
 115   for(i = 0; i < NUM_NODES; i++) {
 116     struct curltime key;
 117
 118     key.tv_sec = 0;
 119     key.tv_usec = (541*i)%1023;
 120
 121     /* add some nodes with the same key */
 122     for(j = 0; j <= i % 3; j++) {
 123       size_t payload = key.tv_usec*10 + j;
 124       /* for simplicity */
 125       nodes[i * 3 + j].payload = CURLX_INTEGER_TO_POINTER_CAST(payload);
 126       root = Curl_splayinsert(key, root, &nodes[i * 3 + j]);
 127     }
 128   }
 129
 130   removed = NULL;
 131   for(i = 0; i <= 1100; i += 100) {
 132     printf("Removing nodes not larger than %d\n", i);
 133     tv_now.tv_usec = i;
 134     root = Curl_splaygetbest(tv_now, root, &removed);
 135     while(removed != NULL) {
 136       printf("removed payload %ld[%ld]\n",
 137              CURLX_POINTER_TO_INTEGER_CAST(removed->payload) / 10,
 138              CURLX_POINTER_TO_INTEGER_CAST(removed->payload) % 10);
 139       root = Curl_splaygetbest(tv_now, root, &removed);
 140     }
 141   }
 142
 143   fail_unless(root == NULL, "tree not empty when it should be");
 144
 145 UNITTEST_STOP
 146
 147
 148
 149