- if (rover == start) // scaned all the way around the list
- return NULL;
- if (rover->tag)
- base = rover = rover->next;
- else
- rover = rover->next;
- } while (base->tag || base->size < size);
-
-//
-// found a block big enough
-//
- extra = base->size - size;
- if (extra > MINFRAGMENT)
- { // there will be a free fragment after the allocated block
- new = (memblock_t *) ((byte *)base + size );
- new->size = extra;
- new->tag = 0; // free block
- new->prev = base;
- new->id = ZONEID;
- new->next = base->next;
- new->next->prev = new;
- base->next = new;
- base->size = size;
+ int index;
+ unsigned int bit;
+ unsigned int needbits;
+ unsigned int startbit;
+ unsigned int endbit;
+ unsigned int needints;
+ int startindex;
+ int endindex;
+ unsigned int value;
+ unsigned int mask;
+ unsigned int *array;
+ memclump_t **clumpchainpointer;
+ memclump_t *clump;
+ needbits = (size + MEMUNIT - 1) / MEMUNIT;
+ needints = (needbits+31)>>5;
+ for (clumpchainpointer = &clumpchain;;clumpchainpointer = &(*clumpchainpointer)->chain)
+ {
+ clump = *clumpchainpointer;
+ if (!clump)
+ {
+ clump = Clump_NewClump();
+ if (!clump)
+ return NULL;
+ }
+ if (clump->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel1))
+ Sys_Error("Clump_AllocBlock: trashed sentinel1\n");
+ if (clump->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel2))
+ Sys_Error("Clump_AllocBlock: trashed sentinel2\n");
+ startbit = 0;
+ endbit = startbit + needbits;
+ array = clump->bits;
+ // do as fast a search as possible, even if it means crude alignment
+ if (needbits >= 32)
+ {
+ // large allocations are aligned to large boundaries
+ // furthermore, they are allocated downward from the top...
+ endindex = MEMBITINTS;
+ startindex = endindex - needints;
+ index = endindex;
+ while (--index >= startindex)
+ {
+ if (array[index])
+ {
+ endindex = index;
+ startindex = endindex - needints;
+ if (startindex < 0)
+ goto nofreeblock;
+ }
+ }
+ startbit = startindex*32;
+ goto foundblock;
+ }
+ else
+ {
+ // search for a multi-bit gap in a single int
+ // (not dealing with the cases that cross two ints)
+ mask = (1<<needbits)-1;
+ endbit = 32-needbits;
+ bit = endbit;
+ for (index = 0;index < MEMBITINTS;index++)
+ {
+ value = array[index];
+ if (value != 0xFFFFFFFFu)
+ {
+ // there may be room in this one...
+ for (bit = 0;bit < endbit;bit++)
+ {
+ if (!(value & (mask<<bit)))
+ {
+ startbit = index*32+bit;
+ goto foundblock;
+ }
+ }
+ }
+ }
+ goto nofreeblock;
+ }
+foundblock:
+ endbit = startbit + needbits;
+ // mark this range as used
+ // TODO: optimize
+ for (bit = startbit;bit < endbit;bit++)
+ if (clump->bits[bit>>5] & (1<<(bit & 31)))
+ Sys_Error("Clump_AllocBlock: internal error (%i needbits)\n", needbits);
+ for (bit = startbit;bit < endbit;bit++)
+ clump->bits[bit>>5] |= (1<<(bit & 31));
+ clump->blocksinuse += needbits;
+ base = clump->block + startbit * MEMUNIT;
+ if (developer_memorydebug.integer)
+ memset(base, 0xBF, needbits * MEMUNIT);
+ return base;
+nofreeblock:
+ ;
+ }
+ // never reached
+ return NULL;