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