Annotation of fam/fam/StringTable.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 StringTable_included
24: #define StringTable_included
25:
26: #include <assert.h>
27: #include <string.h>
28:
29: // A StringTable maps C strings onto values. It is a cheap O(n)
30: // implementation, suitable only for small tables that are
31: // infrequently searched.
32: // class Tv must be able to be assigned a value of 0 and be compared
33: // with 0.
34:
35: template <class Tv> class StringTable {
36:
37: typedef const char *Tk;
38:
39: public:
40:
41: StringTable() : n(0), nalloc(0), table(0)
42: { }
43: virtual ~StringTable();
44:
45: // Makes a copy of the Table. Copys the keys, but not the values.
46: StringTable& operator = (const StringTable&);
47:
48: inline Tv find(const Tk) const;
49: unsigned size() const { return n; }
50: Tk key(unsigned i) const { return i < n ? table[i].key : 0; }
51: Tv value(unsigned i) const { return i < n ? table[i].value : 0; }
52:
53: void insert(const Tk, const Tv&);
54: void remove(const Tk);
55:
56: private:
57:
58: struct Pair {
59: char *key;
60: Tv value;
61: };
62:
63: unsigned n, nalloc;
64: Pair *table;
65:
66: virtual signed int position(const Tk) const;
67:
68: StringTable(const StringTable&); // Do not copy.
69:
70: };
71:
72:
73: //
74: // Template method implementations
75: //
76:
77: template <class Tv>
78: inline Tv
79: StringTable<Tv>::find(const Tk k) const
80: {
81: signed int index = position(k);
82: return index >= 0 ? table[index].value : 0;
83: }
84:
85: template <class Tv>
86: StringTable<Tv>::~StringTable()
87: {
88: {
89: for (unsigned i = 0; i < n; i++)
90: delete [] table[i].key;
91: }
92: delete[] table;
93:
94: table = NULL;
95: nalloc = n = 0;
96: }
97:
98: template <class Tv>
99: StringTable<Tv>&
100: StringTable<Tv>::operator = (const StringTable& that)
101: {
102: if (this != &that)
103: {
104: unsigned i;
105: for (i = 0; i < n; i++)
106: delete [] table[i].key;
107: delete[] table;
108: nalloc = n = that.n;
109: table = new Pair[nalloc];
110: for (i = 0; i < n; i++)
111: { const char *key = that.table[i].key;
112: table[i].key = strcpy(new char[strlen(key) + 1], key);
113: table[i].value = that.table[i].value;
114: }
115: }
116: return *this;
117: }
118:
119: template <class Tv>
120: signed int
121: StringTable<Tv>::position(const Tk key) const
122: {
123: for (unsigned i = 0; i < n; i++)
124: if (!strcmp(key, table[i].key))
125: return i;
126: return -1; // Not found.
127: }
128:
129: template <class Tv>
130: void
131: StringTable<Tv>::insert(const Tk key, const Tv& value)
132: {
133: signed int index = position(key);
134: if (index >= 0)
135: { table[index].value = value;
136: return;
137: }
138:
139: if (n >= nalloc)
140: {
141: // Grow the table.
142:
143: nalloc = 3 * n / 2 + 10;
144: Pair *nt = new Pair[nalloc];
145: for (unsigned i = 0; i < n; i++)
146: nt[i] = table[i];
147: delete [] table;
148: table = nt;
149: assert(n < nalloc);
150: }
151: table[n].key = strcpy(new char[strlen(key) + 1], key);
152: table[n].value = value;
153: n++;
154: }
155:
156: template <class Tv>
157: void
158: StringTable<Tv>::remove(const Tk key)
159: {
160: signed int index = position(key);
161: assert(index >= 0 && index < n);
162:
163: // Delete the matching key.
164:
165: delete [] table[index].key;
166: table[index] = table[--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: #endif /* !StringTable_included */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to StringTable.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / fam / fam