| /************************************************************** |
| * |
| * 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 <tools/debug.hxx> |
| #include <impcont.hxx> |
| #include <tools/table.hxx> |
| |
| // ======================================================================= |
| |
| 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 |
| |
| if( void** pNodes = Container::ImpGetOnlyNodes() ) |
| { |
| sal_uIntPtr nCompareKey = (sal_uIntPtr)(*pNodes); |
| while ( nKey > nCompareKey ) |
| { |
| n += 2; |
| pNodes += 2; |
| if ( n < nTempCount ) |
| nCompareKey = (sal_uIntPtr)(*pNodes); |
| else |
| { |
| nCompareKey = 0; |
| break; |
| } |
| } |
| |
| // Testen, ob sich der Key schon in der Tabelle befindet |
| if ( nKey == nCompareKey ) |
| return sal_False; |
| |
| i = n; |
| } |
| else |
| { |
| i = 0; |
| if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND ) |
| return sal_False; |
| } |
| //-->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; |
| } |
