"Fossies" - the Fresh Open Source Software Archive

Member "ical-tcl/types/testhash.C" (15 Apr 2019, 11896 Bytes) of package /linux/privat/ical-3.0.4.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /* Copyright (c) 1995 by Sanjay Ghemawat */
    2 // Tests for "HashTable".
    3 
    4 #include <assert.h>
    5 #include <stdlib.h>
    6 #include <stdio.h>
    7 #include <string.h>
    8 #include <limits.h>
    9 
   10 #define HTABLE_IMPLEMENT
   11 #define HTABLE          IntSet
   12 #define HKEY            int
   13 #define HASHER(x)       (x)
   14 #include "htable.h"
   15 
   16 typedef IntSet ISet;
   17 typedef IntSet::Elements ISet_Elements;
   18 
   19 //#define LOG_ASSERTS
   20 
   21 #ifdef LOG_ASSERTS
   22 #define ASSERT(x) do {fprintf(stderr, "ASSERT: %s\n", #x);assert(x);} while (0)
   23 #else
   24 #define ASSERT(x) assert(x)
   25 #endif
   26 
   27 #ifdef NDEBUG
   28 static void check(ISet& s) {}
   29 #else
   30 static void check(ISet& s) {s.check();}
   31 #endif
   32 
   33 /*
   34  * Check if M2 is a subset of M1.
   35  */
   36 static int subset(ISet& m1, ISet& m2) {
   37     int val;
   38     ISet_Elements i = &m1;
   39     while (i.get(val)) {
   40         if (! m2.contains(val)) return 0;
   41     }
   42     return 1;
   43 }
   44 
   45 /*
   46  * Compare two sets.
   47  */
   48 static int compare(ISet& m1, ISet& m2) {
   49     return (subset(m1, m2) && subset(m2, m1));
   50 }
   51 
   52 /*
   53  * Copy set contents into another set.
   54  */
   55 static void copy(ISet& m1, ISet& m2) {
   56     m2 = m1;
   57 }
   58 
   59 /*
   60  * Get set size by using iterators.
   61  */
   62 static int num_iterations(const ISet& m) {
   63     int count = 0;
   64     int val;
   65     ISet_Elements i = &m;
   66     while (i.get(val))
   67         count++;
   68     return count;
   69 }
   70 
   71 /*
   72  * Check that iteration over set yields specified key,value pair
   73  */
   74 static int iteration_contains(const ISet& m, int key) {
   75     int val;
   76     ISet_Elements i = &m;
   77     while (i.get(val)) {
   78         if (val == key) return 1;
   79     }
   80     return 0;
   81 }
   82 
   83 static void black_empty();
   84 static void black_single();
   85 static void black_multiple();
   86 
   87 static void black_box() {
   88     /*
   89      * Testing strategy -
   90      *
   91      * - Operations on empty sets.
   92      * - Operations on singleton sets.
   93      * - Operations on larger sets.
   94      */
   95 
   96     black_empty();
   97     black_single();
   98     black_multiple();
   99 }
  100 
  101 static void black_empty() {
  102     /* Empty set tests. */
  103 
  104     int i;
  105 
  106     ISet empty;
  107     check(empty);
  108 
  109     /* Check size */
  110     ASSERT(empty.size() == 0);
  111 
  112     /* Check contains */
  113     for (i = -3; i <= 3; i++) {
  114         ASSERT(! empty.contains(i));
  115     }
  116 
  117     /* Check iterator */
  118     {
  119         ASSERT(num_iterations(empty) == 0);
  120 
  121         ISet_Elements iter = &empty;
  122         int x;
  123         ASSERT(! iter.get(x));
  124     }
  125 
  126     /* Check copy */
  127     {
  128         ISet temp = empty;
  129         check(temp);
  130         ASSERT(compare(temp, empty));
  131     }
  132 
  133     /* Check insert */
  134     {
  135         ISet single;
  136         check(single);
  137         single.insert(1);
  138         check(single);
  139 
  140         ASSERT(single.size() == 1);
  141         ASSERT(single.contains(1));
  142         ASSERT(num_iterations(single) == 1);
  143 
  144         single.insert(1);
  145 
  146         ASSERT(single.size() == 1);
  147         ASSERT(single.contains(1));
  148         ASSERT(num_iterations(single) == 1);
  149     }
  150 
  151     /* Check remove */
  152     {
  153         ISet empty2;
  154         check(empty2);
  155 
  156         ASSERT(empty2.size() == 0);
  157         empty2.remove(1);
  158         check(empty2);
  159         ASSERT(empty2.size() == 0);
  160     }
  161 
  162     /* Check clear */
  163     {
  164         ISet empty2;
  165         check(empty2);
  166 
  167         ASSERT(empty2.size() == 0);
  168         empty2.insert(1);
  169         empty2.clear();
  170         check(empty2);
  171         ASSERT(empty2.size() == 0);
  172         compare(empty2, empty);
  173     }
  174 }
  175 
  176 static void black_single() {
  177     /* Single element set tests */
  178 
  179     int i;
  180 
  181     ISet single;
  182     check(single);
  183     single.insert(2);
  184     check(single);
  185 
  186     ASSERT(single.size() == 1);
  187 
  188     /* Check contains */
  189     for (i = -3; i <= 3; i++) {
  190         ASSERT(single.contains(i) == (i == 2));
  191     }
  192 
  193     /* Check iterator */
  194     {
  195         ASSERT(num_iterations(single) == 1);
  196         ASSERT(iteration_contains(single, 2));
  197     }
  198 
  199     /* Check copy */
  200     {
  201         ISet temp = single;
  202         check(temp);
  203         ASSERT(compare(temp, single));
  204 
  205         temp.remove(2);
  206         ASSERT(temp.size() == 0);
  207 
  208         ISet temp2 = temp;
  209         ASSERT(temp2.size() == 0);
  210     }
  211 
  212     /* Check insert */
  213     {
  214         ISet temp;
  215         check(temp);
  216         copy(single, temp);
  217         check(temp);
  218 
  219         ASSERT(temp.size() == 1);
  220         temp.insert(2);
  221         check(temp);
  222         ASSERT(temp.size() == 1);
  223         ASSERT(temp.contains(2));
  224 
  225         copy(single, temp);
  226         ASSERT(temp.size() == 1);
  227         temp.insert(3);
  228         check(temp);
  229         ASSERT(temp.size() == 2);
  230         ASSERT(temp.contains(2));
  231         ASSERT(temp.contains(3));
  232 
  233         ASSERT(num_iterations(temp) == 2);
  234         ASSERT(iteration_contains(temp, 2));
  235         ASSERT(iteration_contains(temp, 3));
  236 
  237         temp.insert(2);
  238         temp.insert(3);
  239         ASSERT(num_iterations(temp) == 2);
  240     }
  241 
  242     /* Check insert */
  243     {
  244         ISet temp;
  245         check(temp);
  246         copy(single, temp);
  247         check(temp);
  248 
  249         ASSERT(temp.size() == 1);
  250         temp.insert(3);
  251         check(temp);
  252         ASSERT(temp.size() == 2);
  253         ASSERT(temp.contains(2));
  254         ASSERT(temp.contains(3));
  255 
  256         ASSERT(num_iterations(temp) == 2);
  257         ASSERT(iteration_contains(temp, 2));
  258         ASSERT(iteration_contains(temp, 3));
  259     }
  260 
  261     /* Check remove */
  262     {
  263         ISet temp;
  264         check(temp);
  265         copy(single, temp);
  266         check(temp);
  267 
  268         temp.remove(5);
  269         check(temp);
  270         ASSERT(compare(temp, single));
  271         ASSERT(num_iterations(temp) == 1);
  272 
  273         temp.remove(2);
  274         check(temp);
  275         ASSERT(temp.size() == 0);
  276         ASSERT(! temp.contains(2));
  277         ASSERT(num_iterations(temp) == 0);
  278     }
  279 
  280     /* Check clear */
  281     {
  282         ISet temp;
  283         check(temp);
  284         copy(single, temp);
  285         check(temp);
  286 
  287         temp.clear();
  288         check(temp);
  289         ASSERT(temp.size() == 0);
  290         ASSERT(! temp.contains(2));
  291     }
  292 }
  293 
  294 static void black_multiple() {
  295     int i;
  296     ISet multi3, multi4, multi5;
  297 
  298     check(multi3);
  299     multi3.insert(1);
  300     check(multi3);
  301     multi3.insert(2);
  302     check(multi3);
  303     multi3.insert(3);
  304     check(multi3);
  305 
  306     check(multi4);
  307     multi4.insert(1);
  308     check(multi4);
  309     multi4.insert(2);
  310     check(multi4);
  311     multi4.insert(3);
  312     check(multi4);
  313     multi4.insert(4);
  314     check(multi4);
  315 
  316     check(multi5);
  317     multi5.insert(1);
  318     check(multi5);
  319     multi5.insert(2);
  320     check(multi5);
  321     multi5.insert(3);
  322     check(multi5);
  323     multi5.insert(4);
  324     check(multi5);
  325     multi5.insert(5);
  326     check(multi5);
  327 
  328     /* Check size */
  329     ASSERT(multi3.size() == 3);
  330     ASSERT(multi4.size() == 4);
  331     ASSERT(multi5.size() == 5);
  332 
  333     /* Check contains. */
  334     ASSERT(multi3.contains(1));
  335     ASSERT(multi3.contains(2));
  336     ASSERT(multi3.contains(3));
  337 
  338     ASSERT(multi4.contains(1));
  339     ASSERT(multi4.contains(2));
  340     ASSERT(multi4.contains(3));
  341     ASSERT(multi4.contains(4));
  342 
  343     ASSERT(multi5.contains(1));
  344     ASSERT(multi5.contains(2));
  345     ASSERT(multi5.contains(3));
  346     ASSERT(multi5.contains(3));
  347     ASSERT(multi5.contains(5));
  348 
  349     /* Check iterator */
  350     {
  351         ASSERT(num_iterations(multi3) == 3);
  352         ASSERT(iteration_contains(multi3, 1));
  353         ASSERT(iteration_contains(multi3, 2));
  354         ASSERT(iteration_contains(multi3, 3));
  355 
  356         ASSERT(num_iterations(multi4) == 4);
  357         ASSERT(iteration_contains(multi4, 1));
  358         ASSERT(iteration_contains(multi4, 2));
  359         ASSERT(iteration_contains(multi4, 3));
  360         ASSERT(iteration_contains(multi4, 4));
  361 
  362         ASSERT(num_iterations(multi5) == 5);
  363         ASSERT(iteration_contains(multi5, 1));
  364         ASSERT(iteration_contains(multi5, 2));
  365         ASSERT(iteration_contains(multi5, 3));
  366         ASSERT(iteration_contains(multi5, 4));
  367         ASSERT(iteration_contains(multi5, 5));
  368     }
  369 
  370     /* Check copy */
  371     {
  372         ISet temp1 = multi5;
  373         check(temp1);
  374         ASSERT(compare(temp1, multi5));
  375 
  376         temp1.remove(5);
  377         ISet temp2 = temp1;
  378         ASSERT(compare(temp2, multi4));
  379         ASSERT(num_iterations(temp2) == 4);
  380 
  381         temp2.remove(4);
  382         ISet temp3 = temp2;
  383         ASSERT(compare(temp3, multi3));
  384         ASSERT(num_iterations(temp3) == 3);
  385     }
  386 
  387     /* Check insert */
  388     {
  389         ISet temp;
  390         check(temp);
  391         copy(multi3, temp);
  392         check(temp);
  393 
  394         ASSERT(compare(multi3, temp));
  395 
  396         /* Insert existing element */
  397         temp.insert(2);
  398         check(temp);
  399         ASSERT(temp.size() == multi3.size());
  400         ASSERT(temp.contains(2));
  401         temp.remove(2);
  402         check(temp);
  403         temp.insert(2);
  404         check(temp);
  405         ASSERT(compare(multi3, temp));
  406 
  407         /* Insert non-existent element */
  408         copy(multi4, temp);
  409         check(temp);
  410         ASSERT(compare(multi4, temp));
  411         temp.insert(5);
  412         check(temp);
  413         ASSERT(compare(multi5, temp));
  414         temp.remove(5);
  415         check(temp);
  416         ASSERT(compare(multi4, temp));
  417     }
  418 
  419     /* Check insert */
  420     {
  421         ISet temp;
  422         check(temp);
  423         copy(multi4, temp);
  424         check(temp);
  425 
  426         ASSERT(compare(multi4, temp));
  427         ASSERT(temp.size() == 4);
  428         temp.insert(5);
  429         check(temp);
  430         ASSERT(compare(multi5, temp));
  431 
  432         copy(multi3, temp);
  433         temp.insert(4);
  434         check(temp);
  435         temp.insert(5);
  436         check(temp);
  437         ASSERT(compare(multi5, temp));
  438     }
  439 
  440     /* Check remove */
  441     {
  442         ISet temp, empty;
  443 
  444         /* Check removal of existing elements */
  445         check(temp);
  446         copy(multi3, temp);
  447         check(temp);
  448         ASSERT(compare(multi3, temp));
  449         temp.remove(1);
  450         check(temp);
  451         temp.remove(2);
  452         check(temp);
  453         temp.remove(3);
  454         check(temp);
  455         ASSERT(compare(empty, temp));
  456         ASSERT(num_iterations(temp) == 0);
  457 
  458         copy(multi3, temp);
  459         check(temp);
  460         ASSERT(compare(multi3, temp));
  461         temp.remove(3);
  462         check(temp);
  463         temp.remove(2);
  464         check(temp);
  465         temp.remove(1);
  466         check(temp);
  467         ASSERT(compare(empty, temp));
  468         ASSERT(num_iterations(temp) == 0);
  469 
  470         copy(multi5, temp);
  471         check(temp);
  472         ASSERT(compare(multi5, temp));
  473         temp.remove(5);
  474         check(temp);
  475         ASSERT(compare(multi4, temp));
  476         temp.remove(4);
  477         check(temp);
  478         ASSERT(compare(multi3, temp));
  479         temp.remove(1);
  480         check(temp);
  481         temp.remove(2);
  482         check(temp);
  483         temp.remove(3);
  484         check(temp);
  485         ASSERT(compare(empty, temp));
  486         ASSERT(num_iterations(temp) == 0);
  487 
  488         /* Check removal of non-existent elements */
  489         copy(multi4, temp);
  490         check(temp);
  491         for (i = -5; i <= 0; i++) {
  492             temp.remove(i);
  493             check(temp);
  494             ASSERT(compare(multi4, temp));
  495         }
  496         for (i = 5; i <= 10; i++) {
  497             temp.remove(i);
  498             check(temp);
  499             ASSERT(compare(multi4, temp));
  500         }
  501     }
  502 
  503     /* Check large number of entries */
  504     {
  505         ISet set;
  506 
  507         check(set);
  508         for (i = 0; i < 1000; i++) {
  509             set.insert(i);
  510             ASSERT(num_iterations(set) == i+1);
  511         }
  512         check(set);
  513 
  514         for (i = 0; i < 1000; i++) {
  515             ASSERT(set.contains(i));
  516         }
  517 
  518         for (i = 0; i < 1000; i++) {
  519             set.remove(i);
  520             ASSERT(num_iterations(set) == (999-i));
  521         }
  522         check(set);
  523     }
  524 
  525     /* Check prediction */
  526     {
  527         //ISet set(1000);
  528         ISet set;
  529 
  530         check(set);
  531         for (i = 0; i < 1000; i++) {
  532             set.insert(i);
  533             ASSERT(num_iterations(set) == i+1);
  534         }
  535         check(set);
  536 
  537         for (i = 0; i < 1000; i++) {
  538             ASSERT(set.contains(i));
  539         }
  540 
  541         for (i = 0; i < 1000; i++) {
  542             set.remove(i);
  543             ASSERT(num_iterations(set) == (999-i));
  544         }
  545         check(set);
  546     }
  547 }
  548 
  549 /*
  550  * Glass box tests.
  551  */
  552 static void glass_box() {
  553     // ...
  554 }
  555 
  556 int
  557 main() {
  558     black_box();
  559     glass_box();
  560     return 0;
  561 }