00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef __UT_HashTable_h__
00019 #define __UT_HashTable_h__
00020
00021 #include "UT_API.h"
00022 #include <stdio.h>
00023 #include <iostream.h>
00024 #include <SYS/SYS_Types.h>
00025 #include "UT_ThingList.h"
00026 #include "UT_Hash.h"
00027
00028 class UT_API UT_HashTable {
00029 public:
00030 explicit UT_HashTable();
00031 virtual ~UT_HashTable();
00032
00033
00034
00035
00036
00037 void useOrderedLists(bool ordered);
00038
00039 void addSymbol(const UT_Hash& symbol, const UT_Thing &data);
00040 int findSymbol(const UT_Hash& symbol, UT_Thing *datap,
00041 const UT_Hash **hash_symbol = 0) const;
00042
00043 int contains(const UT_Hash &symbol) const
00044 { UT_Thing value; return findSymbol(symbol, &value); }
00045
00046 template <typename T>
00047 T *findPointer(const UT_Hash &symbol) const
00048 {
00049 UT_Thing thing;
00050 if (!findSymbol(symbol, &thing))
00051 return NULL;
00052 return thing.template asPointer<T>();
00053 }
00054
00055 int deleteSymbol(const UT_Hash& symbol);
00056 int moveSymbol(const UT_Hash &oldsymbol,
00057 const UT_Hash &newsymbol);
00058 void clear();
00059
00060 unsigned entries() const { return myNbrEntries; }
00061 bool empty() const { return !myNbrEntries; }
00062
00063
00064 UT_Thing &operator[](const UT_Hash& symbol);
00065
00066
00067
00068 void reserveTableSize(int size);
00069
00070
00071
00072
00073 float getMaxLoadFactor() const { return myMaxLoadFactor; }
00074 void setMaxLoadFactor(float max_load_factor);
00075 float getMinLoadFactor() const { return myMinLoadFactor; }
00076 void setMinLoadFactor(float min_load_factor);
00077
00078
00079 void mergeTable(const UT_HashTable &table);
00080
00081
00082
00083
00084 const UT_Hash *getHashReference(const UT_Hash &hash);
00085
00086 void outputStats(FILE *output) const;
00087 void outputStats(ostream &os) const;
00088 void dumpTable(FILE *output) const;
00089
00090 int64 getMemUsage(bool only_this) const;
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102 int traverseConst(
00103 int (*function)(UT_Thing &, const UT_Hash&, void *),
00104 void *data) const;
00105 int traverse(int (*function)(UT_Thing &, const UT_Hash&, void *),
00106 void *data);
00107
00108 class UT_API traverser
00109 {
00110 public:
00111 traverser()
00112 : myCurrList(0), myEndList(0)
00113 { }
00114 traverser(const traverser &src)
00115 { *this = src; }
00116 ~traverser()
00117 { }
00118
00119 UT_Thing &thing() const
00120 { return myCurrEntry.thing(); }
00121 UT_Hash *hash() const
00122 { return myCurrEntry.hash(); }
00123
00124 int operator==(const traverser &cmp) const
00125 {
00126 return ((!myCurrList && !cmp.myCurrList) ||
00127 ((myCurrList == cmp.myCurrList) &&
00128 (myCurrEntry == cmp.myCurrEntry)));
00129 }
00130 int operator!=(const traverser &cmp) const
00131 { return !(*this == cmp); }
00132
00133 bool atEnd() const
00134 {
00135 return !myCurrList;
00136 }
00137
00138 traverser &operator++()
00139 {
00140 advance();
00141 return *this;
00142 }
00143 traverser &operator++(int)
00144 {
00145 advance();
00146 return *this;
00147 }
00148
00149 traverser &operator=(const traverser &src)
00150 {
00151 myCurrList = src.myCurrList;
00152 myEndList = src.myEndList;
00153 myCurrEntry = src.myCurrEntry;
00154 return *this;
00155 }
00156
00157 void advance()
00158 {
00159 if( ++myCurrEntry == myCurrList->end() )
00160 {
00161 ++myCurrList;
00162 advanceToNextList();
00163 }
00164 }
00165
00166 private:
00167 traverser(const UT_ThingList *list, const UT_ThingList *endlist)
00168 : myCurrList(list), myEndList(endlist)
00169 { advanceToNextList(); }
00170
00171 void advanceToNextList()
00172 {
00173 while( myCurrList != myEndList &&
00174 myCurrList->begin() == myCurrList->end() )
00175 ++myCurrList;
00176 if( myCurrList == myEndList )
00177 myCurrList = 0;
00178 else
00179 myCurrEntry = myCurrList->begin();
00180 }
00181
00182 const UT_ThingList *myCurrList;
00183 const UT_ThingList *myEndList;
00184 UT_ThingList::traverser myCurrEntry;
00185
00186 friend class UT_HashTable;
00187 };
00188
00189 traverser begin() const
00190 {
00191 if( myTable )
00192 return traverser(myTable, myTable + mySize);
00193 return traverser();
00194 }
00195 traverser end() const
00196 { return traverser(); }
00197
00198 private:
00199 enum UT_AdjustType { UT_ADJUST_INCREASE, UT_ADJUST_DECREASE };
00200 void adjustTableSize(UT_AdjustType adjust_type);
00201 void allocateTableOfNewSize(int size);
00202
00203
00204 UT_ThingList *myTable;
00205 int mySize;
00206 unsigned int myNbrEntries;
00207 fpreal myMaxLoadFactor;
00208 fpreal myMinLoadFactor;
00209 bool myUseOrdered;
00210 bool myIsTraversing;
00211 };
00212
00213 #endif