Return to unit1309.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / curl / tests / unit

Annotation of embedaddon/curl/tests/unit/unit1309.c, revision 1.1.1.1

1.1       misho       1: /***************************************************************************
                      2:  *                                  _   _ ____  _
                      3:  *  Project                     ___| | | |  _ \| |
                      4:  *                             / __| | | | |_) | |
                      5:  *                            | (__| |_| |  _ <| |___
                      6:  *                             \___|\___/|_| \_\_____|
                      7:  *
                      8:  * Copyright (C) 1998 - 2018, 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:   size_t storage[NUM_NODES*3];
                     77:   int rc;
                     78:   int i, j;
                     79:   struct curltime tv_now = {0, 0};
                     80:   root = NULL;              /* the empty tree */
                     81: 
                     82:   /* add nodes */
                     83:   for(i = 0; i < NUM_NODES; i++) {
                     84:     struct curltime key;
                     85: 
                     86:     key.tv_sec = 0;
                     87:     key.tv_usec = (541*i)%1023;
                     88:     storage[i] = key.tv_usec;
                     89:     nodes[i].payload = &storage[i];
                     90:     root = Curl_splayinsert(key, root, &nodes[i]);
                     91:   }
                     92: 
                     93:   puts("Result:");
                     94:   splayprint(root, 0, 1);
                     95: 
                     96:   for(i = 0; i < NUM_NODES; i++) {
                     97:     int rem = (i + 7)%NUM_NODES;
                     98:     printf("Tree look:\n");
                     99:     splayprint(root, 0, 1);
                    100:     printf("remove pointer %d, payload %zu\n", rem,
                    101:            *(size_t *)nodes[rem].payload);
                    102:     rc = Curl_splayremovebyaddr(root, &nodes[rem], &root);
                    103:     if(rc) {
                    104:       /* failed! */
                    105:       printf("remove %d failed!\n", rem);
                    106:       fail("remove");
                    107:     }
                    108:   }
                    109: 
                    110:   fail_unless(root == NULL, "tree not empty after removing all nodes");
                    111: 
                    112:   /* rebuild tree */
                    113:   for(i = 0; i < NUM_NODES; i++) {
                    114:     struct curltime key;
                    115: 
                    116:     key.tv_sec = 0;
                    117:     key.tv_usec = (541*i)%1023;
                    118: 
                    119:     /* add some nodes with the same key */
                    120:     for(j = 0; j <= i % 3; j++) {
                    121:       storage[i * 3 + j] = key.tv_usec*10 + j;
                    122:       nodes[i * 3 + j].payload = &storage[i * 3 + j];
                    123:       root = Curl_splayinsert(key, root, &nodes[i * 3 + j]);
                    124:     }
                    125:   }
                    126: 
                    127:   removed = NULL;
                    128:   for(i = 0; i <= 1100; i += 100) {
                    129:     printf("Removing nodes not larger than %d\n", i);
                    130:     tv_now.tv_usec = i;
                    131:     root = Curl_splaygetbest(tv_now, root, &removed);
                    132:     while(removed != NULL) {
                    133:       printf("removed payload %zu[%zu]\n",
                    134:              (*(size_t *)removed->payload) / 10,
                    135:              (*(size_t *)removed->payload) % 10);
                    136:       root = Curl_splaygetbest(tv_now, root, &removed);
                    137:     }
                    138:   }
                    139: 
                    140:   fail_unless(root == NULL, "tree not empty when it should be");
                    141: 
                    142: UNITTEST_STOP