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