Template for a class implementing a set of buckets containing elements
indexed by unique keys. The bucket set contains both a set of buckets and a
pool of bucket elements. The bucket elements are structured as linked lists,
thus each bucket simply contains a pointer to its first element.
The number of buckets in the set is always a power of 2. In this way the
getBucket() method, which determines which bucket is responsible for a key,
can use a simple bit mask instead of a modulo operation, leading to greater
efficiency.
The method of bucket element allocation and pool management can be
customised by passing a custom IAllocator implementation to the constructor.
The default implementation--the BucketSet.FreeBuckets class--uses
'new Bucket.Element' for allocation and manages the pool as a linked list of
bucket elements. Possible alternative implementations include leaving the
pool management up to an external memory manager such as the D or C runtime
library using 'new'/'delete' or malloc()/free(), respectively. Also, if the
maximum number of elements in the map is known in advance, all elements can
be preallocated in a row.
Usage:
See ocean.util.container.map.HashMap & ocean.util.container.map.HashSet
Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
Alternatively, this file may be distributed under the terms of the Tango
3-Clause BSD License (see LICENSE_BSD.txt for details).
Template for a class implementing a set of buckets containing elements indexed by unique keys. The bucket set contains both a set of buckets and a pool of bucket elements. The bucket elements are structured as linked lists, thus each bucket simply contains a pointer to its first element.
The number of buckets in the set is always a power of 2. In this way the getBucket() method, which determines which bucket is responsible for a key, can use a simple bit mask instead of a modulo operation, leading to greater efficiency.
The method of bucket element allocation and pool management can be customised by passing a custom IAllocator implementation to the constructor. The default implementation--the BucketSet.FreeBuckets class--uses 'new Bucket.Element' for allocation and manages the pool as a linked list of bucket elements. Possible alternative implementations include leaving the pool management up to an external memory manager such as the D or C runtime library using 'new'/'delete' or malloc()/free(), respectively. Also, if the maximum number of elements in the map is known in advance, all elements can be preallocated in a row.
Usage: See ocean.util.container.map.HashMap & ocean.util.container.map.HashSet