Documentation
¶
Overview ¶
Copyright (c) 2025 Stefano Scafiti
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Index ¶
Constants ¶
const ( // TableSize represents the fixed size of the internal hash table. // This value (2^16) is chosen to map directly to the uint16 hash space. TableSize = 65536 // Or 1 << 16 for clarity of its power-of-2 nature )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PrefixTable ¶
type PrefixTable[T any] struct { // contains filtered or unexported fields }
PrefixTable is a generic data structure that stores key-value pairs and allows for efficient prefix-based lookups and traversals. It uses a custom hashing mechanism to map byte prefixes to an internal 65536-byte (2^16) array, optimizing for small, byte-array keys. The `T` type parameter allows it to store any kind of value.
func New ¶
func New[T any]() *PrefixTable[T]
New creates and returns a new initialized PrefixTable. It allocates the internal map for storing elements.
func (*PrefixTable[T]) Get ¶
func (t *PrefixTable[T]) Get(key []byte) (T, bool)
Get retrieves the value associated with a given `key` from the PrefixTable.
It returns the value of type T and a boolean indicating whether the key was found (`true`) or not (`false`).
func (*PrefixTable[T]) Insert ¶
func (t *PrefixTable[T]) Insert(key []byte, v T)
Insert adds a new key-value pair to the PrefixTable.
The `key` is a byte slice, and `v` is the value of generic type T.
During insertion, it iterates through the `key` bytes, updating the internal `table` array. For each prefix of the key, it updates the corresponding hash entry in `table` to at least `presentMarker`. The entry corresponding to the full `key` is marked as `elemMarker`. Finally, the key-value pair is stored in the `elems` map.
The hashing mechanism `h = (h << 2) + uint16(v)` effectively uses a 2-bit shift for each byte, allowing up to 8 bytes (16 bits / 2 bits_per_byte) of key information to directly influence the 16-bit hash, though longer keys will cause hash collisions at the 16-bit boundary. This is suitable for relatively short keys or scenarios where the first 8 bytes provide sufficient distinction for prefix matching.
func (*PrefixTable[T]) Size ¶
func (t *PrefixTable[T]) Size() int
Size returns the number of unique key-value pairs currently stored in the table.
func (*PrefixTable[T]) Walk ¶
func (t *PrefixTable[T]) Walk(key []byte, onMatch func(T) bool)
Walk traverses the `PrefixTable` using a given `key` and executes the `onMatch` function for every complete key stored in the table that is a prefix of your `key`.
For example, if your table contains "apple", "applet", and "apricot":
- If you call `Walk("appletie", onMatch)`, `onMatch` will be called twice: first for "apple", and then for "applet".
- If you call `Walk("apricot", onMatch)`, `onMatch` will be called once for "apricot".
- If you call `Walk("application", onMatch)`, `onMatch` will not be called at all.
The traversal stops as soon as a part of your `key` does not match any prefix in the table.
Source Files