home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / graphtal / table.h < prev    next >
C/C++ Source or Header  |  1992-10-28  |  7KB  |  263 lines
  1. /*
  2.  * Copyright (c) 1987, 1988, 1989, 1990, 1991 Stanford University
  3.  * Copyright (c) 1991 Silicon Graphics, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute, and sell this software and 
  6.  * its documentation for any purpose is hereby granted without fee, provided
  7.  * that (i) the above copyright notices and this permission notice appear in
  8.  * all copies of the software and related documentation, and (ii) the names of
  9.  * Stanford and Silicon Graphics may not be used in any advertising or
  10.  * publicity relating to the software without the specific, prior written
  11.  * permission of Stanford and Silicon Graphics.
  12.  * 
  13.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  14.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  15.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  16.  *
  17.  * IN NO EVENT SHALL STANFORD OR SILICON GRAPHICS BE LIABLE FOR
  18.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  19.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  20.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  21.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  22.  * OF THIS SOFTWARE.
  23.  *
  24.  * 12.8.92 Christoph Streit: remove_all function added
  25.  *                           modified for own purposes
  26.  *
  27.  * Generic object association table.
  28.  */
  29.  
  30. #ifndef Table_H
  31. #define  Table_H
  32.  
  33. #include "Hash.h"
  34. #include "rcString.h"
  35.  
  36. #if defined(__STDC__) || defined(__ANSI_CPP__) || defined(__DECCXX)
  37. #define __TableEntry(Table) Table##_Entry
  38. #define TableEntry(Table) __TableEntry(Table)
  39. #define __TableIterator(Table) Table##_Iterator
  40. #define TableIterator(Table) __TableIterator(Table)
  41. #else
  42. #define __TableEntry(Table) Table/**/_Entry
  43. #define TableEntry(Table) __TableEntry(Table)
  44. #define __TableIterator(Table) Table/**/_Iterator
  45. #define TableIterator(Table) __TableIterator(Table)
  46. #endif
  47.  
  48.  
  49. #define declareTable(Table,Key,Value) \
  50. class TableEntry(Table); \
  51. \
  52. class Table { \
  53. public: \
  54.     Table(int); \
  55.     ~Table(); \
  56. \
  57.     int insert(const Key&, const Value&); \
  58.     int find(const Key&); \
  59.     int find_and_replace(const Key&, const Value&); \
  60.     int find_and_remove(const Key&, Value&); \
  61.     int lookup(const Key&, Value&); \
  62.     void remove(const Key&); \
  63.     void remove_all(); \
  64. private: \
  65.     friend class TableIterator(Table); \
  66. \
  67.     int size_; \
  68.     TableEntry(Table)** first_; \
  69.     TableEntry(Table)** last_; \
  70. \
  71.     TableEntry(Table)*&probe(const Key&); \
  72. }; \
  73. \
  74. class TableEntry(Table) { \
  75. private: \
  76.     friend class Table; \
  77.     friend class TableIterator(Table); \
  78. \
  79.     Key key_; \
  80.     Value value_; \
  81.     TableEntry(Table)* chain_; \
  82. }; \
  83. \
  84. class TableIterator(Table) { \
  85. public: \
  86.     TableIterator(Table)(const Table&); \
  87. \
  88.     Key& cur_key(); \
  89.     Value& cur_value(); \
  90.     int more(); \
  91.     int next(); \
  92. private: \
  93.     TableEntry(Table)* cur_; \
  94.     TableEntry(Table)** entry_; \
  95.     TableEntry(Table)** last_; \
  96. }; \
  97. \
  98. inline Key& TableIterator(Table)::cur_key() { return cur_->key_; } \
  99. inline Value& TableIterator(Table)::cur_value() { return cur_->value_; } \
  100. inline int TableIterator(Table)::more() { return entry_ <= last_; }
  101.  
  102. /*
  103.  * Predefined hash functions
  104.  */
  105.  
  106. inline unsigned long key_to_hash(long k) { return (unsigned long)k; }
  107. //inline unsigned long key_to_hash(const void* k) { return (unsigned long)k; }
  108. //inline unsigned long key_to_hash(const char* k) 
  109. //{ return (unsigned long)hash(k); }
  110. inline unsigned long key_to_hash(const rcString& k) 
  111. { return (unsigned long)hash((const char*) k); }
  112.  
  113. /*
  114.  * Table implementation
  115.  */
  116.  
  117. #define implementTable(Table,Key,Value) \
  118. Table::Table(int n) { \
  119.     for (size_ = 32; size_ < n; size_ <<= 1); \
  120.     first_ = new TableEntry(Table)*[size_]; \
  121.     --size_; \
  122.     last_ = &first_[size_]; \
  123.     for (register TableEntry(Table)** e = first_; e <= last_; e++) { \
  124.     *e = NULL; \
  125.     } \
  126. } \
  127. \
  128. Table::~Table() { \
  129.     delete first_; \
  130. } \
  131. \
  132. inline TableEntry(Table)*& Table::probe(const Key &i) { \
  133.     return first_[key_to_hash(i) & size_]; \
  134. } \
  135. \
  136. int Table::insert(const Key& k, const Value &v) { \
  137.     if (find(k)) return 0; \
  138. \
  139.     register TableEntry(Table)* e = new TableEntry(Table); \
  140.     e->key_ = k; \
  141.     e->value_ = v; \
  142.     register TableEntry(Table)** a = &probe(k); \
  143.     e->chain_ = *a; \
  144.     *a = e; \
  145.     return 1;\
  146. } \
  147. \
  148. int Table::lookup(const Key &k, Value &v) { \
  149.     for (register TableEntry(Table)* e = probe(k); e != NULL; e = e->chain_) { \
  150.     if (e->key_ == k) { \
  151.         v = e->value_; \
  152.         return 1; \
  153.     } \
  154.     } \
  155.     return 0; \
  156. } \
  157. \
  158. int Table::find(const Key &k) { \
  159.     for (register TableEntry(Table)* e = probe(k); e != NULL; e = e->chain_) { \
  160.     if (e->key_ == k) { \
  161.         return 1; \
  162.     } \
  163.     } \
  164.     return 0; \
  165. } \
  166. \
  167. int Table::find_and_replace(const Key& k, const Value& v) { \
  168.     for (register TableEntry(Table)* e = probe(k); e != NULL; e = e->chain_) { \
  169.     if (e->key_ == k) { \
  170.       e->value_ = v; \
  171.       return 1; \
  172.     } \
  173.     } \
  174.     return 0; \
  175. } \
  176. \
  177. int Table::find_and_remove(const Key& k, Value& v) { \
  178.     TableEntry(Table)** a = &probe(k); \
  179.     register TableEntry(Table)* e = *a; \
  180.     if (e != NULL) { \
  181.     if (e->key_ == k) { \
  182.         v = e->value_; \
  183.         *a = e->chain_; \
  184.         delete e; \
  185.         return 1; \
  186.     } else { \
  187.         register TableEntry(Table)* prev; \
  188.         do { \
  189.         prev = e; \
  190.         e = e->chain_; \
  191.         } while (e != NULL && e->key_ != k); \
  192.         if (e != NULL) { \
  193.         v = e->value_; \
  194.         prev->chain_ = e->chain_; \
  195.         delete e; \
  196.         return 1; \
  197.         } \
  198.     } \
  199.     } \
  200.     return 0; \
  201. } \
  202. \
  203. void Table::remove(const Key &k) { \
  204.     TableEntry(Table)** a = &probe(k); \
  205.     register TableEntry(Table)* e = *a; \
  206.     if (e != NULL) { \
  207.     if (e->key_ == k) { \
  208.         *a = e->chain_; \
  209.         delete e; \
  210.     } else { \
  211.         register TableEntry(Table)* prev; \
  212.         do { \
  213.         prev = e; \
  214.         e = e->chain_; \
  215.         } while (e != NULL && e->key_ != k); \
  216.         if (e != NULL) { \
  217.         prev->chain_ = e->chain_; \
  218.         delete e; \
  219.         } \
  220.     } \
  221.     } \
  222. } \
  223. \
  224. void Table::remove_all() \
  225. { \
  226.   TableIterator(Table) ti(*this); \
  227.   while (ti.more()) \
  228.   { \
  229.     remove(ti.cur_key()); \
  230.     ti.next(); \
  231.   } \
  232. } \
  233. \
  234. TableIterator(Table)::TableIterator(Table)(const Table& t) { \
  235.     last_ = t.last_; \
  236.     for (entry_ = t.first_; entry_ <= last_; entry_++) { \
  237.     cur_ = *entry_; \
  238.     if (cur_ != NULL) { \
  239.         break; \
  240.     } \
  241.     } \
  242. } \
  243. \
  244. int TableIterator(Table)::next() { \
  245.     cur_ = cur_->chain_; \
  246.     if (cur_ != NULL) { \
  247.     return 1; \
  248.     } \
  249.     for (++entry_; entry_ <= last_; entry_++) { \
  250.     cur_ = *entry_; \
  251.     if (cur_ != NULL) { \
  252.         return 1; \
  253.     } \
  254.     } \
  255.     return 0; \
  256. }
  257.  
  258. #endif // Table_H
  259.  
  260.  
  261.  
  262.  
  263.