xref: /curl/tests/unit/unit1309.c (revision fbf5d507)
1 /***************************************************************************
2  *                                  _   _ ____  _
3  *  Project                     ___| | | |  _ \| |
4  *                             / __| | | | |_) | |
5  *                            | (__| |_| |  _ <| |___
6  *                             \___|\___/|_| \_\_____|
7  *
8  * Copyright (C) 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.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  * SPDX-License-Identifier: curl
22  *
23  ***************************************************************************/
24 #include "curlcheck.h"
25 
26 #include "splay.h"
27 #include "warnless.h"
28 
29 
unit_setup(void)30 static CURLcode unit_setup(void)
31 {
32   return CURLE_OK;
33 }
34 
unit_stop(void)35 static void unit_stop(void)
36 {
37 
38 }
39 
splayprint(struct Curl_tree * t,int d,char output)40 static void splayprint(struct Curl_tree *t, int d, char output)
41 {
42   struct Curl_tree *node;
43   int i;
44   int count;
45   if(!t)
46     return;
47 
48   splayprint(t->larger, d + 1, output);
49   for(i = 0; i < d; i++)
50     if(output)
51       printf("  ");
52 
53   if(output) {
54     printf("%ld.%ld[%d]", (long)t->key.tv_sec,
55            (long)t->key.tv_usec, i);
56   }
57 
58   for(count = 0, node = t->samen; node != t; node = node->samen, count++)
59     ;
60 
61   if(output) {
62     if(count)
63       printf(" [%d more]\n", count);
64     else
65       printf("\n");
66   }
67 
68   splayprint(t->smaller, d + 1, output);
69 }
70 
71 UNITTEST_START
72 
73 /* number of nodes to add to the splay tree */
74 #define NUM_NODES 50
75 
76   struct Curl_tree *root, *removed;
77   struct Curl_tree nodes[NUM_NODES*3];
78   size_t storage[NUM_NODES*3];
79   int rc;
80   int i, j;
81   struct curltime tv_now = {0, 0};
82   root = NULL;              /* the empty tree */
83 
84   /* add nodes */
85   for(i = 0; i < NUM_NODES; i++) {
86     struct curltime key;
87 
88     key.tv_sec = 0;
89     key.tv_usec = (541*i)%1023;
90     storage[i] = key.tv_usec;
91     Curl_splayset(&nodes[i], &storage[i]);
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 %zu\n", rem,
103            *(size_t *)Curl_splayget(&nodes[rem]));
104     rc = Curl_splayremove(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       storage[i * 3 + j] = key.tv_usec*10 + j;
124       Curl_splayset(&nodes[i * 3 + j], &storage[i * 3 + j]);
125       root = Curl_splayinsert(key, root, &nodes[i * 3 + j]);
126     }
127   }
128 
129   removed = NULL;
130   for(i = 0; i <= 1100; i += 100) {
131     printf("Removing nodes not larger than %d\n", i);
132     tv_now.tv_usec = i;
133     root = Curl_splaygetbest(tv_now, root, &removed);
134     while(removed) {
135       printf("removed payload %zu[%zu]\n",
136              *(size_t *)Curl_splayget(removed) / 10,
137              *(size_t *)Curl_splayget(removed) % 10);
138       root = Curl_splaygetbest(tv_now, root, &removed);
139     }
140   }
141 
142   fail_unless(root == NULL, "tree not empty when it should be");
143 
144 UNITTEST_STOP
145