-
-\f
-////////////////////////////////////////////////////////////////////////
-// Simplified hash table for caching paths.
-////////////////////////////////////////////////////////////////////////
-
-#define HASH_TABLE_SIZE 199
-
-SGPropertyNode::hash_table::entry::entry ()
- : _value(0)
-{
-}
-
-SGPropertyNode::hash_table::entry::~entry ()
-{
- // Don't delete the value; we don't own
- // the pointer.
-}
-
-void
-SGPropertyNode::hash_table::entry::set_key (const char * key)
-{
- _key = key;
-}
-
-void
-SGPropertyNode::hash_table::entry::set_value (SGPropertyNode * value)
-{
- _value = value;
-}
-
-SGPropertyNode::hash_table::bucket::bucket ()
- : _length(0),
- _entries(0)
-{
-}
-
-SGPropertyNode::hash_table::bucket::~bucket ()
-{
- for (int i = 0; i < _length; i++)
- delete _entries[i];
- delete [] _entries;
-}
-
-SGPropertyNode::hash_table::entry *
-SGPropertyNode::hash_table::bucket::get_entry (const char * key, bool create)
-{
- int i;
- for (i = 0; i < _length; i++) {
- if (!strcmp(_entries[i]->get_key(), key))
- return _entries[i];
- }
- if (create) {
- entry ** new_entries = new entry*[_length+1];
- for (i = 0; i < _length; i++) {
- new_entries[i] = _entries[i];
- }
- delete [] _entries;
- _entries = new_entries;
- _entries[_length] = new entry;
- _entries[_length]->set_key(key);
- _length++;
- return _entries[_length - 1];
- } else {
- return 0;
- }
-}
-
-bool
-SGPropertyNode::hash_table::bucket::erase (SGPropertyNode * node)
-{
- for (int i = 0; i < _length; i++) {
- if (_entries[i]->get_value() == node) {
- delete _entries[i];
- for (++i; i < _length; i++) {
- _entries[i-1] = _entries[i];
- }
- _length--;
- return true;
- }
- }
- return false;
-}
-
-void
-SGPropertyNode::hash_table::bucket::clear (SGPropertyNode::hash_table * owner)
-{
- for (int i = 0; i < _length; i++) {
- SGPropertyNode * node = _entries[i]->get_value();
- if (node)
- node->remove_linked_node(owner);
- }
-}
-
-SGPropertyNode::hash_table::hash_table ()
- : _data_length(0),
- _data(0)
-{
-}
-
-SGPropertyNode::hash_table::~hash_table ()
-{
- for (unsigned int i = 0; i < _data_length; i++) {
- if (_data[i]) {
- _data[i]->clear(this);
- delete _data[i];
- }
- }
- delete [] _data;
-}
-
-SGPropertyNode *
-SGPropertyNode::hash_table::get (const char * key)
-{
- if (_data_length == 0)
- return 0;
- unsigned int index = hashcode(key) % _data_length;
- if (_data[index] == 0)
- return 0;
- entry * e = _data[index]->get_entry(key);
- if (e == 0)
- return 0;
- else
- return e->get_value();
-}
-
-void
-SGPropertyNode::hash_table::put (const char * key, SGPropertyNode * value)
-{
- if (_data_length == 0) {
- _data = new bucket*[HASH_TABLE_SIZE];
- _data_length = HASH_TABLE_SIZE;
- for (unsigned int i = 0; i < HASH_TABLE_SIZE; i++)
- _data[i] = 0;
- }
- unsigned int index = hashcode(key) % _data_length;
- if (_data[index] == 0) {
- _data[index] = new bucket;
- }
- entry * e = _data[index]->get_entry(key, true);
- e->set_value(value);
- value->add_linked_node(this);
-}
-
-bool
-SGPropertyNode::hash_table::erase (SGPropertyNode * node)
-{
- for (unsigned int i = 0; i < _data_length; i++)
- if (_data[i] && _data[i]->erase(node))
- return true;
-
- return false;
-}
-
-unsigned int
-SGPropertyNode::hash_table::hashcode (const char * key)
-{
- unsigned int hash = 0;
- while (*key != 0) {
- hash = 31 * hash + *key;
- key++;
- }
- return hash;
-}
-
-