Annotation of fam/fam/SmallTable.h, Revision 1.1
1.1 ! trev 1: // Copyright (C) 1999 Silicon Graphics, Inc. All Rights Reserved.
! 2: //
! 3: // This program is free software; you can redistribute it and/or modify it
! 4: // under the terms of version 2 of the GNU General Public License as
! 5: // published by the Free Software Foundation.
! 6: //
! 7: // This program is distributed in the hope that it would be useful, but
! 8: // WITHOUT ANY WARRANTY; without even the implied warranty of
! 9: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Further, any
! 10: // license provided herein, whether implied or otherwise, is limited to
! 11: // this program in accordance with the express provisions of the GNU
! 12: // General Public License. Patent licenses, if any, provided herein do not
! 13: // apply to combinations of this program with other product or programs, or
! 14: // any other product whatsoever. This program is distributed without any
! 15: // warranty that the program is delivered free of the rightful claim of any
! 16: // third person by way of infringement or the like. See the GNU General
! 17: // Public License for more details.
! 18: //
! 19: // You should have received a copy of the GNU General Public License along
! 20: // with this program; if not, write the Free Software Foundation, Inc., 59
! 21: // Temple Place - Suite 330, Boston MA 02111-1307, USA.
! 22:
! 23: #ifndef SmallTable_included
! 24: #define SmallTable_included
! 25:
! 26: #include <assert.h>
! 27:
! 28: // A SmallTable holds key-value mappings. Its implementation is
! 29: // cheap and dirty, so it should not be used for tables with lots of
! 30: // entries. Lookups are faster than insertions/removals.
! 31: //
! 32: // class TKey and Tvalue must define < and > operators, and must
! 33: // be able to be assigned a value of 0 and be compared
! 34: // with 0.
! 35: //
! 36: // Operations:
! 37: // insert() puts a new entry in table.
! 38: // remove() removes an entry.
! 39: // find() returns the value for a key.
! 40: // size() returns number of entries.
! 41: // first() returns the first key
! 42:
! 43:
! 44: template <class Tkey, class Tvalue> class SmallTable {
! 45:
! 46: public:
! 47:
! 48: SmallTable() : n(0), nalloc(0), table(0) { }
! 49: virtual ~SmallTable();
! 50:
! 51: void insert(const Tkey&, const Tvalue&);
! 52: void remove(const Tkey&);
! 53: void removeAll();
! 54: inline Tvalue find(const Tkey& k) const;
! 55: Tkey first() const { return n ? table[0].key : 0; }
! 56: unsigned size() const { return n; }
! 57:
! 58: private:
! 59:
! 60: struct Closure {
! 61: const enum Presence { PRESENT, ABSENT } presence;
! 62: const unsigned index;
! 63: Closure(Presence p, unsigned i) : presence(p), index(i) { }
! 64: };
! 65:
! 66: struct Pair {
! 67: Tkey key;
! 68: Tvalue value;
! 69: };
! 70:
! 71: unsigned n, nalloc;
! 72: Pair *table;
! 73:
! 74: virtual Closure position(const Tkey&) const;
! 75:
! 76: SmallTable(const SmallTable&); // Do not copy
! 77: SmallTable & operator = (const SmallTable&); // or assign.
! 78:
! 79: };
! 80:
! 81:
! 82: //
! 83: // Template member implementations
! 84: //
! 85:
! 86: template <class Tkey, class Tvalue>
! 87: inline Tvalue
! 88: SmallTable<Tkey, Tvalue>::find(const Tkey& k) const
! 89: {
! 90: Closure c = position(k);
! 91: return c.presence == Closure::PRESENT ? table[c.index].value : 0;
! 92: }
! 93:
! 94: template <class Tkey, class Tvalue>
! 95: SmallTable<Tkey, Tvalue>::~SmallTable()
! 96: {
! 97: delete [] table;
! 98: }
! 99:
! 100: template <class Tkey, class Tvalue>
! 101: SmallTable<Tkey, Tvalue>::Closure
! 102: SmallTable<Tkey, Tvalue>::position(const Tkey& key) const
! 103: {
! 104: unsigned l = 0, r = n;
! 105: while (l < r)
! 106: {
! 107: unsigned mid = (l + r) / 2;
! 108: if (key < table[mid].key)
! 109: r = mid;
! 110: else if (key > table[mid].key)
! 111: l = mid + 1;
! 112: else // (key == table[mid].key)
! 113: return Closure(Closure::PRESENT, mid);
! 114: }
! 115: return Closure(Closure::ABSENT, l);
! 116: }
! 117:
! 118: template <class Tkey, class Tvalue>
! 119: void
! 120: SmallTable<Tkey, Tvalue>::insert(const Tkey& key, const Tvalue& value)
! 121: {
! 122: Closure c = position(key);
! 123:
! 124: if (c.presence == Closure::PRESENT)
! 125: { table[c.index].value = value;
! 126: return;
! 127: }
! 128:
! 129: if (n >= nalloc)
! 130: {
! 131: // Grow the table.
! 132:
! 133: nalloc = 3 * n / 2 + 10;
! 134: Pair *nt = new Pair[nalloc];
! 135: unsigned i;
! 136: for (i = 0; i < c.index; i++)
! 137: nt[i] = table[i];
! 138: for ( ; i < n; i++)
! 139: nt[i + 1] = table[i];
! 140: delete [] table;
! 141: table = nt;
! 142: }
! 143: else
! 144: {
! 145: // Shift following entries right.
! 146:
! 147: for (unsigned i = n; i > c.index; --i)
! 148: table[i] = table[i - 1];
! 149: }
! 150: table[c.index].key = key;
! 151: table[c.index].value = value;
! 152: n++;
! 153: }
! 154:
! 155: template <class Tkey, class Tvalue>
! 156: void
! 157: SmallTable<Tkey, Tvalue>::remove(const Tkey& key)
! 158: {
! 159: Closure c = position(key);
! 160: assert(c.presence == Closure::PRESENT);
! 161:
! 162: // Shift following entries left.
! 163:
! 164: for (unsigned i = c.index + 1; i < n; i++)
! 165: table[i - 1] = table[i];
! 166: --n;
! 167:
! 168: // Shrink the table.
! 169:
! 170: if (2 * n < nalloc && n < nalloc - 10)
! 171: {
! 172: nalloc = n;
! 173: Pair *nt = new Pair[nalloc];
! 174: for (unsigned i = 0; i < n; i++)
! 175: nt[i] = table[i];
! 176: delete [] table;
! 177: table = nt;
! 178: }
! 179: }
! 180:
! 181: template <class Tkey, class Tvalue>
! 182: void
! 183: SmallTable<Tkey, Tvalue>::removeAll()
! 184: {
! 185: n = 0;
! 186: nalloc = 0;
! 187: if (table != NULL) delete [] table;
! 188: table = NULL;
! 189: }
! 190:
! 191: #endif /* !SmallTable_included */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to SmallTable.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / fam / fam