Bucket

Template to be mixed in to a bucket element. Contains the shared core members of a bucket element.

This template mixin is used so that we can use structs for the bucket elements rather than classes, thus avoiding the memory overhead of class instances. In the case of bucket elements, which could exist in quantities of many thousands, this is significant.

Using structs instead of classes means that we can't use an interface or base class, and the Bucket struct (below) has to simply assume that the Element struct has certain members. As it's purely internal, we can live with this.

struct Bucket (

size_t V

K = hash_t

) {

struct Element;

package

Element* first;

bool has_element();

Element* find(Element.Key key);

Element* add(Element.Key key, Element* new_element);

Element* add(Element* element);

Element* remove(K key);

}

Members

Functions

add Element* add(Element.Key key, Element* new_element): Adds a bucket element with key as key.
add Element* add(Element* element): Adds an element to the bucket.
find Element* find(Element.Key key): Looks up the element whose key equals key.
has_element bool has_element(): Tells whether there is at least one element in this bucket.
remove Element* remove(K key): Looks up the element corresponding to key in this bucket and removes it, if found.

Structs

Element struct Element: Bucket element type

Variables

first Element* first;: First bucket element

Parameters

V: value size (.sizeof of the value type), may be 0 to store no value
K: key type