b311480e |
1 | // Created on: 2002-04-18 |
2 | // Created by: Alexander KARTOMIN (akm) |
973c2be1 |
3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
b311480e |
15 | |
7fd59977 |
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 | |