Home | History | Annotate | Line # | Download | only in tests 
      1 /* Tests related to the hash tables used inside Expat
      2 __  __            _
      3                          ___\ \/ /_ __   __ _| |_
      4                         / _ \\  /| '_ \ / _` | __|
      5                        |  __//  \| |_) | (_| | |_
      6                         \___/_/\_\ .__/ \__,_|\__|
      7                                  |_| XML parser
      8 
      9    Copyright (c) 2026 Sebastian Pipping <sebastian (at) pipping.org>
     10    Licensed under the MIT license:
     11 
     12    Permission is  hereby granted,  free of charge,  to any  person obtaining
     13    a  copy  of  this  software   and  associated  documentation  files  (the
     14    "Software"),  to  deal in  the  Software  without restriction,  including
     15    without  limitation the  rights  to use,  copy,  modify, merge,  publish,
     16    distribute, sublicense, and/or sell copies of the Software, and to permit
     17    persons  to whom  the Software  is  furnished to  do so,  subject to  the
     18    following conditions:
     19 
     20    The above copyright  notice and this permission notice  shall be included
     21    in all copies or substantial portions of the Software.
     22 
     23    THE  SOFTWARE  IS  PROVIDED  "AS  IS",  WITHOUT  WARRANTY  OF  ANY  KIND,
     24    EXPRESS  OR IMPLIED,  INCLUDING  BUT  NOT LIMITED  TO  THE WARRANTIES  OF
     25    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
     26    NO EVENT SHALL THE AUTHORS OR  COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
     27    DAMAGES OR  OTHER LIABILITY, WHETHER  IN AN  ACTION OF CONTRACT,  TORT OR
     28    OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
     29    USE OR OTHER DEALINGS IN THE SOFTWARE.
     30 
     31    SPDX-License-Identifier: MIT
     32 */
     33 
     34 #include "hash_tests.h"
     35 
     36 #include "common.h" // for XCS
     37 #include "expat.h"
     38 #include "hash_table.h"
     39 #include "minicheck.h"
     40 
     41 #include <stdbool.h>
     42 #include <string.h> // for memcmp
     43 
     44 START_TEST(test_hash_table) {
     45   // The test is not doing any parsing, so a single run
     46   // (with `g_chunkSize == 0`) is enough
     47   if (g_chunkSize != 0)
     48     return;
     49 
     50   typedef struct {
     51     const XML_Char *name;
     52     bool initialized;
     53   } NAME_AND_FLAG;
     54 
     55   HASH_TABLE table;
     56   XML_Parser parser = XML_ParserCreate(NULL);
     57   hashTableInit(&table, parser);
     58 
     59   const XML_Char *const key1 = XCS("key1");
     60   const XML_Char *const key2 = XCS("key2");
     61   const XML_Char *const key3 = XCS("key1overlap");
     62 
     63   // Self-test: `key3` starts with `key1` but is different from it
     64   assert_true(memcmp(key1, key3, keylen(key1)) == 0);
     65   assert_true(keyeq(key1, keylen(key1), key3) == XML_FALSE);
     66 
     67   // Test: Look up false for all keys because the table is empty
     68   assert_true(lookup(parser, &table, key1, 0) == NULL);
     69   assert_true(lookup(parser, &table, key2, 0) == NULL);
     70   assert_true(lookup(parser, &table, key3, 0) == NULL);
     71 
     72   // Test: Iteration yields 0 items initially
     73   {
     74     HASH_TABLE_ITER iter1;
     75     hashTableIterInit(&iter1, &table);
     76     assert_true(hashTableIterNext(&iter1) == NULL);
     77   }
     78 
     79   // Test: Insertion works (including initialization to zero)
     80   NAME_AND_FLAG *const inserted1
     81       = (NAME_AND_FLAG *)lookup(parser, &table, key1, sizeof(NAME_AND_FLAG));
     82   assert_true(inserted1 != NULL);
     83   assert_true(inserted1->name == key1);
     84   assert_true(! inserted1->initialized);
     85 
     86   // Make it possible to tell the struct apart from a freshly inserted version
     87   inserted1->initialized = true;
     88 
     89   // Test: Only present keys can be looked up
     90   assert_true(lookup(parser, &table, key1, 0) != NULL);
     91   assert_true(lookup(parser, &table, key2, 0) == NULL);
     92   assert_true(lookup(parser, &table, key3, 0) == NULL);
     93 
     94   // Test: Key length works without false positives
     95   assert_true(lookupWithLength(parser, &table, key3, /*nameLen=*/3, 0) == NULL);
     96   assert_true(lookupWithLength(parser, &table, key3, /*nameLen=*/4, 0) != NULL);
     97   assert_true(lookupWithLength(parser, &table, key3, /*nameLen=*/5, 0) == NULL);
     98 
     99   // TEST: Lookup does not reset existing entries to zeros
    100   NAME_AND_FLAG *const found
    101       = (NAME_AND_FLAG *)lookup(parser, &table, key1, sizeof(NAME_AND_FLAG));
    102   assert_true(found != NULL);
    103   assert_true(found->name == key1);
    104   assert_true(found->initialized); // this is key
    105 
    106   // Test: Insertion of a second item works
    107   assert_true(lookup(parser, &table, key2, 0) == NULL);
    108   assert_true(lookup(parser, &table, key2, sizeof(NAME_AND_FLAG)) != NULL);
    109   assert_true(lookup(parser, &table, key2, 0) != NULL);
    110 
    111   // Test: Iteration yields nothing but the two expected items
    112   {
    113     HASH_TABLE_ITER iter2;
    114     hashTableIterInit(&iter2, &table);
    115     size_t itemCount = 0;
    116     while (true) {
    117       const NAME_AND_FLAG *const item
    118           = (const NAME_AND_FLAG *)hashTableIterNext(&iter2);
    119       if (item == NULL)
    120         break;
    121 
    122       itemCount++;
    123 
    124       if (keyeq(key1, keylen(key1), item->name) == XML_TRUE)
    125         assert_true(item->initialized);
    126       else if (keyeq(key2, keylen(key2), item->name) == XML_TRUE)
    127         assert_true(! item->initialized);
    128       else
    129         fail("unexpected item .name");
    130     }
    131     assert_true(itemCount == 2);
    132   }
    133 
    134   // Test: After clearing all lookups fail
    135   hashTableClear(&table);
    136   assert_true(lookup(parser, &table, key1, 0) == NULL);
    137   assert_true(lookup(parser, &table, key2, 0) == NULL);
    138   assert_true(lookup(parser, &table, key3, 0) == NULL);
    139 
    140   // Test: After clearing iteration yields 0 items again
    141   {
    142     HASH_TABLE_ITER iter3;
    143     hashTableIterInit(&iter3, &table);
    144     assert_true(hashTableIterNext(&iter3) == NULL);
    145   }
    146 
    147   hashTableDestroy(&table);
    148   XML_ParserFree(parser);
    149 }
    150 END_TEST
    151 
    152 void
    153 make_hash_test_case(Suite *s) {
    154   TCase *const tc_hash = tcase_create("hash tests");
    155   suite_add_tcase(s, tc_hash);
    156   tcase_add_test(tc_hash, test_hash_table);
    157 }
    158