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