1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1998 - 2011, 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
26
unit_setup(void)27 static CURLcode unit_setup(void)
28 {
29 return CURLE_OK;
30 }
31
unit_stop(void)32 static void unit_stop(void)
33 {
34
35 }
36
splayprint(struct Curl_tree * t,int d,char output)37 static void splayprint(struct Curl_tree * t, int d, char output)
38 {
39 struct Curl_tree *node;
40 int i;
41 int count;
42 if(t == NULL)
43 return;
44
45 splayprint(t->larger, d+1, output);
46 for(i=0; i<d; i++)
47 if(output)
48 printf(" ");
49
50 if(output) {
51 printf("%ld.%ld[%d]", (long)t->key.tv_sec,
52 (long)t->key.tv_usec, i);
53 }
54
55 for(count=0, node = t->same; node; node = node->same, count++)
56 ;
57
58 if(output) {
59 if(count)
60 printf(" [%d more]\n", count);
61 else
62 printf("\n");
63 }
64
65 splayprint(t->smaller, d+1, output);
66 }
67
68 UNITTEST_START
69
70 /* number of nodes to add to the splay tree */
71 #define NUM_NODES 50
72
73 struct Curl_tree *root;
74 struct Curl_tree nodes[NUM_NODES];
75 int rc;
76 int i;
77 root = NULL; /* the empty tree */
78
79 for(i = 0; i < NUM_NODES; i++) {
80 struct timeval key;
81
82 key.tv_sec = 0;
83 key.tv_usec = (541*i)%1023;
84
85 nodes[i].payload = (void *)key.tv_usec; /* for simplicity */
86 root = Curl_splayinsert(key, root, &nodes[i]);
87 }
88
89 puts("Result:");
90 splayprint(root, 0, 1);
91
92 for(i = 0; i < NUM_NODES; i++) {
93 int rem = (i+7)%NUM_NODES;
94 printf("Tree look:\n");
95 splayprint(root, 0, 1);
96 printf("remove pointer %d, payload %ld\n", rem,
97 (long)(nodes[rem].payload));
98 rc = Curl_splayremovebyaddr(root, &nodes[rem], &root);
99 if(rc) {
100 /* failed! */
101 printf("remove %d failed!\n", rem);
102 fail("remove");
103 }
104 }
105
106 UNITTEST_STOP
107
108
109
110
111