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     ! 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