Return to unit1309.c CVS log

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

curl

    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