/************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * *************************************************************/ // MARKER(update_precomp.py): autogen include statement, do not remove #include "precompiled_tools.hxx" #define _TOOLS_TABLE_CXX // ----------------------------------------------------------------------- #include #include #include // ======================================================================= sal_uIntPtr Table::ImplGetIndex( sal_uIntPtr nKey, sal_uIntPtr* pIndex ) const { // Abpruefen, ob der erste Key groesser als der Vergleichskey ist if ( !nCount || (nKey < (sal_uIntPtr)Container::ImpGetObject(0)) ) return TABLE_ENTRY_NOTFOUND; sal_uIntPtr nLow; sal_uIntPtr nHigh; sal_uIntPtr nMid; sal_uIntPtr nCompareKey; void** pNodes = Container::ImpGetOnlyNodes(); // Binaeres Suchen nLow = 0; nHigh = nCount-1; if ( pNodes ) { do { nMid = (nLow + nHigh) / 2; nCompareKey = (sal_uIntPtr)pNodes[nMid*2]; if ( nKey < nCompareKey ) nHigh = nMid-1; else { if ( nKey > nCompareKey ) nLow = nMid + 1; else return nMid*2; } } while ( nLow <= nHigh ); } else { do { nMid = (nLow + nHigh) / 2; nCompareKey = (sal_uIntPtr)Container::ImpGetObject( nMid*2 ); if ( nKey < nCompareKey ) nHigh = nMid-1; else { if ( nKey > nCompareKey ) nLow = nMid + 1; else return nMid*2; } } while ( nLow <= nHigh ); } if ( pIndex ) { if ( nKey > nCompareKey ) *pIndex = (nMid+1)*2; else *pIndex = nMid*2; } return TABLE_ENTRY_NOTFOUND; } // ======================================================================= Table::Table( sal_uInt16 _nInitSize, sal_uInt16 _nReSize ) : Container( CONTAINER_MAXBLOCKSIZE, _nInitSize*2, _nReSize*2 ) { DBG_ASSERT( _nInitSize <= 32767, "Table::Table(): InitSize > 32767" ); DBG_ASSERT( _nReSize <= 32767, "Table::Table(): ReSize > 32767" ); nCount = 0; } // ----------------------------------------------------------------------- sal_Bool Table::Insert( sal_uIntPtr nKey, void* p ) { // Tabellenelement einsortieren sal_uIntPtr i; if ( nCount ) { if ( nCount <= 24 ) { sal_uInt16 n = 0; sal_uInt16 nTempCount = (sal_uInt16)nCount * 2; //Modified by PengYunQuan for resolving a NULL pointer access } else { i = 0; if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND ) return sal_False; } } else i = 0; // Eintrag einfuegen (Key vor Pointer) Container::Insert( (void*)nKey, i ); Container::Insert( p, i+1 ); // Ein neuer Eintrag nCount++; return sal_True; } // ----------------------------------------------------------------------- void* Table::Remove( sal_uIntPtr nKey ) { // Index besorgen sal_uIntPtr nIndex = ImplGetIndex( nKey ); // Testen, ob sich der Key in der Tabelle befindet if ( nIndex == TABLE_ENTRY_NOTFOUND ) return NULL; // Itemanzahl erniedrigen nCount--; // Key entfernen Container::Remove( nIndex ); // Pointer entfernen und zurueckgeben return Container::Remove( nIndex ); } // ----------------------------------------------------------------------- void* Table::Replace( sal_uIntPtr nKey, void* p ) { // Index abfragen sal_uIntPtr nIndex = ImplGetIndex( nKey ); // Existiert kein Eintrag mit dem Schluessel if ( nIndex == TABLE_ENTRY_NOTFOUND ) return NULL; else return Container::Replace( p, nIndex+1 ); } // ----------------------------------------------------------------------- void* Table::Get( sal_uIntPtr nKey ) const { // Index besorgen sal_uIntPtr nIndex = ImplGetIndex( nKey ); // Testen, ob sich der Key in der Tabelle befindet if ( nIndex == TABLE_ENTRY_NOTFOUND ) return NULL; else return Container::ImpGetObject( nIndex+1 ); } // ----------------------------------------------------------------------- void* Table::GetCurObject() const { return Container::ImpGetObject( Container::GetCurPos()+1 ); } // ----------------------------------------------------------------------- sal_uIntPtr Table::GetKey( const void* p ) const { sal_uIntPtr nIndex = 0; // Solange noch Eintraege Vorhanden sind while ( nIndex < nCount ) { // Stimmt der Pointer ueberein, wird der Key zurueckgegeben if ( p == Container::ImpGetObject( (nIndex*2)+1 ) ) return (sal_uIntPtr)Container::ImpGetObject( nIndex*2 ); nIndex++; } return TABLE_ENTRY_NOTFOUND; } // ----------------------------------------------------------------------- sal_Bool Table::IsKeyValid( sal_uIntPtr nKey ) const { return (ImplGetIndex( nKey ) != TABLE_ENTRY_NOTFOUND) ? sal_True : sal_False; } // ----------------------------------------------------------------------- sal_uIntPtr Table::GetUniqueKey( sal_uIntPtr nStartKey ) const { DBG_ASSERT( (nStartKey > 1) && (nStartKey < 0xFFFFFFFF), "Table::GetUniqueKey() - nStartKey == 0 or nStartKey >= 0xFFFFFFFF" ); if ( !nCount ) return nStartKey; sal_uIntPtr nLastKey = (sal_uIntPtr)Container::GetObject( (nCount*2)-2 ); if ( nLastKey < nStartKey ) return nStartKey; else { if ( nLastKey < 0xFFFFFFFE ) return nLastKey+1; else { sal_uIntPtr nPos; sal_uIntPtr nTempPos = ImplGetIndex( nStartKey, &nPos ); if ( nTempPos != TABLE_ENTRY_NOTFOUND ) nPos = nTempPos; nLastKey = (sal_uIntPtr)Container::GetObject( nPos ); if ( nStartKey < nLastKey ) return nStartKey; while ( nLastKey < 0xFFFFFFFE ) { nPos += 2; nLastKey++; if ( nLastKey != (sal_uIntPtr)Container::GetObject( nPos ) ) return nLastKey; } } } return 0; } // ----------------------------------------------------------------------- sal_uIntPtr Table::SearchKey( sal_uIntPtr nKey, sal_uIntPtr* pPos ) const { *pPos = 0; sal_uIntPtr nPos = ImplGetIndex( nKey, pPos ); if ( nPos != TABLE_ENTRY_NOTFOUND ) { nPos /= 2; *pPos = nPos; } else *pPos /= 2; return nPos; } // ----------------------------------------------------------------------- void* Table::Seek( sal_uIntPtr nKey ) { // Testen, ob ein Eintrag vorhanden ist if ( nCount ) { sal_uIntPtr nIndex = ImplGetIndex( nKey ); // Ist Key nicht enthalten if ( nIndex == TABLE_ENTRY_NOTFOUND ) return NULL; else { // Index setzen Container::Seek( nIndex ); // Pointer zurueckgeben return Container::ImpGetObject( Container::GetCurPos() + 1 ); } } else return NULL; } // ----------------------------------------------------------------------- void* Table::Seek( void* p ) { sal_uIntPtr nKey = GetKey( p ); // Ist Key vorhanden, dann als aktuellen Eintrag setzen if ( nKey != TABLE_ENTRY_NOTFOUND ) return Seek( nKey ); else return NULL; } // ----------------------------------------------------------------------- void* Table::First() { // Testen, ob ein Eintrag vorhanden ist if ( nCount ) { // Auf ersten Eintag setzen Container::First(); // Pointer zurueckgeben return Container::ImpGetObject( 1 ); } else return NULL; } // ----------------------------------------------------------------------- void* Table::Last() { // Testen, ob ein Eintrag vorhanden ist if ( nCount ) { // Last auf letzten Eintrag setzen void* p = Container::Last(); Container::Prev(); // Pointer zurueckgeben return p; } else return NULL; } // ----------------------------------------------------------------------- void* Table::Next() { // Ueber den Pointer weiterschalten Container::Next(); // Nachsten Eintag Container::Next(); // Pointer vom naechsten Key zurueckgeben return Container::ImpGetObject( Container::GetCurPos() + 1 ); } // ----------------------------------------------------------------------- void* Table::Prev() { // Ueber den Pointer weiterschalten void* p = Container::Prev(); // Nachsten Eintag Container::Prev(); // Pointer vom vorherigen Key zurueckgeben return p; }