quickjs-tart

quickjs-based runtime for wallet-core logic
Log | Files | Refs | README | LICENSE

unit1309.c (3707B)

      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 "unitcheck.h"
     25 
     26 #include "splay.h"
     27 
     28 static void splayprint(struct Curl_tree *t, int d, char output)
     29 {
     30   struct Curl_tree *node;
     31   int i;
     32   int count;
     33   if(!t)
     34     return;
     35 
     36   splayprint(t->larger, d + 1, output);
     37   for(i = 0; i < d; i++)
     38     if(output)
     39       printf("  ");
     40 
     41   if(output) {
     42     printf("%ld.%ld[%d]", (long)t->key.tv_sec,
     43            (long)t->key.tv_usec, i);
     44   }
     45 
     46   for(count = 0, node = t->samen; node != t; node = node->samen, count++)
     47     ;
     48 
     49   if(output) {
     50     if(count)
     51       printf(" [%d more]\n", count);
     52     else
     53       printf("\n");
     54   }
     55 
     56   splayprint(t->smaller, d + 1, output);
     57 }
     58 
     59 static CURLcode test_unit1309(char *arg)
     60 {
     61   UNITTEST_BEGIN_SIMPLE
     62 
     63 /* number of nodes to add to the splay tree */
     64 #define NUM_NODES 50
     65 
     66   struct Curl_tree *root, *removed;
     67   struct Curl_tree nodes[NUM_NODES*3];
     68   size_t storage[NUM_NODES*3];
     69   int rc;
     70   int i, j;
     71   struct curltime tv_now = {0, 0};
     72   root = NULL;              /* the empty tree */
     73 
     74   /* add nodes */
     75   for(i = 0; i < NUM_NODES; i++) {
     76     struct curltime key;
     77 
     78     key.tv_sec = 0;
     79     key.tv_usec = (541*i)%1023;
     80     storage[i] = key.tv_usec;
     81     Curl_splayset(&nodes[i], &storage[i]);
     82     root = Curl_splayinsert(key, root, &nodes[i]);
     83   }
     84 
     85   puts("Result:");
     86   splayprint(root, 0, 1);
     87 
     88   for(i = 0; i < NUM_NODES; i++) {
     89     int rem = (i + 7)%NUM_NODES;
     90     printf("Tree look:\n");
     91     splayprint(root, 0, 1);
     92     curl_mprintf("remove pointer %d, payload %zu\n", rem,
     93                  *(size_t *)Curl_splayget(&nodes[rem]));
     94     rc = Curl_splayremove(root, &nodes[rem], &root);
     95     if(rc) {
     96       /* failed! */
     97       printf("remove %d failed!\n", rem);
     98       fail("remove");
     99     }
    100   }
    101 
    102   fail_unless(root == NULL, "tree not empty after removing all nodes");
    103 
    104   /* rebuild tree */
    105   for(i = 0; i < NUM_NODES; i++) {
    106     struct curltime key;
    107 
    108     key.tv_sec = 0;
    109     key.tv_usec = (541*i)%1023;
    110 
    111     /* add some nodes with the same key */
    112     for(j = 0; j <= i % 3; j++) {
    113       storage[i * 3 + j] = key.tv_usec*10 + j;
    114       Curl_splayset(&nodes[i * 3 + j], &storage[i * 3 + j]);
    115       root = Curl_splayinsert(key, root, &nodes[i * 3 + j]);
    116     }
    117   }
    118 
    119   removed = NULL;
    120   for(i = 0; i <= 1100; i += 100) {
    121     printf("Removing nodes not larger than %d\n", i);
    122     tv_now.tv_usec = i;
    123     root = Curl_splaygetbest(tv_now, root, &removed);
    124     while(removed) {
    125       curl_mprintf("removed payload %zu[%zu]\n",
    126                    *(size_t *)Curl_splayget(removed) / 10,
    127                    *(size_t *)Curl_splayget(removed) % 10);
    128       root = Curl_splaygetbest(tv_now, root, &removed);
    129     }
    130   }
    131 
    132   fail_unless(root == NULL, "tree not empty when it should be");
    133 
    134   UNITTEST_END_SIMPLE
    135 }