0024252: GCC warnings on breakage of strict-aliasing rules
[occt.git] / src / NCollection / NCollection_DataMap.hxx
1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and / or modify it
8 // under the terms of the GNU Lesser General Public version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_DataMap_HeaderFile
17 #define NCollection_DataMap_HeaderFile
18
19 #include <NCollection_BaseCollection.hxx>
20 #include <NCollection_BaseMap.hxx>
21 #include <NCollection_TListNode.hxx>
22
23 #include <NCollection_DefaultHasher.hxx>
24
25 #include <Standard_TypeMismatch.hxx>
26 #include <Standard_NoSuchObject.hxx>
27
28 /**
29 * Purpose:     The DataMap is a Map to store keys with associated
30 *              Items. See Map  from NCollection for  a discussion
31 *              about the number of buckets.
32 *
33 *              The DataMap can be seen as an extended array where
34 *              the Keys  are the   indices.  For this reason  the
35 *              operator () is defined on DataMap to fetch an Item
36 *              from a Key. So the following syntax can be used :
37 *
38 *              anItem = aMap(aKey);
39 *              aMap(aKey) = anItem;
40 *
41 *              This analogy has its  limit.   aMap(aKey) = anItem
42 *              can  be done only  if aKey was previously bound to
43 *              an item in the map.
44 */              
45
46 template < class TheKeyType, 
47            class TheItemType, 
48            class Hasher = NCollection_DefaultHasher<TheKeyType> >  class NCollection_DataMap 
49   
50   : public NCollection_BaseCollection<TheItemType>,
51     public NCollection_BaseMap
52 {
53   // **************** Adaptation of the TListNode to the DATAmap
54  public:
55   class DataMapNode : public NCollection_TListNode<TheItemType>
56   {
57   public:
58     //! Constructor with 'Next'
59     DataMapNode (const TheKeyType&     theKey, 
60                  const TheItemType&    theItem, 
61                  NCollection_ListNode* theNext) :
62                    NCollection_TListNode<TheItemType> (theItem, theNext) 
63     { myKey = theKey; }
64     //! Key
65     const TheKeyType& Key (void) const
66     { return myKey; }
67     
68     //! Static deleter to be passed to BaseList
69     static void delNode (NCollection_ListNode * theNode, 
70                          Handle(NCollection_BaseAllocator)& theAl)
71     {
72       ((DataMapNode *) theNode)->~DataMapNode();
73       theAl->Free(theNode);
74     }
75
76   private:
77     TheKeyType    myKey;
78   };
79
80  public:
81   // **************** Implementation of the Iterator interface.
82   class Iterator 
83     : public NCollection_BaseCollection<TheItemType>::Iterator,
84       public NCollection_BaseMap::Iterator
85   {
86   public:
87     //! Empty constructor
88     Iterator (void) :
89       NCollection_BaseMap::Iterator() {}
90     //! Constructor
91     Iterator (const NCollection_DataMap& theMap) :
92       NCollection_BaseMap::Iterator(theMap) {}
93     //! Query if the end of collection is reached by iterator
94     virtual Standard_Boolean More(void) const
95     { return PMore(); }
96     //! Make a step along the collection
97     virtual void Next(void)
98     { PNext(); }
99     //! Value inquiry
100     virtual const TheItemType& Value(void) const
101     {  
102 #if !defined No_Exception && !defined No_Standard_NoSuchObject
103       if (!More())
104         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value");  
105 #endif
106       return ((DataMapNode *) myNode)->Value();
107     }
108     //! Value change access
109     virtual TheItemType& ChangeValue(void) const
110     {  
111 #if !defined No_Exception && !defined No_Standard_NoSuchObject
112       if (!More())
113         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue");  
114 #endif
115       return ((DataMapNode *) myNode)->ChangeValue();
116     }
117     //! Key
118     const TheKeyType& Key (void) const
119     { 
120 #if !defined No_Exception && !defined No_Standard_NoSuchObject
121       if (!More())
122         Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key");  
123 #endif
124       return ((DataMapNode *) myNode)->Key();
125     }
126   };
127
128  public:
129   // ---------- PUBLIC METHODS ------------
130
131   //! Constructor
132   NCollection_DataMap (const Standard_Integer NbBuckets=1,
133                      const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
134     : NCollection_BaseCollection<TheItemType>(theAllocator),
135       NCollection_BaseMap (NbBuckets, Standard_True) {}
136
137   //! Copy constructor
138   NCollection_DataMap (const NCollection_DataMap& theOther)
139     : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
140       NCollection_BaseMap (theOther.NbBuckets(), Standard_True) 
141   { *this = theOther; }
142
143   //! Assign another collection
144   virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
145   { 
146     if (this == &theOther)
147       return;
148     Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible");
149   }
150
151   //! Exchange the content of two maps without re-allocations.
152   //! Notice that allocators will be swapped as well!
153   void Exchange (NCollection_DataMap& theOther)
154   {
155     this->exchangeAllocators (theOther);
156     this->exchangeMapsData   (theOther);
157   }
158
159   //! = another map
160   NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
161   { 
162     if (this == &theOther)
163       return *this;
164
165     Clear(theOther.myAllocator);
166     ReSize (theOther.Extent()-1);
167     Iterator anIter(theOther);
168     for (; anIter.More(); anIter.Next())
169       Bind (anIter.Key(), anIter.Value());
170     return *this;
171   }
172
173   //! ReSize
174   void ReSize (const Standard_Integer N)
175   {
176     NCollection_ListNode** newdata = NULL;
177     NCollection_ListNode** dummy   = NULL;
178     Standard_Integer newBuck;
179     if (BeginResize (N, newBuck, newdata, dummy, this->myAllocator))
180     {
181       if (myData1) 
182       {
183         DataMapNode** olddata = (DataMapNode**) myData1;
184         DataMapNode *p, *q;
185         Standard_Integer i,k;
186         for (i = 0; i <= NbBuckets(); i++) 
187         {
188           if (olddata[i]) 
189           {
190             p = olddata[i];
191             while (p) 
192             {
193               k = Hasher::HashCode(p->Key(),newBuck);
194               q = (DataMapNode*) p->Next();
195               p->Next() = newdata[k];
196               newdata[k] = p;
197               p = q;
198             }
199           }
200         }
201       }
202       EndResize (N, newBuck, newdata, dummy, this->myAllocator);
203     }
204   }
205
206   //! Bind
207   Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
208   {
209     if (Resizable()) 
210       ReSize(Extent());
211     DataMapNode** data = (DataMapNode**)myData1;
212     Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
213     DataMapNode* p = data[k];
214     while (p) 
215     {
216       if (Hasher::IsEqual(p->Key(), theKey))
217       {
218         p->ChangeValue() = theItem;
219         return Standard_False;
220       }
221       p = (DataMapNode *) p->Next();
222     }
223     data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
224     Increment();
225     return Standard_True;
226   }
227
228   //! IsBound
229   Standard_Boolean IsBound(const TheKeyType& K) const
230   {
231     if (IsEmpty()) 
232       return Standard_False;
233     DataMapNode** data = (DataMapNode**) myData1;
234     DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
235     while (p) 
236     {
237       if (Hasher::IsEqual(p->Key(),K)) 
238         return Standard_True;
239       p = (DataMapNode *) p->Next();
240     }
241     return Standard_False;
242   }
243
244   //! UnBind
245   Standard_Boolean UnBind(const TheKeyType& K)
246   {
247     if (IsEmpty()) 
248       return Standard_False;
249     DataMapNode** data = (DataMapNode**) myData1;
250     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
251     DataMapNode* p = data[k];
252     DataMapNode* q = NULL;
253     while (p) 
254     {
255       if (Hasher::IsEqual(p->Key(),K)) 
256       {
257         Decrement();
258         if (q) 
259           q->Next() = p->Next();
260         else
261           data[k] = (DataMapNode*) p->Next();
262         p->~DataMapNode();
263         this->myAllocator->Free(p);
264         return Standard_True;
265       }
266       q = p;
267       p = (DataMapNode*) p->Next();
268     }
269     return Standard_False;
270   }
271
272   //! Find
273   const TheItemType& Find(const TheKeyType& theKey) const
274   {
275 #if !defined No_Exception && !defined No_Standard_NoSuchObject
276     if (IsEmpty())
277       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
278 #endif
279     DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
280     while (p) 
281     {
282       if (Hasher::IsEqual(p->Key(),theKey)) 
283         return p->Value();
284       p = (DataMapNode*) p->Next();
285     }
286     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
287     return p->Value(); // This for compiler
288   }
289
290   //! Find value for key with copying.
291   //! @return true if key was found
292   Standard_Boolean Find (const TheKeyType& theKey,
293                          TheItemType&      theValue) const
294   {
295     if (IsEmpty())
296     {
297       return Standard_False;
298     }
299
300     for (DataMapNode* aNodeIter = (DataMapNode* )myData1[Hasher::HashCode (theKey, NbBuckets())];
301          aNodeIter != NULL;
302          aNodeIter = (DataMapNode* )aNodeIter->Next())
303     {
304       if (Hasher::IsEqual (aNodeIter->Key(), theKey))
305       {
306         theValue = aNodeIter->Value();
307         return Standard_True;
308       }
309     }
310     return Standard_False;
311   }
312
313   //! operator ()
314   const TheItemType& operator() (const TheKeyType& theKey) const
315   { return Find(theKey); }
316
317   //! ChangeFind
318   TheItemType& ChangeFind (const TheKeyType& theKey)
319   {
320 #if !defined No_Exception && !defined No_Standard_NoSuchObject
321     if (IsEmpty())
322       Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
323 #endif
324     DataMapNode*  p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
325     while (p) 
326     {
327       if (Hasher::IsEqual(p->Key(),theKey)) 
328         return p->ChangeValue();
329       p = (DataMapNode*) p->Next();
330     }
331     Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
332     return p->ChangeValue(); // This for compiler
333   }
334
335   //! operator ()
336   TheItemType& operator() (const TheKeyType& theKey)
337   { return ChangeFind(theKey); }
338
339   //! Clear data. If doReleaseMemory is false then the table of
340   //! buckets is not released and will be reused.
341   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
342   { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); }
343
344   //! Clear data and reset allocator
345   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
346   { 
347     Clear();
348     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
349                     NCollection_BaseAllocator::CommonBaseAllocator() );
350   }
351
352   //! Destructor
353   ~NCollection_DataMap (void)
354   { Clear(); }
355
356   //! Size
357   virtual Standard_Integer Size(void) const
358   { return Extent(); }
359
360  private:
361   // ----------- PRIVATE METHODS -----------
362
363   //! Creates Iterator for use on BaseCollection
364   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& 
365           CreateIterator(void) const
366   { return *(new (this->IterAllocator()) Iterator(*this)); }
367
368 };
369
370 #endif
371