0029302: Foundation Classes, NCollection - optimize iteration of indexed maps
[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) const 
31 {
32   N = NextPrimeForMap(NbBuckets);
33   if (N <= myNbBuckets) {
34     if (!myData1)
35       N = myNbBuckets;
36     else
37       return Standard_False;
38   }
39   data1 = (NCollection_ListNode **)
40     myAllocator->Allocate((N+1)*sizeof(NCollection_ListNode *));
41   memset(data1, 0, (N+1)*sizeof(NCollection_ListNode *));
42   if (isDouble) 
43   {
44     data2 = (NCollection_ListNode **)
45     myAllocator->Allocate((N+1)*sizeof(NCollection_ListNode *));
46     memset(data2, 0, (N+1)*sizeof(NCollection_ListNode *));
47   }
48   else
49     data2 = NULL;
50   return Standard_True;
51 }
52
53 //=======================================================================
54 //function : EndResize
55 //purpose  : 
56 //=======================================================================
57
58 void  NCollection_BaseMap::EndResize
59   (const Standard_Integer theNbBuckets,
60    const Standard_Integer N,
61    NCollection_ListNode** data1,
62    NCollection_ListNode** data2)
63 {
64   (void )theNbBuckets; // obsolete parameter
65   if (myData1) 
66     myAllocator->Free(myData1);
67   if (myData2) 
68     myAllocator->Free(myData2);
69   myNbBuckets = N;
70   myData1 = data1;
71   myData2 = data2;
72 }
73
74
75 //=======================================================================
76 //function : Destroy
77 //purpose  : 
78 //=======================================================================
79
80 void  NCollection_BaseMap::Destroy (NCollection_DelMapNode fDel,
81                                     Standard_Boolean doReleaseMemory)
82 {
83   if (!IsEmpty()) 
84   {
85     Standard_Integer i;
86     NCollection_ListNode** data = (NCollection_ListNode**) myData1;
87     NCollection_ListNode *p,*q;
88     for (i = 0; i <= NbBuckets(); i++) 
89     {
90       if (data[i]) 
91       {
92         p = data[i];
93         while (p) 
94         {
95           q = (NCollection_ListNode*)p->Next();
96           fDel (p, myAllocator);
97           p = q;
98         }
99         data[i] = NULL;
100       }
101     }
102   }
103
104   mySize = 0;
105   if (doReleaseMemory)
106   {
107     if (myData1) 
108       myAllocator->Free(myData1);
109     if (isDouble && myData2) 
110       myAllocator->Free(myData2);
111     myData1 = myData2 = NULL;
112   }
113 }
114
115
116 //=======================================================================
117 //function : Statistics
118 //purpose  : 
119 //=======================================================================
120
121 void NCollection_BaseMap::Statistics(Standard_OStream& S) const
122 {
123   S <<"\nMap Statistics\n---------------\n\n";
124   S <<"This Map has "<<myNbBuckets<<" Buckets and "<<mySize<<" Keys\n\n";
125   
126   if (mySize == 0) return;
127
128   // compute statistics on 1
129   Standard_Integer * sizes = new Standard_Integer [mySize+1];
130   Standard_Integer i,l,nb;
131   NCollection_ListNode* p;
132   NCollection_ListNode** data;
133   
134   S << "\nStatistics for the first Key\n";
135   for (i = 0; i <= mySize; i++) sizes[i] = 0;
136   data = (NCollection_ListNode **) myData1;
137   nb = 0;
138   for (i = 0; i <= myNbBuckets; i++) 
139   {
140     l = 0;
141     p = data[i];
142     if (p) nb++;
143     while (p) 
144     {
145       l++;
146       p = p->Next();
147     }
148     sizes[l]++;
149   }
150
151   // display results
152   l = 0;
153   for (i = 0; i<= mySize; i++) 
154   {
155     if (sizes[i] > 0) 
156     {
157       l += sizes[i] * i;
158       S << setw(5) << sizes[i] <<" buckets of size "<<i<<"\n";
159     }
160   }
161
162   Standard_Real mean = ((Standard_Real) l) / ((Standard_Real) nb);
163   S<<"\n\nMean of length : "<<mean<<"\n";
164
165   delete [] sizes;
166 }
167
168 //=======================================================================
169 //function : NextPrimeForMap
170 //purpose  : 
171 //=======================================================================
172
173 Standard_Integer NCollection_BaseMap::NextPrimeForMap
174   (const Standard_Integer N) const
175 {
176   return TCollection::NextPrimeForMap ( N );
177 }
178