1  /*
       2   * Simple trie interface
       3   *
       4   * Copyright (c) 2020-2021 Ákos Uzonyi <uzonyi.akos@gmail.com>
       5   * All rights reserved.
       6   *
       7   * SPDX-License-Identifier: LGPL-2.1-or-later
       8   */
       9  
      10  #ifndef STRACE_TRIE_H
      11  # define STRACE_TRIE_H
      12  
      13  # include <stdbool.h>
      14  # include <stdint.h>
      15  
      16  /**
      17   * Trie control structure.
      18   * Trie implemented here has the following properties:
      19   *  * It allows storing values of the same size, the size can vary from 1 bit to
      20   *    64 bit values (only power of 2 sizes are allowed).
      21   *  * The key can be up to 64 bits in size.
      22   *  * It has separate configuration for node size and data block size.
      23   *
      24   * How bits of key are used for different node levels:
      25   *
      26   *   highest bits                                                  lowest bits
      27   *  | node_key_bits | node_key_bits | ... | <remainder> | data_block_key_bits |
      28   *  \_________________________________________________________________________/
      29   *                                 key_size
      30   *
      31   * So, the remainder is used on the lowest non-data node level.
      32   *
      33   * As of now, it doesn't implement any mechanisms for resizing/changing key
      34   * size.  De-fragmentation is also unsupported currently.
      35   */
      36  struct trie {
      37  	/** Return value of trie_get if key is not found */
      38  	uint64_t empty_value;
      39  	/**
      40  	 * Empty value copied over to fill the whole uint64_t.
      41  	 * Pre-calculated in trie_create to be used in trie_create_data_block.
      42  	 */
      43  	uint64_t fill_value;
      44  
      45  	/** Pointer to root node */
      46  	void *data;
      47  
      48  	/** Key size in bits (0..64). */
      49  	uint8_t key_size;
      50  
      51  	/**
      52  	 * Size of the stored values in log2 bits (0..6).
      53  	 * (6: 64 bit values, 5: 32 bit values, ...)
      54  	 */
      55  	uint8_t item_size_lg;
      56  
      57  	/**
      58  	 * Number of bits in the key that make a symbol for a node.
      59  	 * (equals to log2 of the child count of the node)
      60  	 */
      61  	uint8_t node_key_bits;
      62  
      63  	/**
      64  	 * Number of bits in the key that make a symbol for the data block (leaf).
      65  	 * (equals to log2 of the value count stored in a data block)
      66  	 */
      67  	uint8_t data_block_key_bits;
      68  
      69  	/** The depth of the data block. Calculated from the values above */
      70  	uint8_t max_depth;
      71  };
      72  
      73  struct trie* trie_create(uint8_t key_size, uint8_t item_size_lg,
      74  			uint8_t node_key_bits, uint8_t data_block_key_bits,
      75  			uint64_t empty_value);
      76  
      77  bool trie_set(struct trie *t, uint64_t key, uint64_t val);
      78  uint64_t trie_get(struct trie *t, uint64_t key);
      79  
      80  typedef void (*trie_iterate_fn)(void *data, uint64_t key, uint64_t val);
      81  
      82  /**
      83   * Calls trie_iterate_fn for each key-value pair where
      84   * key is inside the [start, end] interval (inclusive).
      85   *
      86   * @param t        The trie.
      87   * @param start    The start of the key interval (inclusive).
      88   * @param end      The end of the key interval (inclusive).
      89   * @param fn       The function to be called.
      90   * @param fn_data  The value to be passed to fn.
      91   */
      92  uint64_t trie_iterate_keys(struct trie *t, uint64_t start, uint64_t end,
      93  			    trie_iterate_fn fn, void *fn_data);
      94  
      95  void trie_free(struct trie *t);
      96  
      97  #endif /* !STRACE_TRIE_H */