/* * Copyright (c) 1987, 1988, 1989, 1990, 1991 Stanford University * Copyright (c) 1991 Silicon Graphics, Inc. * * Permission to use, copy, modify, distribute, and sell this software and * its documentation for any purpose is hereby granted without fee, provided * that (i) the above copyright notices and this permission notice appear in * all copies of the software and related documentation, and (ii) the names of * Stanford and Silicon Graphics may not be used in any advertising or * publicity relating to the software without the specific, prior written * permission of Stanford and Silicon Graphics. * * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. * * IN NO EVENT SHALL STANFORD OR SILICON GRAPHICS BE LIABLE FOR * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE * OF THIS SOFTWARE. * * 12.8.92 Christoph Streit: remove_all function added * modified for own purposes * * Generic object association table. */ #ifndef Table_H #define Table_H #include "Hash.h" #include "rcString.h" #if defined(__STDC__) || defined(__ANSI_CPP__) || defined(__DECCXX) #define __TableEntry(Table) Table##_Entry #define TableEntry(Table) __TableEntry(Table) #define __TableIterator(Table) Table##_Iterator #define TableIterator(Table) __TableIterator(Table) #else #define __TableEntry(Table) Table/**/_Entry #define TableEntry(Table) __TableEntry(Table) #define __TableIterator(Table) Table/**/_Iterator #define TableIterator(Table) __TableIterator(Table) #endif #define declareTable(Table,Key,Value) \ class TableEntry(Table); \ \ class Table { \ public: \ Table(int); \ ~Table(); \ \ int insert(const Key&, const Value&); \ int find(const Key&); \ int find_and_replace(const Key&, const Value&); \ int find_and_remove(const Key&, Value&); \ int lookup(const Key&, Value&); \ void remove(const Key&); \ void remove_all(); \ private: \ friend class TableIterator(Table); \ \ int size_; \ TableEntry(Table)** first_; \ TableEntry(Table)** last_; \ \ TableEntry(Table)*&probe(const Key&); \ }; \ \ class TableEntry(Table) { \ private: \ friend class Table; \ friend class TableIterator(Table); \ \ Key key_; \ Value value_; \ TableEntry(Table)* chain_; \ }; \ \ class TableIterator(Table) { \ public: \ TableIterator(Table)(const Table&); \ \ Key& cur_key(); \ Value& cur_value(); \ int more(); \ int next(); \ private: \ TableEntry(Table)* cur_; \ TableEntry(Table)** entry_; \ TableEntry(Table)** last_; \ }; \ \ inline Key& TableIterator(Table)::cur_key() { return cur_->key_; } \ inline Value& TableIterator(Table)::cur_value() { return cur_->value_; } \ inline int TableIterator(Table)::more() { return entry_ <= last_; } /* * Predefined hash functions */ inline unsigned long key_to_hash(long k) { return (unsigned long)k; } //inline unsigned long key_to_hash(const void* k) { return (unsigned long)k; } //inline unsigned long key_to_hash(const char* k) //{ return (unsigned long)hash(k); } inline unsigned long key_to_hash(const rcString& k) { return (unsigned long)hash((const char*) k); } /* * Table implementation */ #define implementTable(Table,Key,Value) \ Table::Table(int n) { \ for (size_ = 32; size_ < n; size_ <<= 1); \ first_ = new TableEntry(Table)*[size_]; \ --size_; \ last_ = &first_[size_]; \ for (register TableEntry(Table)** e = first_; e <= last_; e++) { \ *e = NULL; \ } \ } \ \ Table::~Table() { \ delete first_; \ } \ \ inline TableEntry(Table)*& Table::probe(const Key &i) { \ return first_[key_to_hash(i) & size_]; \ } \ \ int Table::insert(const Key& k, const Value &v) { \ if (find(k)) return 0; \ \ register TableEntry(Table)* e = new TableEntry(Table); \ e->key_ = k; \ e->value_ = v; \ register TableEntry(Table)** a = &probe(k); \ e->chain_ = *a; \ *a = e; \ return 1;\ } \ \ int Table::lookup(const Key &k, Value &v) { \ for (register TableEntry(Table)* e = probe(k); e != NULL; e = e->chain_) { \ if (e->key_ == k) { \ v = e->value_; \ return 1; \ } \ } \ return 0; \ } \ \ int Table::find(const Key &k) { \ for (register TableEntry(Table)* e = probe(k); e != NULL; e = e->chain_) { \ if (e->key_ == k) { \ return 1; \ } \ } \ return 0; \ } \ \ int Table::find_and_replace(const Key& k, const Value& v) { \ for (register TableEntry(Table)* e = probe(k); e != NULL; e = e->chain_) { \ if (e->key_ == k) { \ e->value_ = v; \ return 1; \ } \ } \ return 0; \ } \ \ int Table::find_and_remove(const Key& k, Value& v) { \ TableEntry(Table)** a = &probe(k); \ register TableEntry(Table)* e = *a; \ if (e != NULL) { \ if (e->key_ == k) { \ v = e->value_; \ *a = e->chain_; \ delete e; \ return 1; \ } else { \ register TableEntry(Table)* prev; \ do { \ prev = e; \ e = e->chain_; \ } while (e != NULL && e->key_ != k); \ if (e != NULL) { \ v = e->value_; \ prev->chain_ = e->chain_; \ delete e; \ return 1; \ } \ } \ } \ return 0; \ } \ \ void Table::remove(const Key &k) { \ TableEntry(Table)** a = &probe(k); \ register TableEntry(Table)* e = *a; \ if (e != NULL) { \ if (e->key_ == k) { \ *a = e->chain_; \ delete e; \ } else { \ register TableEntry(Table)* prev; \ do { \ prev = e; \ e = e->chain_; \ } while (e != NULL && e->key_ != k); \ if (e != NULL) { \ prev->chain_ = e->chain_; \ delete e; \ } \ } \ } \ } \ \ void Table::remove_all() \ { \ TableIterator(Table) ti(*this); \ while (ti.more()) \ { \ remove(ti.cur_key()); \ ti.next(); \ } \ } \ \ TableIterator(Table)::TableIterator(Table)(const Table& t) { \ last_ = t.last_; \ for (entry_ = t.first_; entry_ <= last_; entry_++) { \ cur_ = *entry_; \ if (cur_ != NULL) { \ break; \ } \ } \ } \ \ int TableIterator(Table)::next() { \ cur_ = cur_->chain_; \ if (cur_ != NULL) { \ return 1; \ } \ for (++entry_; entry_ <= last_; entry_++) { \ cur_ = *entry_; \ if (cur_ != NULL) { \ return 1; \ } \ } \ return 0; \ } #endif // Table_H