sw/source/core/bastyp/bparr.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: bparr.cxx,v $
  10  * $Revision: 1.11 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_sw.hxx"
  33
  34
  35
  36 #include <string.h>
  37 #include <limits.h>
  38 #include "bparr.hxx"
  39
  40 // die Blockverwaltung waechst/schrumpft immer um 20 Bloecke, das sind dann
  41 // immer ~ 20 * MAXENTRY == 20000 Eintraege
  42 const USHORT nBlockGrowSize = 20;
  43
  44 #ifdef PRODUCT
  45
  46 #define CHECKIDX( p, n, i, c )
  47
  48 #else
  49
  50 #define CHECKIDX( p, n, i, c ) CheckIdx( p, n, i, c );
  51
  52 void CheckIdx( BlockInfo** ppInf, USHORT nBlock, ULONG nSize, USHORT nCur )
  53 {
  54     DBG_ASSERT( !nSize || nCur < nBlock, "BigPtrArray: CurIndex steht falsch" );
  55
  56     ULONG nIdx = 0;
  57     for( USHORT nCnt = 0; nCnt < nBlock; ++nCnt, ++ppInf )
  58     {
  59         nIdx += (*ppInf)->nElem;
  60         // Array mit Luecken darf es nicht geben
  61         DBG_ASSERT( !nCnt || (*(ppInf-1))->nEnd + 1 == (*ppInf)->nStart,
  62                     "BigPtrArray: Luecke in der Verwaltung!" );
  63     }
  64
  65     DBG_ASSERT( nIdx == nSize, "BigPtrArray: Anzahl ungueltig" );
  66 }
  67
  68 #endif
  69
  70
  71 BigPtrArray::BigPtrArray()
  72 {
  73     nBlock = nCur = 0;
  74     nSize = 0;
  75     nMaxBlock = nBlockGrowSize;         // == 20 * 1000 Eintraege
  76     ppInf = new BlockInfo* [ nMaxBlock ];
  77 }
  78
  79
  80
  81 BigPtrArray::~BigPtrArray()
  82 {
  83     if( nBlock )
  84     {
  85         BlockInfo** pp = ppInf;
  86         for( USHORT n = 0; n < nBlock; ++n, ++pp )
  87         {
  88             delete[] (*pp)->pData;
  89             delete    *pp;
  90         }
  91     }
  92     delete[] ppInf;
  93 }
  94
  95 // Auch der Move ist schlicht. Optimieren ist hier wg. der
  96 // Stueckelung des Feldes zwecklos!
  97
  98 void BigPtrArray::Move( ULONG from, ULONG to )
  99 {
 100     USHORT cur = Index2Block( from );
 101     BlockInfo* p = ppInf[ cur ];
 102     ElementPtr pElem = p->pData[ from - p->nStart ];
 103     Insert( pElem, to );                        // erst einfuegen, dann loeschen !!!!
 104     Remove( ( to < from ) ? ( from + 1 ) : from );
 105 }
 106
 107 // das Ende ist EXCLUSIV
 108
 109
 110 void BigPtrArray::ForEach( ULONG nStart, ULONG nEnd,
 111                             FnForEach fn, void* pArgs )
 112 {
 113     if( nEnd > nSize )
 114         nEnd = nSize;
 115
 116     if( nStart < nEnd )
 117     {
 118         USHORT cur = Index2Block( nStart );
 119         BlockInfo** pp = ppInf + cur;
 120         BlockInfo* p = *pp;
 121         USHORT nElem = USHORT( nStart - p->nStart );
 122         ElementPtr* pElem = p->pData + nElem;
 123         nElem = p->nElem - nElem;
 124         for(;;)
 125         {
 126             if( !(*fn)( *pElem++, pArgs ) || ++nStart >= nEnd )
 127                 break;
 128
 129             // naechstes Element
 130             if( !--nElem )
 131             {
 132                 // neuer Block
 133                 p = *++pp;
 134                 pElem = p->pData;
 135                 nElem = p->nElem;
 136             }
 137         }
 138     }
 139 }
 140
 141
 142 ElementPtr BigPtrArray::operator[]( ULONG idx ) const
 143 {
 144     // weil die Funktion eben doch nicht const ist:
 145     DBG_ASSERT( idx < nSize, "operator[]: Index aussserhalb" );
 146     BigPtrArray* pThis = (BigPtrArray*) this;
 147     USHORT cur = Index2Block( idx );
 148     BlockInfo* p = ppInf[ cur ];
 149     pThis->nCur = cur;
 150     return p->pData[ idx - p->nStart ];
 151 }
 152
 153 ///////////////////////////////////////////////////////////////////////////
 154
 155 // private Methoden
 156
 157 // Suchen des Blocks einer bestimmten Position
 158 // Algorithmus:
 159 // 1. Test, ob der letzte Block der gesuchte Block ist
 160 // 2. Sonderfall: Index = 0?
 161 // 3. Test der Nachbarbloecke
 162
 163 // 4. Binaere Suche
 164
 165
 166
 167 USHORT BigPtrArray::Index2Block( ULONG pos ) const
 168 {
 169     // zuletzt verwendeter Block?
 170     BlockInfo* p = ppInf[ nCur ];
 171     if( p->nStart <= pos && p->nEnd >= pos )
 172         return nCur;
 173     // Index = 0?
 174     if( !pos )
 175         return 0;
 176     // Folgeblock?
 177     if( nCur < ( nBlock - 1 ) )
 178     {
 179         p = ppInf[ nCur+1 ];
 180         if( p->nStart <= pos && p->nEnd >= pos )
 181             return nCur+1;
 182     }
 183     // vorangehender Block?
 184     else if( pos < p->nStart && nCur > 0 )
 185     {
 186         p = ppInf[ nCur-1 ];
 187         if( p->nStart <= pos && p->nEnd >= pos )
 188             return nCur-1;
 189     }
 190     // Binaere Suche:
 191     // Diese fuehrt immer zum Erfolg
 192     USHORT lower = 0, upper = nBlock - 1;
 193     USHORT cur = 0;
 194     for(;;)
 195     {
 196         USHORT n = lower + ( upper - lower ) / 2;
 197         cur = ( n == cur ) ? n+1 : n;
 198         p = ppInf[ cur ];
 199         if( p->nStart <= pos && p->nEnd >= pos )
 200             return cur;
 201         if( p->nStart > pos )
 202             upper = cur;
 203         else
 204             lower = cur;
 205     }
 206 }
 207
 208
 209 // Update aller Indexbereiche ab einer bestimmten Position
 210
 211 // pos bezeichnet den letzten korrekten Block
 212
 213 void BigPtrArray::UpdIndex( USHORT pos )
 214 {
 215     BlockInfo** pp = ppInf + pos;
 216     ULONG idx = (*pp)->nEnd + 1;
 217     BlockInfo* p;
 218     while( ++pos < nBlock )
 219     {
 220         p = *++pp;
 221         p->nStart = idx;
 222         idx       += p->nElem;
 223         p->nEnd   = idx - 1;
 224     }
 225 }
 226
 227 // Einrichten eines neuen Blocks an einer bestimmten Position
 228
 229 // Vorhandene Blocks werden nach hinten verschoben
 230
 231
 232
 233 BlockInfo* BigPtrArray::InsBlock( USHORT pos )
 234 {
 235     if( nBlock == nMaxBlock )
 236     {
 237         // dann sollte wir mal das Array erweitern
 238         BlockInfo** ppNew = new BlockInfo* [ nMaxBlock + nBlockGrowSize ];
 239         memcpy( ppNew, ppInf, nMaxBlock * sizeof( BlockInfo* ));
 240         delete[] ppInf;
 241         nMaxBlock += nBlockGrowSize;
 242         ppInf = ppNew;
 243     }
 244     if( pos != nBlock )
 245         memmove( ppInf + pos+1, ppInf + pos ,
 246                  ( nBlock - pos ) * sizeof (BlockInfo*) );
 247     ++nBlock;
 248     BlockInfo* p = new BlockInfo;
 249     ppInf[ pos ] = p;
 250
 251     if( pos )
 252         p->nStart = p->nEnd = ppInf[ pos-1 ]->nEnd + 1;
 253     else
 254         p->nStart = p->nEnd = 0;
 255     p->nEnd--;  // keine Elemente
 256     p->nElem = 0;
 257     p->pData = new ElementPtr [ MAXENTRY ];
 258     p->pBigArr = this;
 259     return p;
 260 }
 261
 262 void BigPtrArray::BlockDel( USHORT nDel )
 263 {
 264     nBlock = nBlock - nDel;
 265     if( nMaxBlock - nBlock > nBlockGrowSize )
 266     {
 267         // dann koennen wir wieder schrumpfen
 268         nDel = (( nBlock / nBlockGrowSize ) + 1 ) * nBlockGrowSize;
 269         BlockInfo** ppNew = new BlockInfo* [ nDel ];
 270         memcpy( ppNew, ppInf, nBlock * sizeof( BlockInfo* ));
 271         delete[] ppInf;
 272         ppInf = ppNew;
 273         nMaxBlock = nDel;
 274     }
 275 }
 276
 277
 278 void BigPtrArray::Insert( const ElementPtr& rElem, ULONG pos )
 279 {
 280     CHECKIDX( ppInf, nBlock, nSize, nCur );
 281
 282     BlockInfo* p;
 283     USHORT cur;
 284     if( !nSize )
 285         // Sonderfall: erstes Element einfuegen
 286         p = InsBlock( cur = 0 );
 287     else if( pos == nSize )
 288     {
 289         // Sonderfall: Einfuegen am Ende
 290         cur = nBlock - 1;
 291         p = ppInf[ cur ];
 292         if( p->nElem == MAXENTRY )
 293             // Der letzte Block ist voll, neuen anlegen
 294             p = InsBlock( ++cur );
 295     }
 296     else
 297     {
 298         // Standardfall:
 299         cur = Index2Block( pos );
 300         p = ppInf[ cur ];
 301     }
 302     if( p->nElem == MAXENTRY )
 303     {
 304         // passt der letzte Eintrag in den naechsten Block?
 305         BlockInfo* q;
 306         if( cur < ( nBlock - 1 ) && ppInf[ cur+1 ]->nElem < MAXENTRY )
 307         {
 308             q = ppInf[ cur+1 ];
 309             if( q->nElem )
 310             {
 311                 int nCount = q->nElem;
 312                 ElementPtr *pFrom = q->pData + nCount,
 313                                     *pTo = pFrom+1;
 314                 while( nCount-- )
 315                     ++( *--pTo = *--pFrom )->nOffset;
 316             }
 317             q->nStart--;
 318             q->nEnd--;
 319         }
 320         else
 321         {
 322             // Wenn er auch nicht in den Folgeblock passt, muss ein
 323             // neuer Block eingefuegt werden
 324             // erst mal bei Bedarf komprimieren
 325
 326             // wenn mehr als 50% "Luft" im Array ist, dann sollte man mal das
 327             // Compress aufrufen
 328             if( /*nBlock == nMaxBlock &&*/
 329                 nBlock > ( nSize / ( MAXENTRY / 2 ) ) &&
 330                 cur >= Compress() )
 331             {
 332                 // es wurde vor der akt. Pos etwas verschoben und alle
 333                 // Pointer koennen ungueltig sein. Also das Insert
 334                 // nochmals aufsetzen
 335                 Insert( rElem, pos );
 336                 return ;
 337             }
 338
 339             q = InsBlock( cur+1 );
 340         }
 341
 342         // Eintrag passt nicht mehr. Dann muss Platz gemacht werden
 343         ElementPtr pLast = p->pData[ MAXENTRY-1 ];
 344         pLast->nOffset = 0;
 345         pLast->pBlock = q;
 346
 347         q->pData[ 0 ] = pLast;
 348         q->nElem++;
 349         q->nEnd++;
 350
 351         p->nEnd--;
 352         p->nElem--;
 353     }
 354     // Nun haben wir einen freien Block am Wickel: eintragen
 355     pos -= p->nStart;
 356     DBG_ASSERT( pos < MAXENTRY, "falsche Pos" );
 357     if( pos != p->nElem )
 358     {
 359         int nCount = p->nElem - USHORT(pos);
 360         ElementPtr *pFrom = p->pData + p->nElem,
 361                             *pTo = pFrom + 1;
 362         while( nCount-- )
 363             ++( *--pTo = *--pFrom )->nOffset;
 364     }
 365     // Element eintragen und Indexe updaten
 366     ((ElementPtr&)rElem)->nOffset = USHORT(pos);
 367     ((ElementPtr&)rElem)->pBlock = p;
 368     p->pData[ pos ] = rElem;
 369     p->nEnd++;
 370     p->nElem++;
 371     nSize++;
 372     if( cur != ( nBlock - 1 ) ) UpdIndex( cur );
 373     nCur = cur;
 374
 375     CHECKIDX( ppInf, nBlock, nSize, nCur );
 376 }
 377
 378 void BigPtrArray::Remove( ULONG pos, ULONG n )
 379 {
 380     CHECKIDX( ppInf, nBlock, nSize, nCur );
 381
 382     USHORT nBlkdel = 0;                                 // entfernte Bloecke
 383     USHORT cur = Index2Block( pos );    // aktuelle Blocknr
 384     USHORT nBlk1 = cur;                 // 1. behandelter Block
 385     USHORT nBlk1del = USHRT_MAX;                // 1. entfernter Block
 386     BlockInfo* p = ppInf[ cur ];
 387     pos -= p->nStart;
 388     ULONG nElem = n;
 389     while( nElem )
 390     {
 391         USHORT nel = p->nElem - USHORT(pos);
 392         if( ULONG(nel) > nElem )
 393             nel = USHORT(nElem);
 394         // Eventuell Elemente verschieben
 395         if( ( pos + nel ) < ULONG(p->nElem) )
 396         {
 397             ElementPtr *pTo = p->pData + pos,
 398                                 *pFrom = pTo + nel;
 399             int nCount = p->nElem - nel - USHORT(pos);
 400             while( nCount-- )
 401             {
 402                 *pTo = *pFrom++;
 403                 (*pTo)->nOffset = (*pTo)->nOffset - nel;
 404                 ++pTo;
 405             }
 406         }
 407         p->nEnd -= nel;
 408         p->nElem = p->nElem - nel;
 409         if( !p->nElem )
 410         {
 411             // eventuell Block ganz entfernen
 412             delete[] p->pData;
 413             nBlkdel++;
 414             if( USHRT_MAX == nBlk1del )
 415                 nBlk1del = cur;
 416         }
 417         nElem -= nel;
 418         if( !nElem )
 419             break;
 420         p = ppInf[ ++cur ];
 421         pos = 0;
 422     }
 423     // Am Ende die Tabelle updaten, falls Bloecke geloescht waren
 424     if( nBlkdel )
 425     {
 426         // loeschen sollte man immer !!
 427         for( USHORT i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
 428             delete ppInf[ i ];
 429
 430         if( ( nBlk1del + nBlkdel ) < nBlock )
 431         {
 432             memmove( ppInf + nBlk1del, ppInf + nBlk1del + nBlkdel,
 433                      ( nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );
 434
 435             // JP 19.07.95: nicht den ersten behandelten, sondern den davor!!
 436             //                          UpdateIdx updatet nur alle Nachfolgende!!
 437             if( !nBlk1 )
 438             {
 439                 p = ppInf[ 0 ];
 440                 p->nStart = 0;
 441                 p->nEnd = p->nElem-1;
 442             }
 443             else
 444                 --nBlk1;
 445         }
 446         BlockDel( nBlkdel );                    // es wurden Bloecke geloescht
 447     }
 448
 449     nSize -= n;
 450     if( nBlk1 != ( nBlock - 1 ) && nSize )
 451         UpdIndex( nBlk1 );
 452     nCur = nBlk1;
 453
 454     // wenn mehr als 50% "Luft" im Array ist, dann sollte man mal das
 455     // Compress aufrufen
 456     if( nBlock > ( nSize / ( MAXENTRY / 2 ) ) )
 457         Compress();
 458
 459     CHECKIDX( ppInf, nBlock, nSize, nCur );
 460 }
 461
 462
 463 void BigPtrArray::Replace( ULONG idx, const ElementPtr& rElem)
 464 {
 465     // weil die Funktion eben doch nicht const ist:
 466     DBG_ASSERT( idx < nSize, "Set: Index aussserhalb" );
 467     BigPtrArray* pThis = (BigPtrArray*) this;
 468     USHORT cur = Index2Block( idx );
 469     BlockInfo* p = ppInf[ cur ];
 470     pThis->nCur = cur;
 471     ((ElementPtr&)rElem)->nOffset = USHORT(idx - p->nStart);
 472     ((ElementPtr&)rElem)->pBlock = p;
 473     p->pData[ idx - p->nStart ] = rElem;
 474 }
 475
 476
 477 // Array komprimieren
 478
 479 USHORT BigPtrArray::Compress( short nMax )
 480 {
 481     CHECKIDX( ppInf, nBlock, nSize, nCur );
 482
 483     // Es wird von vorne nach hinten ueber das InfoBlock Array iteriert.
 484     // Wenn zwischen durch Block gel�scht werden, dann mussen alle
 485     // nachfolgenden verschoben werden. Dazu werden die Pointer pp und qq
 486     // benutzt; wobei pp das "alte" Array, qq das "neue" Array ist.
 487     BlockInfo** pp = ppInf, **qq = pp;
 488     BlockInfo* p;
 489     BlockInfo* pLast(0);                                // letzter nicht voller Block
 490     USHORT nLast = 0;                                   // fehlende Elemente
 491     USHORT nBlkdel = 0;                                 // Anzahl der geloeschte Bloecke
 492     USHORT nFirstChgPos = USHRT_MAX;    // ab welcher Pos gab es die 1. Aenderung?
 493
 494     // von Fuell-Prozenten auf uebrige Eintrage umrechnen
 495     nMax = MAXENTRY - (long) MAXENTRY * nMax / 100;
 496
 497     for( USHORT cur = 0; cur < nBlock; ++cur )
 498     {
 499         p = *pp++;
 500         USHORT n = p->nElem;
 501         // Testen, ob der noch nicht volle Block so gelassen wird
 502         // dies ist der Fall, wenn der aktuelle Block gesplittet
 503         // werden muesste, der noch nicht volle Block aber bereits
 504         // ueber dem uebergebenen Break-Wert voll ist. In diesem
 505         // Fall wird von einer weiteren Fuellung (die ja wegen dem
 506         // zweifachen memmove() zeitaufwendig ist) abgesehen.
 507         if( nLast && ( n > nLast ) && ( nLast < nMax ) )
 508             nLast = 0;
 509         if( nLast )
 510         {
 511             if( USHRT_MAX == nFirstChgPos )
 512                 nFirstChgPos = cur;
 513
 514             // ein nicht voller Block vorhanden: auffuellen
 515             if( n > nLast )
 516                 n = nLast;
 517
 518             // Elemente uebertragen, vom akt. in den letzten
 519             ElementPtr* pElem = pLast->pData + pLast->nElem;
 520             ElementPtr* pFrom = p->pData;
 521             for( USHORT nCount = n, nOff = pLast->nElem;
 522                             nCount; --nCount, ++pElem )
 523                 *pElem = *pFrom++,
 524                     (*pElem)->pBlock = pLast,
 525                     (*pElem)->nOffset = nOff++;
 526
 527             // korrigieren
 528             pLast->nElem = pLast->nElem + n;
 529             nLast = nLast - n;
 530             p->nElem = p->nElem - n;
 531
 532             // Ist der aktuelle Block dadurch leer geworden?
 533             if( !p->nElem )
 534             {
 535                 // dann kann der entfernt werden
 536                 delete[] p->pData;
 537                 delete   p, p = 0;
 538                 ++nBlkdel;
 539             }
 540             else
 541             {
 542                 pElem = p->pData, pFrom = pElem + n;
 543                 int nCount = p->nElem;
 544                 while( nCount-- )
 545                 {
 546                     *pElem = *pFrom++;
 547                     (*pElem)->nOffset = (*pElem)->nOffset - n;
 548                     ++pElem;
 549                 }
 550             }
 551         }
 552
 553         if( p )         // die Blockinfo wurde nicht geloescht
 554         {
 555             *qq++ = p;          // dann setze sie an die richtige neue Position
 556
 557             // eventuell den letzten halbvollen Block festhalten
 558             if( !nLast && p->nElem < MAXENTRY )
 559             {
 560                 pLast = p;
 561                 nLast = MAXENTRY - p->nElem;
 562             }
 563         }
 564     }
 565
 566     // Bloecke geloescht wurden, ggfs. das BlockInfo Array verkuerzen
 567     if( nBlkdel )
 568         BlockDel( nBlkdel );
 569
 570     // Und neu durchindizieren
 571     p = ppInf[ 0 ];
 572     p->nEnd = p->nElem - 1;
 573     UpdIndex( 0 );
 574
 575     if( nCur >= nFirstChgPos )
 576         nCur = 0;
 577
 578     CHECKIDX( ppInf, nBlock, nSize, nCur );
 579
 580     return nFirstChgPos;
 581 }
 582
 583