xref: /aoo42x/main/tools/source/memtools/table.cxx (revision 79aad27f)
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_tools.hxx"
26 
27 #define _TOOLS_TABLE_CXX
28 
29 // -----------------------------------------------------------------------
30 #include <tools/debug.hxx>
31 #include <impcont.hxx>
32 #include <tools/table.hxx>
33 
34 // =======================================================================
35 
ImplGetIndex(sal_uIntPtr nKey,sal_uIntPtr * pIndex) const36 sal_uIntPtr Table::ImplGetIndex( sal_uIntPtr nKey, sal_uIntPtr* pIndex ) const
37 {
38 	// Abpruefen, ob der erste Key groesser als der Vergleichskey ist
39 	if ( !nCount || (nKey < (sal_uIntPtr)Container::ImpGetObject(0)) )
40 		return TABLE_ENTRY_NOTFOUND;
41 
42 	sal_uIntPtr	nLow;
43 	sal_uIntPtr	nHigh;
44 	sal_uIntPtr	nMid;
45 	sal_uIntPtr	nCompareKey;
46 	void**	pNodes = Container::ImpGetOnlyNodes();
47 
48 	// Binaeres Suchen
49 	nLow  = 0;
50 	nHigh = nCount-1;
51 	if ( pNodes )
52 	{
53 		do
54 		{
55 			nMid = (nLow + nHigh) / 2;
56 			nCompareKey = (sal_uIntPtr)pNodes[nMid*2];
57 			if ( nKey < nCompareKey )
58 				nHigh = nMid-1;
59 			else
60 			{
61 				if ( nKey > nCompareKey )
62 					nLow = nMid + 1;
63 				else
64 					return nMid*2;
65 			}
66 		}
67 		while ( nLow <= nHigh );
68 	}
69 	else
70 	{
71 		do
72 		{
73 			nMid = (nLow + nHigh) / 2;
74 			nCompareKey = (sal_uIntPtr)Container::ImpGetObject( nMid*2 );
75 			if ( nKey < nCompareKey )
76 				nHigh = nMid-1;
77 			else
78 			{
79 				if ( nKey > nCompareKey )
80 					nLow = nMid + 1;
81 				else
82 					return nMid*2;
83 			}
84 		}
85 		while ( nLow <= nHigh );
86 	}
87 
88 	if ( pIndex )
89 	{
90 		if ( nKey > nCompareKey )
91 			*pIndex = (nMid+1)*2;
92 		else
93 			*pIndex = nMid*2;
94 	}
95 
96 	return TABLE_ENTRY_NOTFOUND;
97 }
98 
99 // =======================================================================
100 
Table(sal_uInt16 _nInitSize,sal_uInt16 _nReSize)101 Table::Table( sal_uInt16 _nInitSize, sal_uInt16 _nReSize ) :
102 		   Container( CONTAINER_MAXBLOCKSIZE, _nInitSize*2, _nReSize*2 )
103 {
104 	DBG_ASSERT( _nInitSize <= 32767, "Table::Table(): InitSize > 32767" );
105 	DBG_ASSERT( _nReSize <= 32767, "Table::Table(): ReSize > 32767" );
106 	nCount = 0;
107 }
108 
109 // -----------------------------------------------------------------------
110 
Insert(sal_uIntPtr nKey,void * p)111 sal_Bool Table::Insert( sal_uIntPtr nKey, void* p )
112 {
113 	// Tabellenelement einsortieren
114 	sal_uIntPtr i;
115 	if ( nCount )
116 	{
117 		if ( nCount <= 24 )
118 		{
119 			sal_uInt16 n = 0;
120 			sal_uInt16 nTempCount = (sal_uInt16)nCount * 2;
121 			//<!--Modified by PengYunQuan for resolving a NULL pointer access
122 
123 			if( void** pNodes = Container::ImpGetOnlyNodes() )
124 			{
125 				sal_uIntPtr  nCompareKey = (sal_uIntPtr)(*pNodes);
126 				while ( nKey > nCompareKey )
127 				{
128 					n += 2;
129 					pNodes += 2;
130 					if ( n < nTempCount )
131 						nCompareKey = (sal_uIntPtr)(*pNodes);
132 					else
133 					{
134 						nCompareKey = 0;
135 						break;
136 					}
137 				}
138 
139 				// Testen, ob sich der Key schon in der Tabelle befindet
140 				if ( nKey == nCompareKey )
141 					return sal_False;
142 
143 				i = n;
144 			}
145 			else
146 			{
147 				i = 0;
148 				if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND )
149 					return sal_False;
150 			}
151 			//-->Modified by PengYunQuan for resolving a NULL pointer access
152 		}
153 		else
154 		{
155 			i = 0;
156 			if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND )
157 				return sal_False;
158 		}
159 	}
160 	else
161 		i = 0;
162 
163 	// Eintrag einfuegen (Key vor Pointer)
164 	Container::Insert( (void*)nKey, i );
165 	Container::Insert( p, i+1 );
166 
167 	// Ein neuer Eintrag
168 	nCount++;
169 
170 	return sal_True;
171 }
172 
173 // -----------------------------------------------------------------------
174 
Remove(sal_uIntPtr nKey)175 void* Table::Remove( sal_uIntPtr nKey )
176 {
177 	// Index besorgen
178 	sal_uIntPtr nIndex = ImplGetIndex( nKey );
179 
180 	// Testen, ob sich der Key in der Tabelle befindet
181 	if ( nIndex == TABLE_ENTRY_NOTFOUND )
182 		return NULL;
183 
184 	// Itemanzahl erniedrigen
185 	nCount--;
186 
187 	// Key entfernen
188 	Container::Remove( nIndex );
189 
190 	// Pointer entfernen und zurueckgeben
191 	return Container::Remove( nIndex );
192 }
193 
194 // -----------------------------------------------------------------------
195 
Replace(sal_uIntPtr nKey,void * p)196 void* Table::Replace( sal_uIntPtr nKey, void* p )
197 {
198 	// Index abfragen
199 	sal_uIntPtr nIndex = ImplGetIndex( nKey );
200 
201 	// Existiert kein Eintrag mit dem Schluessel
202 	if ( nIndex == TABLE_ENTRY_NOTFOUND )
203 		return NULL;
204 	else
205 		return Container::Replace( p, nIndex+1 );
206 }
207 
208 // -----------------------------------------------------------------------
209 
Get(sal_uIntPtr nKey) const210 void* Table::Get( sal_uIntPtr nKey ) const
211 {
212 	// Index besorgen
213 	sal_uIntPtr nIndex = ImplGetIndex( nKey );
214 
215 	// Testen, ob sich der Key in der Tabelle befindet
216 	if ( nIndex == TABLE_ENTRY_NOTFOUND )
217 		return NULL;
218 	else
219 		return Container::ImpGetObject( nIndex+1 );
220 }
221 
222 // -----------------------------------------------------------------------
223 
GetCurObject() const224 void* Table::GetCurObject() const
225 {
226 	return Container::ImpGetObject( Container::GetCurPos()+1 );
227 }
228 
229 // -----------------------------------------------------------------------
230 
GetKey(const void * p) const231 sal_uIntPtr Table::GetKey( const void* p ) const
232 {
233 	sal_uIntPtr nIndex = 0;
234 
235 	// Solange noch Eintraege Vorhanden sind
236 	while ( nIndex < nCount )
237 	{
238 		// Stimmt der Pointer ueberein, wird der Key zurueckgegeben
239 		if ( p == Container::ImpGetObject( (nIndex*2)+1 ) )
240 			return (sal_uIntPtr)Container::ImpGetObject( nIndex*2 );
241 
242 		nIndex++;
243 	}
244 
245 	return TABLE_ENTRY_NOTFOUND;
246 }
247 
248 // -----------------------------------------------------------------------
249 
IsKeyValid(sal_uIntPtr nKey) const250 sal_Bool Table::IsKeyValid( sal_uIntPtr nKey ) const
251 {
252 	return (ImplGetIndex( nKey ) != TABLE_ENTRY_NOTFOUND) ? sal_True : sal_False;
253 }
254 
255 // -----------------------------------------------------------------------
256 
GetUniqueKey(sal_uIntPtr nStartKey) const257 sal_uIntPtr Table::GetUniqueKey( sal_uIntPtr nStartKey ) const
258 {
259 	DBG_ASSERT( (nStartKey > 1) && (nStartKey < 0xFFFFFFFF),
260 				"Table::GetUniqueKey() - nStartKey == 0 or nStartKey >= 0xFFFFFFFF" );
261 
262 	if ( !nCount )
263 		return nStartKey;
264 
265 	sal_uIntPtr nLastKey = (sal_uIntPtr)Container::GetObject( (nCount*2)-2 );
266 	if ( nLastKey < nStartKey )
267 		return nStartKey;
268 	else
269 	{
270 		if ( nLastKey < 0xFFFFFFFE )
271 			return nLastKey+1;
272 		else
273 		{
274 			sal_uIntPtr nPos;
275 			sal_uIntPtr nTempPos = ImplGetIndex( nStartKey, &nPos );
276 			if ( nTempPos != TABLE_ENTRY_NOTFOUND )
277 				nPos = nTempPos;
278 			nLastKey = (sal_uIntPtr)Container::GetObject( nPos );
279 			if ( nStartKey < nLastKey )
280 				return nStartKey;
281 			while ( nLastKey < 0xFFFFFFFE )
282 			{
283 				nPos += 2;
284 				nLastKey++;
285 				if ( nLastKey != (sal_uIntPtr)Container::GetObject( nPos ) )
286 					return nLastKey;
287 			}
288 		}
289 	}
290 
291 	return 0;
292 }
293 
294 // -----------------------------------------------------------------------
295 
SearchKey(sal_uIntPtr nKey,sal_uIntPtr * pPos) const296 sal_uIntPtr Table::SearchKey( sal_uIntPtr nKey, sal_uIntPtr* pPos ) const
297 {
298 	*pPos = 0;
299 	sal_uIntPtr nPos = ImplGetIndex( nKey, pPos );
300 	if ( nPos != TABLE_ENTRY_NOTFOUND )
301 	{
302 		nPos /= 2;
303 		*pPos = nPos;
304 	}
305 	else
306 		*pPos /= 2;
307 	return nPos;
308 }
309 
310 // -----------------------------------------------------------------------
311 
Seek(sal_uIntPtr nKey)312 void* Table::Seek( sal_uIntPtr nKey )
313 {
314 	// Testen, ob ein Eintrag vorhanden ist
315 	if ( nCount )
316 	{
317 		sal_uIntPtr nIndex = ImplGetIndex( nKey );
318 
319 		// Ist Key nicht enthalten
320 		if ( nIndex == TABLE_ENTRY_NOTFOUND )
321 			return NULL;
322 		else
323 		{
324 			// Index setzen
325 			Container::Seek( nIndex );
326 
327 			// Pointer zurueckgeben
328 			return Container::ImpGetObject( Container::GetCurPos() + 1 );
329 		}
330 	}
331 	else
332 		return NULL;
333 }
334 
335 // -----------------------------------------------------------------------
336 
Seek(void * p)337 void* Table::Seek( void* p )
338 {
339 	sal_uIntPtr nKey = GetKey( p );
340 
341 	// Ist Key vorhanden, dann als aktuellen Eintrag setzen
342 	if ( nKey != TABLE_ENTRY_NOTFOUND )
343 		return Seek( nKey );
344 	else
345 		return NULL;
346 }
347 
348 // -----------------------------------------------------------------------
349 
First()350 void* Table::First()
351 {
352 	// Testen, ob ein Eintrag vorhanden ist
353 	if ( nCount )
354 	{
355 		// Auf ersten Eintag setzen
356 		Container::First();
357 
358 		// Pointer zurueckgeben
359 		return Container::ImpGetObject( 1 );
360 	}
361 	else
362 		return NULL;
363 }
364 
365 // -----------------------------------------------------------------------
366 
Last()367 void* Table::Last()
368 {
369 	// Testen, ob ein Eintrag vorhanden ist
370 	if ( nCount )
371 	{
372 		// Last auf letzten Eintrag setzen
373 		void* p = Container::Last();
374 		Container::Prev();
375 
376 		// Pointer zurueckgeben
377 		return p;
378 	}
379 	else
380 		return NULL;
381 }
382 
383 // -----------------------------------------------------------------------
384 
Next()385 void* Table::Next()
386 {
387 	// Ueber den Pointer weiterschalten
388 	Container::Next();
389 
390 	// Nachsten Eintag
391 	Container::Next();
392 
393 	// Pointer vom naechsten Key zurueckgeben
394 	return Container::ImpGetObject( Container::GetCurPos() + 1 );
395 }
396 
397 // -----------------------------------------------------------------------
398 
Prev()399 void* Table::Prev()
400 {
401 	// Ueber den Pointer weiterschalten
402 	void* p = Container::Prev();
403 
404 	// Nachsten Eintag
405 	Container::Prev();
406 
407 	// Pointer vom vorherigen Key zurueckgeben
408 	return p;
409 }
410