1 /******************************************************************************** 2 * * 3 * H a s h T a b l e C l a s s * 4 * * 5 ********************************************************************************* 6 * Copyright (C) 2003,2021 by Jeroen van der Zijp. All Rights Reserved. * 7 ********************************************************************************* 8 * This library is free software; you can redistribute it and/or modify * 9 * it under the terms of the GNU Lesser General Public License as published by * 10 * the Free Software Foundation; either version 3 of the License, or * 11 * (at your option) any later version. * 12 * * 13 * This library is distributed in the hope that it will be useful, * 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 16 * GNU Lesser General Public License for more details. * 17 * * 18 * You should have received a copy of the GNU Lesser General Public License * 19 * along with this program. If not, see <http://www.gnu.org/licenses/> * 20 ********************************************************************************/ 21 #ifndef FXHASH_H 22 #define FXHASH_H 23 24 namespace FX { 25 26 27 /** 28 * A hash table for mapping pointers to pointers. 29 * Two special key values are disallowed: NULL and the pointer value (-1L); 30 * NULL is used to designate an unoccupied slot, while (-1L) is used to designate 31 * a formerly occupied slot. 32 */ 33 class FXAPI FXHash { 34 protected: 35 struct Entry { 36 FXptr key; 37 FXptr data; 38 }; 39 protected: 40 Entry *table; 41 protected: 42 43 // Change size of the table & hash existing contents 44 FXbool no(FXival n); 45 46 // Change number of used entries used(FXival u)47 void used(FXival u){ ((FXival*)table)[-2]=u; } 48 49 // Change number of free entries free(FXival f)50 void free(FXival f){ ((FXival*)table)[-3]=f; } 51 52 // Resize the table to the given size, keeping contents 53 FXbool resize(FXival n); 54 public: 55 56 /** 57 * Construct empty hash table. 58 */ 59 FXHash(); 60 61 /** 62 * Construct from another table. 63 */ 64 FXHash(const FXHash& other); 65 66 /** 67 * Return the total number of slots in the table. 68 */ no()69 FXival no() const { return ((FXival*)table)[-1]; } 70 71 /** 72 * Return number of used slots in the table. 73 */ used()74 FXival used() const { return ((FXival*)table)[-2]; } 75 76 /** 77 * Return number of free slots in the table. 78 */ free()79 FXival free() const { return ((FXival*)table)[-3]; } 80 81 /** 82 * See if hash table is empty 83 */ empty()84 FXbool empty() const { return ((FXival*)table)[-1]<=1; } 85 86 /** 87 * Assign from another table. 88 */ 89 FXHash &operator=(const FXHash& other); 90 91 /** 92 * Adopt table from another; the other table becomes empty. 93 */ 94 FXHash& adopt(FXHash& other); 95 96 /** 97 * Find position of given key, returning -1 if not found. 98 */ 99 FXival find(FXptr ky) const; 100 101 /** 102 * Return reference to slot assocated with given key. 103 */ 104 FXptr& at(FXptr ky); 105 106 /** 107 * Return constant reference to slot assocated with given key. 108 */ 109 const FXptr& at(FXptr ky) const; 110 111 /** 112 * Return reference to slot assocated with given key. 113 */ 114 FXptr& operator[](FXptr ky){ return at(ky); } 115 116 /** 117 * Return constant reference to slot assocated with given key. 118 */ 119 const FXptr& operator[](FXptr ky) const { return at(ky); } 120 121 /** 122 * Replace key in table, overwriting the old value if the 123 * given key already exists. Returns the old value of the key. 124 */ 125 FXptr insert(FXptr ky,FXptr ptr=NULL){ return swap(ptr,at(ky)); } 126 127 /** 128 * Remove key from the table. Returns the old value of the key. 129 */ 130 FXptr remove(FXptr ky); 131 132 /** 133 * Erase entry from table at pos, returning old value. 134 */ 135 FXptr erase(FXival pos); 136 137 /** 138 * Return true if slot is not occupied by a key. 139 */ empty(FXival pos)140 FXbool empty(FXival pos) const { return (table[pos].key==(FXptr)0L)||(table[pos].key==(FXptr)-1L); } 141 142 /** 143 * Return key at position pos. 144 */ key(FXival pos)145 FXptr key(FXival pos) const { return table[pos].key; } 146 147 /** 148 * Return reference to data pointer at position pos. 149 */ data(FXival pos)150 FXptr& data(FXival pos){ return table[pos].data; } 151 152 /** 153 * Return constant reference data pointer at position pos. 154 */ data(FXival pos)155 const FXptr& data(FXival pos) const { return table[pos].data; } 156 157 /** 158 * Clear hash table. 159 */ 160 void clear(); 161 162 /// Destructor 163 ~FXHash(); 164 }; 165 166 } 167 168 #endif 169