Annotation of fam/fam/StringTable.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 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