1 #ifndef HASH_TABLE_CLASS
2 #define HASH_TABLE_CLASS
31 template <
class key,
class contents>
class internal_hash_array;
65 template <
class key_type,
class contents>
119 bool find(
const key_type &key, contents * &item_found)
const;
125 contents *
find(
const key_type &key)
const
135 bool zap(
const key_type &key);
172 int c_estim_elements;
197 template <
class key_type,
class contents>
211 template <
class key_type,
class contents>
224 template <
class key_type,
class contents>
226 :
public basis::array<hash_wrapper<key_type, contents> >,
227 public virtual basis::root_object
234 int find(
const key_type &to_find) {
235 for (
int i = 0; i < this->
length(); i++) {
236 key_type *curr_key = this->
get(i)._id;
239 if (curr_key && (to_find == *curr_key))
242 return basis::common::NOT_FOUND;
248 template <
class key_type,
class contents>
254 (
hash_table<key_type, contents>::calculate_num_slots(estimated_elements)) {}
259 template <
class key_type,
class contents>
261 : c_estim_elements(estimated_elements),
262 _hasher(hasher.clone()),
267 template <
class key_type,
class contents>
270 #ifdef EXTREME_CHECKING
272 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
279 template <
class key_type,
class contents>
283 int log_2_truncated = int(log(
float(estimated_elements)) / log(2.0));
285 int slots_needed_for_elems = (int)pow(2.0,
double(log_2_truncated + 1));
287 return slots_needed_for_elems;
291 template <
class key_type,
class contents>
295 #ifdef EXTREME_CHECKING
298 deadly_error(class_name(), func,
"source state did not verify.");
301 for (
int i = 0; i < source.
table_access().elements(); i++) {
304 for (
int j = 0; j < buck->
length(); j++) {
305 target.
add(*((*buck)[j]._id),
new contents(*((*buck)[j]._data)));
308 #ifdef EXTREME_CHECKING
310 deadly_error(class_name(), func,
"target state did not verify.");
315 template <
class key_type,
class contents>
318 #ifdef EXTREME_CHECKING
320 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
323 for (
int i = 0; i < _table->elements(); i++) {
326 for (
int j = 0; j < buck->
length(); j++) {
334 #ifdef EXTREME_CHECKING
336 deadly_error(class_name(), func,
"state did not verify afterwards.");
340 template <
class key_type,
class contents>
343 for (
int i = 0; i < _table->elements(); i++) {
346 for (
int j = 0; j < buck->
length(); j++) {
361 template <
class key_type,
class contents>
366 template <
class key_type,
class contents>
369 #ifdef EXTREME_CHECKING
371 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
378 for (
int i = 0; i < _table->elements(); i++) {
379 buckie *b = _table->borrow(i);
381 for (
int j = b->length() - 1; j >= 0; j--) {
382 key_type *k = b->use(j)._id;
383 contents *c = b->use(j)._data;
392 _table->adjust(new_hash._table->elements());
393 for (
int q = 0; q < new_hash._table->elements(); q++)
394 _table->put(q, new_hash._table->acquire(q));
396 c_estim_elements = new_hash.c_estim_elements;
398 #ifdef EXTREME_CHECKING
400 deadly_error(class_name(), func,
"state did not verify afterwards.");
404 template <
class key_type,
class contents>
407 {
return add(
new key_type(key), to_store); }
409 template <
class key_type,
class contents>
411 contents *to_store,
bool check_dupes)
413 #ifdef EXTREME_CHECKING
415 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
418 basis::un_int hashed = _hasher->hash((
const void *)key,
sizeof(key_type));
420 hashed = hashed % _table->elements();
426 _table->
put(hashed, buck);
433 int indy = buck->
find(*key);
437 #ifdef EXTREME_CHECKING
439 deadly_error(class_name(), func,
"state did not verify afterwards.");
446 (*buck)[indy]._data = to_store;
447 #ifdef EXTREME_CHECKING
449 deadly_error(class_name(), func,
"state did not verify afterwards.");
454 template <
class key_type,
class contents>
456 (
const key_type &key, contents *to_store)
457 {
return add(
new key_type(key), to_store,
false); }
459 template <
class key_type,
class contents>
461 contents * &item_found)
const
463 #ifdef EXTREME_CHECKING
465 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
469 basis::un_int hashed = _hasher->hash((
const void *)&key,
sizeof(key));
471 hashed = hashed % _table->elements();
474 if (!buck)
return false;
475 int indy = buck->
find(key);
478 item_found = (*buck)[indy]._data;
482 template <
class key_type,
class contents>
485 #ifdef EXTREME_CHECKING
487 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
490 basis::un_int hashed = _hasher->hash((
const void *)&key,
sizeof(key));
492 hashed = hashed % _table->elements();
496 int indy = buck->
find(key);
498 contents *to_return = (*buck)[indy]._data;
500 buck->
zap(indy, indy);
501 #ifdef EXTREME_CHECKING
503 deadly_error(class_name(), func,
"state did not verify afterwards.");
508 template <
class key_type,
class contents>
511 #ifdef EXTREME_CHECKING
513 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
516 basis::un_int hashed = _hasher->hash((
const void *)&key,
sizeof(key));
518 hashed = hashed % _table->elements();
521 if (!buck)
return false;
522 int indy = buck->
find(key);
529 buck->
zap(indy, indy);
532 buck = _table->acquire(hashed);
535 #ifdef EXTREME_CHECKING
537 deadly_error(class_name(), func,
"state did not verify afterwards.");
542 template <
class key_type,
class contents>
546 #ifdef EXTREME_CHECKING
548 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
552 int posn = _last_iter;
553 while (bucks_seen++ < _table->elements()) {
554 if ( (posn < 0) || (posn >= _table->elements()) )
556 buckie *b = _table->borrow(posn);
562 for (
int j = 0; j < b->length(); j++) {
563 contents *c = b->
use(j)._data;
565 #ifdef EXTREME_CHECKING
566 deadly_error(
"hash_table",
"apply",
"logic error--missing pointer");
570 if (!to_apply(*b->use(j)._id, *c, data_link))
return;
575 template <
class key_type,
class contents>
578 #ifdef EXTREME_CHECKING
580 if (!verify())
deadly_error(class_name(), func,
"state did not verify.");
584 for (
int i = 0; i < _table->elements(); i++) {
587 to_return += buck->
length();
592 #undef static_class_name
Represents a sequential, ordered, contiguous collection of objects.
@ EXPONE
synonym for EXPONENTIAL_GROWTH.
@ SIMPLE_COPY
the contents can be memcpy'd and are not deep.
@ FLUSH_INVISIBLE
blanks out allocated but inaccessible elements.
outcome put(int index, const contents &to_put)
Stores an object at the index "index" in the array.
const hash_wrapper< key_type, contents > & get(int index) const
Accesses individual objects stored in "this" at the "index" position.
int length() const
Returns the current reported length of the allocated C array.
outcome zap(int start, int end)
Deletes from "this" the objects inclusively between "start" and "end".
contents & use(int index)
A non-constant version of get(); the returned object can be modified.
array(int number=0, const hash_wrapper< key_type, contents > *init=NULL_POINTER, int flags=EXPONENTIAL_GROWTH|FLUSH_INVISIBLE)
Constructs an array with room for "number" objects.
A clonable object knows how to make copy of itself.
Root object for any class that knows its own name.
Outcomes describe the state of completion for an operation.
int find(const key_type &to_find)
Implements hashing into buckets for quick object access.
bool apply_function(const key_type &key, contents ¤t, void *data_link)
the "apply_function" is what a user of the "apply" method must supply.
int elements() const
the number of valid items we found by traversing the hash table.
basis::outcome add(key_type *key, contents *to_store, bool check_dupes=true)
specialized add for a pre-existing pointer "key".
basis::outcome add(const key_type &key, contents *to_store)
Stores "to_store" into the table given its "key" for hashing.
internal_hash_array< key_type, contents > & table_access() const
special accessor for the copy_hash_table method only.
bool verify() const
returns true if the hash table is internally consistent.
DEFINE_CLASS_NAME("hash_table")
static int calculate_num_slots(int estimated_elements)
a helper method that lets us know what n is for how many 2^n slots we should have.
void apply(apply_function *to_apply, void *data_link)
Invokes the function "to_apply" on every entry in the table.
void rehash(int estimated_elements)
resizes the hashing structures to optimise for a new size of "estimated_elements".
contents * acquire(const key_type &key)
retrieves the contents held for "key" out of the table.
void reset()
removes all entries in the table and returns it to a pristine state.
bool find(const key_type &key, contents *&item_found) const
locates the item specified by the "key", if possible.
basis::outcome fast_dangerous_add(const key_type &key, contents *to_store)
Like the add method above, but doesn't check for duplicates.
hash_table(const hashing_algorithm &hasher, int estimated_elements)
Creates a table using the "hasher" that is ready to store "estimated_elements".
virtual ~hash_table()
destroys any objects left in the hash_table.
int estimated_elements() const
returns the size of table we're optimized for.
contents * find(const key_type &key) const
simplified form of above find() method.
bool zap(const key_type &key)
removes the entry with the "key" specified.
hash_wrapper(key_type *id=NULL_POINTER, contents *data=NULL_POINTER)
A hashing algorithm takes a key and derives a related integer from it.
virtual hashing_algorithm * clone() const =0
supports virtual construction of new algorithm objects.
virtual basis::un_int hash(const void *key_data, int key_length) const =0
returns a hash value based on the "key_data" and "key_length".
internal_hash_array(int estimated_elements)
#define deadly_error(c, f, i)
#define NULL_POINTER
The value representing a pointer to nothing.
#define FUNCDEF(func_in)
FUNCDEF sets the name of a function (and plugs it into the callstack).
The guards collection helps in testing preconditions and reporting errors.
void WHACK(contents *&ptr)
deletion with clearing of the pointer.
unsigned int un_int
Abbreviated name for unsigned integers.
bool negative(const type &a)
negative returns true if "a" is less than zero.
A dynamic container class that holds any kind of object via pointers.
void copy_hash_table(hash_table< key_type, contents > &target, const hash_table< key_type, contents > &source)
Copies the entire hash table, given a contents type that supports copying.