Annotation of fam/fam/SmallTable.h, Revision 1.1.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