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