1  /*
       2   * Copyright (c) 2017-2020 The strace developers.
       3   * All rights reserved.
       4   *
       5   * SPDX-License-Identifier: GPL-2.0-or-later
       6   */
       7  
       8  #include "tests.h"
       9  #include "trie.h"
      10  
      11  #include <stdio.h>
      12  #include <inttypes.h>
      13  
      14  static void
      15  assert_equals(const char *msg, uint64_t expected, uint64_t actual) {
      16  	if (actual != expected)
      17  		error_msg_and_fail("%s: expected: %" PRIu64
      18  		                   ", actual: %" PRIu64, msg, expected, actual);
      19  }
      20  
      21  static void
      22  iterate_fn(void *data, uint64_t key, uint64_t value)
      23  {
      24  	uint64_t expected = key < 256 && key % 10 == 0 ? key + 42 : -1ULL;
      25  	assert_equals("iterate_fn", expected, value);
      26  
      27  	int *count = (int *) data;
      28  	if (value != -1ULL)
      29  		(*count)++;
      30  }
      31  
      32  static void
      33  test_trie_iterate_fn(void)
      34  {
      35  	struct trie *t = trie_create(8, 6, 3, 3, -1);
      36  	for (int i = 0; i < 26; i++)
      37  		trie_set(t, i * 10, i * 10 + 42);
      38  
      39  	static const struct {
      40  		uint64_t start;
      41  		uint64_t end;
      42  		int expected_count;
      43  	} iterate_params[] = {
      44  		{0, 256, 26},
      45  		{0, UINT64_MAX, 26},
      46  		{20, 90, 8},
      47  		{99, 999, 16},
      48  		{10000, 100000, 0},
      49  		{200, 100, 0},
      50  	};
      51  
      52  	for (size_t i = 0; i < ARRAY_SIZE(iterate_params); i++) {
      53  		int count = 0;
      54  		trie_iterate_keys(t, iterate_params[i].start, iterate_params[i].end, iterate_fn, &count);
      55  		assert_equals("iteration count", iterate_params[i].expected_count, count);
      56  	}
      57  }
      58  
      59  struct key_value_pair {
      60  	uint64_t key, value;
      61  };
      62  
      63  static void
      64  test_trie_get(void)
      65  {
      66  	static const struct {
      67  		uint8_t key_size;
      68  		uint8_t item_size_lg;
      69  		uint8_t node_key_bits;
      70  		uint8_t data_block_key_bits;
      71  		uint64_t empty_value;
      72  
      73  		struct key_value_pair set_values[3], get_values[3];
      74  	} params[] = {
      75  		{64, 6, 10, 10, 0,
      76  			{{300, 1}, {0xfacefeed, 0xabcdef123456}, {-1ULL, -1ULL}},
      77  			{{301, 0}, {0xfacefeed, 0xabcdef123456}, {-1ULL, -1ULL}}},
      78  		{8, 2, 4, 4, 10,
      79  			{{0xab, 0xcd}, {0xface, 2}, {0, 3}},
      80  			{{0xab, 0xd}, {0xface, 10}, {0, 3}}},
      81  		{30, 0, 6, 3, -1,
      82  			{{0xaaaa, 127}, {0xface, 0}, {0, 0}},
      83  			{{0xaaaa, 1}, {0xface, 0}, {1, 1}}},
      84  		{16, 4, 5, 11, 0xffffff,
      85  			{{0xabcdef, 42}, {0xabcd, 42}, {0xffff, 0}},
      86  			{{0xabcdef, 0xffff}, {0xabcd, 42}, {0xffff, 0}}},
      87  		{41, 5, 1, 1, -1,
      88  			{{0xabcdef01, 0x22222222}, {-1, 0x33333333}, {10, 10}},
      89  			{{0xabcdef01, 0x22222222}, {-1, 0xffffffff}, {10, 10}}},
      90  	};
      91  
      92  	for (size_t i = 0; i < ARRAY_SIZE(params); i++) {
      93  		struct trie *t = trie_create(params[i].key_size,
      94  		                             params[i].item_size_lg,
      95  					     params[i].node_key_bits,
      96  					     params[i].data_block_key_bits,
      97  					     params[i].empty_value);
      98  
      99  		if (!t)
     100  			error_msg_and_fail("trie creation failed");
     101  
     102  		for (size_t j = 0; j < ARRAY_SIZE(params[i].set_values); j++) {
     103  			struct key_value_pair kv = params[i].set_values[j];
     104  			trie_set(t, kv.key, kv.value);
     105  		}
     106  		for (size_t j = 0; j < ARRAY_SIZE(params[i].get_values); j++) {
     107  			struct key_value_pair kv = params[i].get_values[j];
     108  			assert_equals("trie_get", kv.value, trie_get(t, kv.key));
     109  		}
     110  
     111  		trie_free(t);
     112  	}
     113  }
     114  
     115  int
     116  main(void)
     117  {
     118  	test_trie_get();
     119  	test_trie_iterate_fn();
     120  	return 0;
     121  }