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 30static CURLcode unit_setup(void) 31{ 32 return CURLE_OK; 33} 34 35static void unit_stop(void) 36{ 37 38} 39 40static 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 71UNITTEST_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 nodes[i].payload = &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 *)nodes[rem].payload); 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 nodes[i * 3 + j].payload = &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 *)removed->payload) / 10, 137 (*(size_t *)removed->payload) % 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 144UNITTEST_STOP 145