029b82544c1f0f257d89eedabacf63a3678f40cc
[occt.git] / src / NCollection / NCollection_BaseMap.cxx
1 // Created on: 2002-04-18
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 under
8 // the terms of the GNU Lesser General Public License 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 // Purpose:     Implementation of the BaseMap class
17
18 #include <NCollection_BaseMap.hxx>
19 #include <TCollection.hxx>
20
21 //=======================================================================
22 //function : BeginResize
23 //purpose  : 
24 //=======================================================================
25
26 Standard_Boolean  NCollection_BaseMap::BeginResize
27   (const Standard_Integer  NbBuckets,
28    Standard_Integer&       N,
29    NCollection_ListNode**& data1,
30    NCollection_ListNode**& data2,
31    Handle(NCollection_BaseAllocator)& theAllocator) const 
32 {
33   if (mySaturated) return Standard_False;
34   N = NextPrimeForMap(NbBuckets);
35   if (N <= myNbBuckets) {
36     if (!myData1)
37       N = myNbBuckets;
38     else
39       return Standard_False;
40   }
41   data1 = (NCollection_ListNode **)
42     theAllocator->Allocate((N+1)*sizeof(NCollection_ListNode *));
43   memset(data1, 0, (N+1)*sizeof(NCollection_ListNode *));
44   if (isDouble) 
45   {
46     data2 = (NCollection_ListNode **)
47     theAllocator->Allocate((N+1)*sizeof(NCollection_ListNode *));
48     memset(data2, 0, (N+1)*sizeof(NCollection_ListNode *));
49   }
50   else
51     data2 = NULL;
52   return Standard_True;
53 }
54
55 //=======================================================================
56 //function : EndResize
57 //purpose  : 
58 //=======================================================================
59
60 void  NCollection_BaseMap::EndResize
61   (const Standard_Integer NbBuckets,
62    const Standard_Integer N,
63    NCollection_ListNode** data1,
64    NCollection_ListNode** data2,
65    Handle(NCollection_BaseAllocator)& theAllocator)
66 {
67   if (myData1) 
68     theAllocator->Free(myData1);
69   if (myData2) 
70     theAllocator->Free(myData2);
71   myNbBuckets = N;
72   mySaturated = (myNbBuckets <= NbBuckets);
73   myData1 = data1;
74   myData2 = data2;
75 }
76
77
78 //=======================================================================
79 //function : Destroy
80 //purpose  : 
81 //=======================================================================
82
83 void  NCollection_BaseMap::Destroy
84   (NCollection_DelMapNode fDel,
85    Handle(NCollection_BaseAllocator)& theAllocator,
86    const Standard_Boolean doReleaseMemory)
87 {
88   if (!IsEmpty()) 
89   {
90     Standard_Integer i;
91     NCollection_ListNode** data = (NCollection_ListNode**) myData1;
92     NCollection_ListNode *p,*q;
93     for (i = 0; i <= NbBuckets(); i++) 
94     {
95       if (data[i]) 
96       {
97         p = data[i];
98         while (p) 
99         {
100           q = (NCollection_ListNode*)p->Next();
101           fDel (p, theAllocator);
102           p = q;
103         }
104         data[i] = NULL;
105       }
106     }
107   }
108
109   mySize = 0;
110   if (doReleaseMemory)
111   {
112     mySaturated = Standard_False;
113     if (myData1) 
114       theAllocator->Free(myData1);
115     if (isDouble && myData2) 
116       theAllocator->Free(myData2);
117     myData1 = myData2 = NULL;
118   }
119 }
120
121
122 //=======================================================================
123 //function : Statistics
124 //purpose  : 
125 //=======================================================================
126
127 void NCollection_BaseMap::Statistics(Standard_OStream& S) const
128 {
129   S <<"\nMap Statistics\n---------------\n\n";
130   S <<"This Map has "<<myNbBuckets<<" Buckets and "<<mySize<<" Keys\n\n";
131   if (mySaturated) S<<"The maximum number of Buckets is reached\n";
132   
133   if (mySize == 0) return;
134
135   // compute statistics on 1
136   Standard_Integer * sizes = new Standard_Integer [mySize+1];
137   Standard_Integer i,l,nb;
138   NCollection_ListNode* p;
139   NCollection_ListNode** data;
140   
141   S << "\nStatistics for the first Key\n";
142   for (i = 0; i <= mySize; i++) sizes[i] = 0;
143   data = (NCollection_ListNode **) myData1;
144   nb = 0;
145   for (i = 0; i <= myNbBuckets; i++) 
146   {
147     l = 0;
148     p = data[i];
149     if (p) nb++;
150     while (p) 
151     {
152       l++;
153       p = p->Next();
154     }
155     sizes[l]++;
156   }
157
158   // display results
159   l = 0;
160   for (i = 0; i<= mySize; i++) 
161   {
162     if (sizes[i] > 0) 
163     {
164       l += sizes[i] * i;
165       S << setw(5) << sizes[i] <<" buckets of size "<<i<<"\n";
166     }
167   }
168
169   Standard_Real mean = ((Standard_Real) l) / ((Standard_Real) nb);
170   S<<"\n\nMean of length : "<<mean<<"\n";
171
172   delete [] sizes;
173 }
174
175 //=======================================================================
176 //function : NextPrimeForMap
177 //purpose  : 
178 //=======================================================================
179
180 Standard_Integer NCollection_BaseMap::NextPrimeForMap
181   (const Standard_Integer N) const
182 {
183   return TCollection::NextPrimeForMap ( N );
184 }
185