Tesseract: MEMBLOCK Class Reference

MEMUNION * MEMBLOCK::find_chunk ( INT32 count )

Find a chunk within the block which is big enough for the given request.

Definition at line 778 of file memblk.cpp.

References blockend, blockstart, freechunk, lowerspace, MEMUNION::size, topchunk, and upperspace.

00780                                 {
00781   MEMUNION *chunk;               //current chunk
00782   INT32 chunksize;               //size of free chunk
00783   MEMUNION *chunkstart;          //start of free chunk
00784   INT32 spaceshift;              //shift in lowerspace
00785 
00786   if (upperspace <= lowerspace) {
00787     freechunk = blockstart;      //restart chunklist
00788     upperspace += lowerspace;
00789     lowerspace = 0;              //correct space counts
00790   }
00791   chunk = freechunk;             //current free chunk
00792   if (chunk->size < count) {     //big enough?
00793     spaceshift = 0;
00794     do {
00795       while (chunk->size < 0) {  //find free chunk
00796         chunk -= chunk->size;    //skip forward
00797         if (chunk == blockend) {
00798           chunk = blockstart;    //restart block
00799                                  //gone back to start
00800           spaceshift = -lowerspace;
00801         }
00802         if (chunk == freechunk)
00803           return chunk;          //gone all round & failed
00804       }
00805       chunkstart = chunk;        //start of chunk
00806       chunksize = chunk->size;;
00807       chunk += chunk->size;
00808       while (chunk != blockend   //until end
00809       && chunk->size > 0) {      //or used
00810         chunksize += chunk->size;//coalesce free blocks
00811                                  //gone all round
00812         if (chunk == freechunk) {
00813                                  //ensure it is at end
00814           freechunk += chunk->size;
00815           upperspace -= chunk->size;
00816           lowerspace += chunk->size;
00817           spaceshift -= chunk->size;
00818         }
00819         if (chunk == topchunk)   //got back to end one
00820           topchunk = chunkstart; //end one bigger
00821         chunk += chunk->size;    //get next block
00822       }
00823                                  //new big block
00824       chunkstart->size = chunksize;
00825       if (chunksize < count)
00826         spaceshift += chunksize; //skipping free block
00827       if (chunk == blockend) {
00828         chunk = blockstart;      //back to start
00829         if (freechunk == blockend) {
00830           freechunk = blockstart;//so is freechunk
00831           upperspace += lowerspace;
00832           lowerspace = 0;
00833           spaceshift = 0;
00834         }
00835         else
00836                                  //so is shift
00837             spaceshift = -lowerspace;
00838       }
00839     }
00840     while (chunksize < count && chunk != freechunk);
00841     if (chunksize < count)
00842       return chunk;              //failed
00843     lowerspace += spaceshift;    //get space counts right
00844     upperspace -= spaceshift;
00845     freechunk = chunkstart;
00846     return chunkstart;           //success
00847   }
00848   return chunk;                  //easy
00849 }