source: NonGTP/Xerces/xercesc/util/RefHashTableOf.hpp @ 188

Revision 188, 14.6 KB checked in by mattausch, 19 years ago (diff)

added xercesc to support

Line 
1/*
2 * The Apache Software License, Version 1.1
3 *
4 * Copyright (c) 1999-2003 The Apache Software Foundation.  All rights
5 * reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in
16 *    the documentation and/or other materials provided with the
17 *    distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 *    if any, must include the following acknowledgment:
21 *       "This product includes software developed by the
22 *        Apache Software Foundation (http://www.apache.org/)."
23 *    Alternately, this acknowledgment may appear in the software itself,
24 *    if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "Xerces" and "Apache Software Foundation" must
27 *    not be used to endorse or promote products derived from this
28 *    software without prior written permission. For written
29 *    permission, please contact apache\@apache.org.
30 *
31 * 5. Products derived from this software may not be called "Apache",
32 *    nor may "Apache" appear in their name, without prior written
33 *    permission of the Apache Software Foundation.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46 * SUCH DAMAGE.
47 * ====================================================================
48 *
49 * This software consists of voluntary contributions made by many
50 * individuals on behalf of the Apache Software Foundation, and was
51 * originally based on software copyright (c) 1999, International
52 * Business Machines, Inc., http://www.ibm.com .  For more information
53 * on the Apache Software Foundation, please see
54 * <http://www.apache.org/>.
55 */
56
57/*
58 * $Log: RefHashTableOf.hpp,v $
59 * Revision 1.13  2004/01/29 11:48:46  cargilld
60 * Code cleanup changes to get rid of various compiler diagnostic messages.
61 *
62 * Revision 1.12  2003/12/17 00:18:35  cargilld
63 * Update to memory management so that the static memory manager (one used to call Initialize) is only for static data.
64 *
65 * Revision 1.11  2003/10/20 11:45:06  gareth
66 * Made enumerators inherit from XMemory.
67 *
68 * Revision 1.10  2003/05/18 14:02:05  knoaman
69 * Memory manager implementation: pass per instance manager.
70 *
71 * Revision 1.9  2003/05/16 21:36:59  knoaman
72 * Memory manager implementation: Modify constructors to pass in the memory manager.
73 *
74 * Revision 1.8  2003/05/15 19:04:35  knoaman
75 * Partial implementation of the configurable memory manager.
76 *
77 * Revision 1.7  2003/05/15 10:37:08  gareth
78 * Optimization. We now resize the hash when appropriate. Patch by Nathan Codding.
79 *
80 * Revision 1.6  2002/11/04 15:22:04  tng
81 * C++ Namespace Support.
82 *
83 * Revision 1.5  2002/08/21 17:45:00  tng
84 * [Bug 7087] compiler warnings when using gcc.
85 *
86 * Revision 1.4  2002/07/11 18:49:53  knoaman
87 * Add setAdoptElements method.
88 * Rename removeBucketElemSafe to orphanKey.
89 *
90 * Revision 1.3  2002/07/04 15:24:57  tng
91 * DOM L3: add transferElement and removeBucketElemSafe for use in DOMDocument::renameNode.
92 *
93 * Revision 1.2  2002/06/12 17:14:03  tng
94 * Add function cleanup, reinitialize and nextElementKey for ease of use.
95 *
96 * Revision 1.1.1.1  2002/02/01 22:22:12  peiyongz
97 * sane_include
98 *
99 * Revision 1.9  2001/06/04 13:45:04  tng
100 * The "hash" argument clashes with STL hash.  Fixed by Pei Yong Zhang.
101 *
102 * Revision 1.8  2000/07/07 22:16:51  jpolast
103 * remove old put(value) function.  use put(key,value) instead.
104 *
105 * Revision 1.7  2000/06/29 18:27:09  jpolast
106 * bug fix for passing hasher class references to constructor
107 *
108 * Revision 1.6  2000/06/27 22:11:12  jpolast
109 * added more general functionality to hashtables.
110 * able to specify which hasher to use.
111 * default: HashXMLCh [hashes XMLCh* strings]
112 *
113 * future todo: make hasher class references static so only
114 * one instance of a hasher is ever created.
115 *
116 * Revision 1.5  2000/03/02 19:54:44  roddey
117 * This checkin includes many changes done while waiting for the
118 * 1.1.0 code to be finished. I can't list them all here, but a list is
119 * available elsewhere.
120 *
121 * Revision 1.4  2000/02/24 20:05:25  abagchi
122 * Swat for removing Log from API docs
123 *
124 * Revision 1.3  2000/02/06 07:48:03  rahulj
125 * Year 2K copyright swat.
126 *
127 * Revision 1.2  1999/12/18 00:18:10  roddey
128 * More changes to support the new, completely orthagonal support for
129 * intrinsic encodings.
130 *
131 * Revision 1.1.1.1  1999/11/09 01:05:01  twl
132 * Initial checkin
133 *
134 * Revision 1.2  1999/11/08 20:45:12  rahul
135 * Swat for adding in Product name and CVS comment log variable.
136 *
137 */
138
139
140#if !defined(REFHASHTABLEOF_HPP)
141#define REFHASHTABLEOF_HPP
142
143
144#include <xercesc/util/HashBase.hpp>
145#include <xercesc/util/IllegalArgumentException.hpp>
146#include <xercesc/util/NoSuchElementException.hpp>
147#include <xercesc/util/RuntimeException.hpp>
148#include <xercesc/util/XMLString.hpp>
149#include <xercesc/util/HashXMLCh.hpp>
150#include <xercesc/util/PlatformUtils.hpp>
151#include <xercesc/framework/MemoryManager.hpp>
152
153XERCES_CPP_NAMESPACE_BEGIN
154
155//
156//  Forward declare the enumerator so he can be our friend. Can you say
157//  friend? Sure...
158//
159template <class TVal> class RefHashTableOfEnumerator;
160template <class TVal> struct RefHashTableBucketElem;
161
162
163//
164//  This should really be a nested class, but some of the compilers we
165//  have to support cannot deal with that!
166//
167template <class TVal> struct RefHashTableBucketElem : public XMemory
168{
169    RefHashTableBucketElem(void* key, TVal* const value, RefHashTableBucketElem<TVal>* next)
170                : fData(value), fNext(next), fKey(key)
171        {
172        }
173
174    RefHashTableBucketElem(){};
175
176    TVal*                           fData;
177    RefHashTableBucketElem<TVal>*   fNext;
178        void*                                                   fKey;
179
180private:
181    // -----------------------------------------------------------------------
182    //  Unimplemented constructors and operators
183    // -----------------------------------------------------------------------
184    RefHashTableBucketElem(const RefHashTableBucketElem<TVal>&);
185    RefHashTableBucketElem<TVal>& operator=(const RefHashTableBucketElem<TVal>&);
186};
187
188
189template <class TVal> class RefHashTableOf : public XMemory
190{
191public:
192    // -----------------------------------------------------------------------
193    //  Constructors and Destructor
194    // -----------------------------------------------------------------------
195        // backwards compatability - default hasher is HashXMLCh
196    RefHashTableOf
197    (
198        const unsigned int modulus
199        , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager
200    );
201        // backwards compatability - default hasher is HashXMLCh
202    RefHashTableOf
203    (
204        const unsigned int modulus
205        , const bool adoptElems
206        , MemoryManager* const manager =  XMLPlatformUtils::fgMemoryManager
207    );
208        // if a hash function is passed in, it will be deleted when the hashtable is deleted.
209        // use a new instance of the hasher class for each hashtable, otherwise one hashtable
210        // may delete the hasher of a different hashtable if both use the same hasher.
211    RefHashTableOf
212    (
213        const unsigned int modulus
214        , const bool adoptElems
215        , HashBase* hashBase
216        , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager
217    );
218    ~RefHashTableOf();
219
220
221    // -----------------------------------------------------------------------
222    //  Element management
223    // -----------------------------------------------------------------------
224    bool isEmpty() const;
225    bool containsKey(const void* const key) const;
226    void removeKey(const void* const key);
227    void removeAll();
228    void cleanup();
229    void reinitialize(HashBase* hashBase);
230    void transferElement(const void* const key1, void* key2);
231    TVal* orphanKey(const void* const key);
232
233    // -----------------------------------------------------------------------
234    //  Getters
235    // -----------------------------------------------------------------------
236    TVal* get(const void* const key);
237    const TVal* get(const void* const key) const;
238    MemoryManager* getMemoryManager() const;
239
240    // -----------------------------------------------------------------------
241    //  Setters
242    // -----------------------------------------------------------------------
243    void setAdoptElements(const bool aValue);
244
245
246    // -----------------------------------------------------------------------
247    //  Putters
248    // -----------------------------------------------------------------------
249        void put(void* key, TVal* const valueToAdopt);
250
251
252private :
253    // -----------------------------------------------------------------------
254    //  Declare our friends
255    // -----------------------------------------------------------------------
256    friend class RefHashTableOfEnumerator<TVal>;
257
258private:
259    // -----------------------------------------------------------------------
260    //  Unimplemented constructors and operators
261    // -----------------------------------------------------------------------
262    RefHashTableOf(const RefHashTableOf<TVal>&);
263    RefHashTableOf<TVal>& operator=(const RefHashTableOf<TVal>&);
264
265    // -----------------------------------------------------------------------
266    //  Private methods
267    // -----------------------------------------------------------------------
268    RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal);
269    const RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal) const;
270    void removeBucketElem(const void* const key, unsigned int& hashVal);
271    void initialize(const unsigned int modulus);
272    void rehash();
273
274
275    // -----------------------------------------------------------------------
276    //  Data members
277    //
278    //  fAdoptedElems
279    //      Indicates whether the values added are adopted or just referenced.
280    //      If adopted, then they are deleted when they are removed from the
281    //      hash table.
282    //
283    //  fBucketList
284    //      This is the array that contains the heads of all of the list
285    //      buckets, one for each possible hash value.
286    //
287    //  fHashModulus
288    //      The modulus used for this hash table, to hash the keys. This is
289    //      also the number of elements in the bucket list.
290        //
291        //  fHash
292        //      The hasher for the key data type.
293    // -----------------------------------------------------------------------
294    MemoryManager*                 fMemoryManager;
295    bool                           fAdoptedElems;
296    RefHashTableBucketElem<TVal>** fBucketList;
297    unsigned int                   fHashModulus;
298    unsigned int                   fInitialModulus;
299    unsigned int                   fCount;
300    HashBase*                      fHash;
301};
302
303
304
305//
306//  An enumerator for a value array. It derives from the basic enumerator
307//  class, so that value vectors can be generically enumerated.
308//
309template <class TVal> class RefHashTableOfEnumerator : public XMLEnumerator<TVal>, public XMemory
310{
311public :
312    // -----------------------------------------------------------------------
313    //  Constructors and Destructor
314    // -----------------------------------------------------------------------
315    RefHashTableOfEnumerator(RefHashTableOf<TVal>* const toEnum
316        , const bool adopt = false
317        , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
318    virtual ~RefHashTableOfEnumerator();
319
320    RefHashTableOfEnumerator(const RefHashTableOfEnumerator<TVal>&);
321    // -----------------------------------------------------------------------
322    //  Enum interface
323    // -----------------------------------------------------------------------
324    bool hasMoreElements() const;
325    TVal& nextElement();
326    void Reset();
327
328    // -----------------------------------------------------------------------
329    //  New interface specific for key used in RefHashable
330    // -----------------------------------------------------------------------
331    void* nextElementKey();
332
333private :
334    // -----------------------------------------------------------------------
335    //  Unimplemented constructors and operators
336    // -----------------------------------------------------------------------
337    RefHashTableOfEnumerator<TVal>& operator=(const RefHashTableOfEnumerator<TVal>&);
338
339    // -----------------------------------------------------------------------
340    //  Private methods
341    // -----------------------------------------------------------------------
342    void findNext();
343
344
345    // -----------------------------------------------------------------------
346    //  Data Members
347    //
348    //  fAdopted
349    //      Indicates whether we have adopted the passed vector. If so then
350    //      we delete the vector when we are destroyed.
351    //
352    //  fCurElem
353    //      This is the current bucket bucket element that we are on.
354    //
355    //  fCurHash
356    //      The is the current hash buck that we are working on. Once we hit
357    //      the end of the bucket that fCurElem is in, then we have to start
358    //      working this one up to the next non-empty bucket.
359    //
360    //  fToEnum
361    //      The value array being enumerated.
362    // -----------------------------------------------------------------------
363    bool                                  fAdopted;
364    RefHashTableBucketElem<TVal>*         fCurElem;
365    unsigned int                          fCurHash;
366    RefHashTableOf<TVal>*                 fToEnum;
367    MemoryManager* const                  fMemoryManager;
368};
369
370XERCES_CPP_NAMESPACE_END
371
372#if !defined(XERCES_TMPLSINC)
373#include <xercesc/util/RefHashTableOf.c>
374#endif
375
376#endif
377
Note: See TracBrowser for help on using the repository browser.