AOO410/main/sw/source/core/bastyp/bparr.cxx

/**************************************************************
 * 
 * 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_sw.hxx"



#include <string.h>
#include <limits.h>
#include "bparr.hxx"

// die Blockverwaltung waechst/schrumpft immer um 20 Bloecke, das sind dann
// immer ~ 20 * MAXENTRY == 20000 Eintraege
const sal_uInt16 nBlockGrowSize = 20;

#ifndef DBG_UTIL

#define CHECKIDX( p, n, i, c )

#else

#define CHECKIDX( p, n, i, c ) CheckIdx( p, n, i, c );

void CheckIdx( BlockInfo** ppInf, sal_uInt16 nBlock, sal_uLong nSize, sal_uInt16 nCur )
{
	DBG_ASSERT( !nSize || nCur < nBlock, "BigPtrArray: CurIndex steht falsch" );

	sal_uLong nIdx = 0;
	for( sal_uInt16 nCnt = 0; nCnt < nBlock; ++nCnt, ++ppInf )
	{
		nIdx += (*ppInf)->nElem;
		// Array mit Luecken darf es nicht geben
		DBG_ASSERT( !nCnt || (*(ppInf-1))->nEnd + 1 == (*ppInf)->nStart,
					"BigPtrArray: Luecke in der Verwaltung!" );
	}

	DBG_ASSERT( nIdx == nSize, "BigPtrArray: Anzahl ungueltig" );
}

#endif


BigPtrArray::BigPtrArray()
{
	nBlock = nCur = 0;
	nSize = 0;
	nMaxBlock = nBlockGrowSize;		// == 20 * 1000 Eintraege
	ppInf = new BlockInfo* [ nMaxBlock ];
}



BigPtrArray::~BigPtrArray()
{
	if( nBlock )
	{
		BlockInfo** pp = ppInf;
		for( sal_uInt16 n = 0; n < nBlock; ++n, ++pp )
		{
			delete[] (*pp)->pData;
			delete    *pp;
		}
	}
	delete[] ppInf;
}

// Auch der Move ist schlicht. Optimieren ist hier wg. der
// Stueckelung des Feldes zwecklos!

void BigPtrArray::Move( sal_uLong from, sal_uLong to )
{
	sal_uInt16 cur = Index2Block( from );
	BlockInfo* p = ppInf[ cur ];
	ElementPtr pElem = p->pData[ from - p->nStart ];
	Insert( pElem, to );			// erst einfuegen, dann loeschen !!!!
	Remove( ( to < from ) ? ( from + 1 ) : from );
}

// das Ende ist EXCLUSIV


void BigPtrArray::ForEach( sal_uLong nStart, sal_uLong nEnd,
							FnForEach fn, void* pArgs )
{
	if( nEnd > nSize )
		nEnd = nSize;

	if( nStart < nEnd )
	{
		sal_uInt16 cur = Index2Block( nStart );
		BlockInfo** pp = ppInf + cur;
		BlockInfo* p = *pp;
		sal_uInt16 nElem = sal_uInt16( nStart - p->nStart );
		ElementPtr* pElem = p->pData + nElem;
		nElem = p->nElem - nElem;
		for(;;)
		{
			if( !(*fn)( *pElem++, pArgs ) || ++nStart >= nEnd )
				break;

			// naechstes Element
			if( !--nElem )
			{
				// neuer Block
				p = *++pp;
				pElem = p->pData;
				nElem = p->nElem;
			}
		}
	}
}


ElementPtr BigPtrArray::operator[]( sal_uLong idx ) const
{
	// weil die Funktion eben doch nicht const ist:
	DBG_ASSERT( idx < nSize, "operator[]: Index aussserhalb" );
	BigPtrArray* pThis = (BigPtrArray*) this;
	sal_uInt16 cur = Index2Block( idx );
	BlockInfo* p = ppInf[ cur ];
	pThis->nCur = cur;
	return p->pData[ idx - p->nStart ];
}

///////////////////////////////////////////////////////////////////////////

// private Methoden

// Suchen des Blocks einer bestimmten Position
// Algorithmus:
// 1. Test, ob der letzte Block der gesuchte Block ist
// 2. Sonderfall: Index = 0?
// 3. Test der Nachbarbloecke

// 4. Binaere Suche



sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
{
	// zuletzt verwendeter Block?
	BlockInfo* p = ppInf[ nCur ];
	if( p->nStart <= pos && p->nEnd >= pos )
		return nCur;
	// Index = 0?
	if( !pos )
		return 0;
	// Folgeblock?
	if( nCur < ( nBlock - 1 ) )
	{
		p = ppInf[ nCur+1 ];
		if( p->nStart <= pos && p->nEnd >= pos )
			return nCur+1;
	}
	// vorangehender Block?
	else if( pos < p->nStart && nCur > 0 )
	{
		p = ppInf[ nCur-1 ];
		if( p->nStart <= pos && p->nEnd >= pos )
			return nCur-1;
	}
	// Binaere Suche:
	// Diese fuehrt immer zum Erfolg
	sal_uInt16 lower = 0, upper = nBlock - 1;
	sal_uInt16 cur = 0;
	for(;;)
	{
		sal_uInt16 n = lower + ( upper - lower ) / 2;
		cur = ( n == cur ) ? n+1 : n;
		p = ppInf[ cur ];
		if( p->nStart <= pos && p->nEnd >= pos )
			return cur;
		if( p->nStart > pos )
			upper = cur;
		else
			lower = cur;
	}
}


// Update aller Indexbereiche ab einer bestimmten Position

// pos bezeichnet den letzten korrekten Block

void BigPtrArray::UpdIndex( sal_uInt16 pos )
{
	BlockInfo** pp = ppInf + pos;
	sal_uLong idx = (*pp)->nEnd + 1;
	BlockInfo* p;
	while( ++pos < nBlock )
	{
		p = *++pp;
		p->nStart = idx;
		idx       += p->nElem;
		p->nEnd   = idx - 1;
	}
}

// Einrichten eines neuen Blocks an einer bestimmten Position

// Vorhandene Blocks werden nach hinten verschoben



BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
{
	if( nBlock == nMaxBlock )
	{
		// dann sollte wir mal das Array erweitern
		BlockInfo** ppNew = new BlockInfo* [ nMaxBlock + nBlockGrowSize ];
		memcpy( ppNew, ppInf, nMaxBlock * sizeof( BlockInfo* ));
		delete[] ppInf;
		nMaxBlock += nBlockGrowSize;
		ppInf = ppNew;
	}
	if( pos != nBlock )
		memmove( ppInf + pos+1, ppInf + pos ,
				 ( nBlock - pos ) * sizeof (BlockInfo*) );
	++nBlock;
	BlockInfo* p = new BlockInfo;
	ppInf[ pos ] = p;

	if( pos )
		p->nStart = p->nEnd = ppInf[ pos-1 ]->nEnd + 1;
	else
		p->nStart = p->nEnd = 0;
	p->nEnd--;	// keine Elemente
	p->nElem = 0;
	p->pData = new ElementPtr [ MAXENTRY ];
	p->pBigArr = this;
	return p;
}

void BigPtrArray::BlockDel( sal_uInt16 nDel )
{
	nBlock = nBlock - nDel;
	if( nMaxBlock - nBlock > nBlockGrowSize )
	{
		// dann koennen wir wieder schrumpfen
		nDel = (( nBlock / nBlockGrowSize ) + 1 ) * nBlockGrowSize;
		BlockInfo** ppNew = new BlockInfo* [ nDel ];
		memcpy( ppNew, ppInf, nBlock * sizeof( BlockInfo* ));
		delete[] ppInf;
		ppInf = ppNew;
		nMaxBlock = nDel;
	}
}


void BigPtrArray::Insert( const ElementPtr& rElem, sal_uLong pos )
{
	CHECKIDX( ppInf, nBlock, nSize, nCur );

	BlockInfo* p;
	sal_uInt16 cur;
	if( !nSize )
		// Sonderfall: erstes Element einfuegen
		p = InsBlock( cur = 0 );
	else if( pos == nSize )
	{
		// Sonderfall: Einfuegen am Ende
		cur = nBlock - 1;
		p = ppInf[ cur ];
		if( p->nElem == MAXENTRY )
			// Der letzte Block ist voll, neuen anlegen
			p = InsBlock( ++cur );
	}
	else
	{
		// Standardfall:
		cur = Index2Block( pos );
		p = ppInf[ cur ];
	}
	if( p->nElem == MAXENTRY )
	{
		// passt der letzte Eintrag in den naechsten Block?
		BlockInfo* q;
		if( cur < ( nBlock - 1 ) && ppInf[ cur+1 ]->nElem < MAXENTRY )
		{
			q = ppInf[ cur+1 ];
			if( q->nElem )
			{
				int nCount = q->nElem;
				ElementPtr *pFrom = q->pData + nCount,
									*pTo = pFrom+1;
				while( nCount-- )
					++( *--pTo = *--pFrom )->nOffset;
			}
			q->nStart--;
			q->nEnd--;
		}
		else
		{
			// Wenn er auch nicht in den Folgeblock passt, muss ein
			// neuer Block eingefuegt werden
			// erst mal bei Bedarf komprimieren

			// wenn mehr als 50% "Luft" im Array ist, dann sollte man mal das
			// Compress aufrufen
			if( /*nBlock == nMaxBlock &&*/
				nBlock > ( nSize / ( MAXENTRY / 2 ) ) &&
				cur >= Compress() )
			{
				// es wurde vor der akt. Pos etwas verschoben und alle
				// Pointer koennen ungueltig sein. Also das Insert
				// nochmals aufsetzen
				Insert( rElem, pos );
				return ;
			}

			q = InsBlock( cur+1 );
		}

		// Eintrag passt nicht mehr. Dann muss Platz gemacht werden
		ElementPtr pLast = p->pData[ MAXENTRY-1 ];
		pLast->nOffset = 0;
		pLast->pBlock = q;

		q->pData[ 0 ] = pLast;
		q->nElem++;
		q->nEnd++;

		p->nEnd--;
		p->nElem--;
	}
	// Nun haben wir einen freien Block am Wickel: eintragen
	pos -= p->nStart;
	DBG_ASSERT( pos < MAXENTRY, "falsche Pos" );
	if( pos != p->nElem )
	{
		int nCount = p->nElem - sal_uInt16(pos);
		ElementPtr *pFrom = p->pData + p->nElem,
							*pTo = pFrom + 1;
		while( nCount-- )
			++( *--pTo = *--pFrom )->nOffset;
	}
	// Element eintragen und Indexe updaten
	((ElementPtr&)rElem)->nOffset = sal_uInt16(pos);
	((ElementPtr&)rElem)->pBlock = p;
	p->pData[ pos ] = rElem;
	p->nEnd++;
	p->nElem++;
	nSize++;
	if( cur != ( nBlock - 1 ) ) UpdIndex( cur );
	nCur = cur;

	CHECKIDX( ppInf, nBlock, nSize, nCur );
}

