b311480e |
1 | // Created on: 2002-04-18 |
2 | // Created by: Alexander KARTOMIN (akm) |
3 | // Copyright (c) 2002-2012 OPEN CASCADE SAS |
4 | // |
5 | // The content of this file is subject to the Open CASCADE Technology Public |
6 | // License Version 6.5 (the "License"). You may not use the content of this file |
7 | // except in compliance with the License. Please obtain a copy of the License |
8 | // at http://www.opencascade.org and read it completely before using this file. |
9 | // |
10 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its |
11 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. |
12 | // |
13 | // The Original Code and all software distributed under the License is |
14 | // distributed on an "AS IS" basis, without warranty of any kind, and the |
15 | // Initial Developer hereby disclaims all such warranties, including without |
16 | // limitation, any warranties of merchantability, fitness for a particular |
17 | // purpose or non-infringement. Please see the License for the specific terms |
18 | // and conditions governing the rights and limitations under the License. |
19 | |
7fd59977 |
20 | // Purpose: Implementation of the BaseMap class |
21 | |
22 | #include <NCollection_BaseMap.hxx> |
23 | #include <TCollection.hxx> |
24 | |
25 | //======================================================================= |
26 | //function : BeginResize |
27 | //purpose : |
28 | //======================================================================= |
29 | |
30 | Standard_Boolean NCollection_BaseMap::BeginResize |
31 | (const Standard_Integer NbBuckets, |
32 | Standard_Integer& N, |
33 | NCollection_ListNode**& data1, |
34 | NCollection_ListNode**& data2, |
35 | Handle(NCollection_BaseAllocator)& theAllocator) const |
36 | { |
37 | if (mySaturated) return Standard_False; |
38 | N = NextPrimeForMap(NbBuckets); |
39 | if (N <= myNbBuckets) { |
40 | if (!myData1) |
41 | N = myNbBuckets; |
42 | else |
43 | return Standard_False; |
44 | } |
45 | data1 = (NCollection_ListNode **) |
46 | theAllocator->Allocate((N+1)*sizeof(NCollection_ListNode *)); |
47 | memset(data1, 0, (N+1)*sizeof(NCollection_ListNode *)); |
48 | if (isDouble) |
49 | { |
50 | data2 = (NCollection_ListNode **) |
51 | theAllocator->Allocate((N+1)*sizeof(NCollection_ListNode *)); |
52 | memset(data2, 0, (N+1)*sizeof(NCollection_ListNode *)); |
53 | } |
54 | else |
55 | data2 = NULL; |
56 | return Standard_True; |
57 | } |
58 | |
59 | //======================================================================= |
60 | //function : EndResize |
61 | //purpose : |
62 | //======================================================================= |
63 | |
64 | void NCollection_BaseMap::EndResize |
65 | (const Standard_Integer NbBuckets, |
66 | const Standard_Integer N, |
67 | NCollection_ListNode** data1, |
68 | NCollection_ListNode** data2, |
69 | Handle(NCollection_BaseAllocator)& theAllocator) |
70 | { |
71 | if (myData1) |
72 | theAllocator->Free(myData1); |
73 | if (myData2) |
74 | theAllocator->Free(myData2); |
75 | myNbBuckets = N; |
76 | mySaturated = (myNbBuckets <= NbBuckets); |
77 | myData1 = data1; |
78 | myData2 = data2; |
79 | } |
80 | |
81 | |
82 | //======================================================================= |
83 | //function : Destroy |
84 | //purpose : |
85 | //======================================================================= |
86 | |
87 | void NCollection_BaseMap::Destroy |
88 | (NCollection_DelMapNode fDel, |
89 | Handle(NCollection_BaseAllocator)& theAllocator, |
90 | const Standard_Boolean doReleaseMemory) |
91 | { |
92 | if (!IsEmpty()) |
93 | { |
94 | Standard_Integer i; |
95 | NCollection_ListNode** data = (NCollection_ListNode**) myData1; |
96 | NCollection_ListNode *p,*q; |
97 | for (i = 0; i <= NbBuckets(); i++) |
98 | { |
99 | if (data[i]) |
100 | { |
101 | p = data[i]; |
102 | while (p) |
103 | { |
104 | q = (NCollection_ListNode*)p->Next(); |
105 | fDel (p, theAllocator); |
106 | p = q; |
107 | } |
108 | data[i] = NULL; |
109 | } |
110 | } |
111 | } |
112 | |
113 | mySize = 0; |
114 | if (doReleaseMemory) |
115 | { |
116 | mySaturated = Standard_False; |
117 | if (myData1) |
118 | theAllocator->Free(myData1); |
119 | if (isDouble && myData2) |
120 | theAllocator->Free(myData2); |
121 | myData1 = myData2 = NULL; |
122 | } |
123 | } |
124 | |
125 | |
126 | //======================================================================= |
127 | //function : Statistics |
128 | //purpose : |
129 | //======================================================================= |
130 | |
131 | void NCollection_BaseMap::Statistics(Standard_OStream& S) const |
132 | { |
133 | S <<"\nMap Statistics\n---------------\n\n"; |
134 | S <<"This Map has "<<myNbBuckets<<" Buckets and "<<mySize<<" Keys\n\n"; |
135 | if (mySaturated) S<<"The maximum number of Buckets is reached\n"; |
136 | |
137 | if (mySize == 0) return; |
138 | |
139 | // compute statistics on 1 |
140 | Standard_Integer * sizes = new Standard_Integer [mySize+1]; |
141 | Standard_Integer i,l,nb; |
142 | NCollection_ListNode* p; |
143 | NCollection_ListNode** data; |
144 | |
145 | S << "\nStatistics for the first Key\n"; |
146 | for (i = 0; i <= mySize; i++) sizes[i] = 0; |
147 | data = (NCollection_ListNode **) myData1; |
148 | nb = 0; |
149 | for (i = 0; i <= myNbBuckets; i++) |
150 | { |
151 | l = 0; |
152 | p = data[i]; |
153 | if (p) nb++; |
154 | while (p) |
155 | { |
156 | l++; |
157 | p = p->Next(); |
158 | } |
159 | sizes[l]++; |
160 | } |
161 | |
162 | // display results |
163 | l = 0; |
164 | for (i = 0; i<= mySize; i++) |
165 | { |
166 | if (sizes[i] > 0) |
167 | { |
168 | l += sizes[i] * i; |
169 | S << setw(5) << sizes[i] <<" buckets of size "<<i<<"\n"; |
170 | } |
171 | } |
172 | |
173 | Standard_Real mean = ((Standard_Real) l) / ((Standard_Real) nb); |
174 | S<<"\n\nMean of length : "<<mean<<"\n"; |
175 | |
176 | delete [] sizes; |
177 | } |
178 | |
179 | //======================================================================= |
180 | //function : NextPrimeForMap |
181 | //purpose : |
182 | //======================================================================= |
183 | |
184 | Standard_Integer NCollection_BaseMap::NextPrimeForMap |
185 | (const Standard_Integer N) const |
186 | { |
187 | return TCollection::NextPrimeForMap ( N ); |
188 | } |
189 | |