void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
{
	CHECKIDX( ppInf, nBlock, nSize, nCur );

	sal_uInt16 nBlkdel = 0;					// entfernte Bloecke
	sal_uInt16 cur = Index2Block( pos );	// aktuelle Blocknr
	sal_uInt16 nBlk1 = cur;                 // 1. behandelter Block
	sal_uInt16 nBlk1del = USHRT_MAX;		// 1. entfernter Block
	BlockInfo* p = ppInf[ cur ];
	pos -= p->nStart;
	sal_uLong nElem = n;
	while( nElem )
	{
		sal_uInt16 nel = p->nElem - sal_uInt16(pos);
		if( sal_uLong(nel) > nElem )
			nel = sal_uInt16(nElem);
		// Eventuell Elemente verschieben
		if( ( pos + nel ) < sal_uLong(p->nElem) )
		{
			ElementPtr *pTo = p->pData + pos,
								*pFrom = pTo + nel;
			int nCount = p->nElem - nel - sal_uInt16(pos);
			while( nCount-- )
			{
                *pTo = *pFrom++;
                (*pTo)->nOffset = (*pTo)->nOffset - nel;
                ++pTo;
			}
		}
		p->nEnd -= nel;
		p->nElem = p->nElem - nel;
		if( !p->nElem )
		{
			// eventuell Block ganz entfernen
			delete[] p->pData;
			nBlkdel++;
			if( USHRT_MAX == nBlk1del )
				nBlk1del = cur;
		}
		nElem -= nel;
		if( !nElem )
			break;
		p = ppInf[ ++cur ];
		pos = 0;
	}
	// Am Ende die Tabelle updaten, falls Bloecke geloescht waren
	if( nBlkdel )
	{
		// loeschen sollte man immer !!
		for( sal_uInt16 i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
			delete ppInf[ i ];

		if( ( nBlk1del + nBlkdel ) < nBlock )
		{
			memmove( ppInf + nBlk1del, ppInf + nBlk1del + nBlkdel,
					 ( nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );

			// JP 19.07.95: nicht den ersten behandelten, sondern den davor!!
			//				UpdateIdx updatet nur alle Nachfolgende!!
			if( !nBlk1 )
			{
				p = ppInf[ 0 ];
				p->nStart = 0;
				p->nEnd = p->nElem-1;
			}
			else
				--nBlk1;
		}
		BlockDel( nBlkdel );			// es wurden Bloecke geloescht
	}

	nSize -= n;
	if( nBlk1 != ( nBlock - 1 ) && nSize )
		UpdIndex( nBlk1 );
	nCur = nBlk1;

	// wenn mehr als 50% "Luft" im Array ist, dann sollte man mal das
	// Compress aufrufen
	if( nBlock > ( nSize / ( MAXENTRY / 2 ) ) )
		Compress();

	CHECKIDX( ppInf, nBlock, nSize, nCur );
}


void BigPtrArray::Replace( sal_uLong idx, const ElementPtr& rElem)
{
	// weil die Funktion eben doch nicht const ist:
	DBG_ASSERT( idx < nSize, "Set: Index aussserhalb" );
	BigPtrArray* pThis = (BigPtrArray*) this;
	sal_uInt16 cur = Index2Block( idx );
	BlockInfo* p = ppInf[ cur ];
	pThis->nCur = cur;
	((ElementPtr&)rElem)->nOffset = sal_uInt16(idx - p->nStart);
	((ElementPtr&)rElem)->pBlock = p;
	p->pData[ idx - p->nStart ] = rElem;
}


// Array komprimieren

sal_uInt16 BigPtrArray::Compress( short nMax )
{
	CHECKIDX( ppInf, nBlock, nSize, nCur );

	// Es wird von vorne nach hinten ueber das InfoBlock Array iteriert.
	// Wenn zwischen durch Block gel�scht werden, dann mussen alle
	// nachfolgenden verschoben werden. Dazu werden die Pointer pp und qq
	// benutzt; wobei pp das "alte" Array, qq das "neue" Array ist.
	BlockInfo** pp = ppInf, **qq = pp;
	BlockInfo* p;
	BlockInfo* pLast(0);				// letzter nicht voller Block
	sal_uInt16 nLast = 0;					// fehlende Elemente
	sal_uInt16 nBlkdel = 0;					// Anzahl der geloeschte Bloecke
	sal_uInt16 nFirstChgPos = USHRT_MAX;	// ab welcher Pos gab es die 1. Aenderung?

	// von Fuell-Prozenten auf uebrige Eintrage umrechnen
	nMax = MAXENTRY - (long) MAXENTRY * nMax / 100;

	for( sal_uInt16 cur = 0; cur < nBlock; ++cur )
	{
		p = *pp++;
		sal_uInt16 n = p->nElem;
		// Testen, ob der noch nicht volle Block so gelassen wird
		// dies ist der Fall, wenn der aktuelle Block gesplittet
		// werden muesste, der noch nicht volle Block aber bereits
		// ueber dem uebergebenen Break-Wert voll ist. In diesem
		// Fall wird von einer weiteren Fuellung (die ja wegen dem
		// zweifachen memmove() zeitaufwendig ist) abgesehen.
		if( nLast && ( n > nLast ) && ( nLast < nMax ) )
			nLast = 0;
		if( nLast )
		{
			if( USHRT_MAX == nFirstChgPos )
				nFirstChgPos = cur;

			// ein nicht voller Block vorhanden: auffuellen
			if( n > nLast )
				n = nLast;

			// Elemente uebertragen, vom akt. in den letzten
			ElementPtr* pElem = pLast->pData + pLast->nElem;
			ElementPtr* pFrom = p->pData;
			for( sal_uInt16 nCount = n, nOff = pLast->nElem;
							nCount; --nCount, ++pElem )
				*pElem = *pFrom++,
					(*pElem)->pBlock = pLast,
					(*pElem)->nOffset = nOff++;

			// korrigieren
			pLast->nElem = pLast->nElem + n;
			nLast = nLast - n;
			p->nElem = p->nElem - n;

			// Ist der aktuelle Block dadurch leer geworden?
			if( !p->nElem )
			{
				// dann kann der entfernt werden
				delete[] p->pData;
				delete   p, p = 0;
				++nBlkdel;
			}
			else
			{
				pElem = p->pData, pFrom = pElem + n;
				int nCount = p->nElem;
				while( nCount-- )
				{
					*pElem = *pFrom++;
					(*pElem)->nOffset = (*pElem)->nOffset - n;
					++pElem;
				}
			}
		}

		if( p )		// die Blockinfo wurde nicht geloescht
		{
			*qq++ = p;		// dann setze sie an die richtige neue Position

			// eventuell den letzten halbvollen Block festhalten
			if( !nLast && p->nElem < MAXENTRY )
			{
				pLast = p;
				nLast = MAXENTRY - p->nElem;
			}
		}
	}

	// Bloecke geloescht wurden, ggfs. das BlockInfo Array verkuerzen
	if( nBlkdel )
		BlockDel( nBlkdel );

	// Und neu durchindizieren
	p = ppInf[ 0 ];
	p->nEnd = p->nElem - 1;
	UpdIndex( 0 );

	if( nCur >= nFirstChgPos )
		nCur = 0;

	CHECKIDX( ppInf, nBlock, nSize, nCur );

	return nFirstChgPos;
}