In the free list, we don't strictly speaking need to have every block
in a coalesced group point to the head block, although this is an
invariant for non-free blocks. Dropping this invariant for the free
list means that coalesce() is O(1) rather than O(N), and freeGroup()
is therefore O(N) not O(N^2).
The bad case probably didn't happen most of the time, indeed it has
never shown up in a profile that I've seen. I had a report from a
while back that this was a problem with really large heaps, though.
Fortunately the fix is easy.
for (bd = free_list; bd != NULL; bd = bd->link) {
if (bd->blocks == n) { /* exactly the right size! */
*last = bd->link;
for (bd = free_list; bd != NULL; bd = bd->link) {
if (bd->blocks == n) { /* exactly the right size! */
*last = bd->link;
- /* no initialisation necessary - this is already a
- * self-contained block group. */
- bd->free = bd->start; /* block isn't free now */
- bd->link = NULL;
+ initGroup(n, bd); /* initialise it */
return bd;
}
if (bd->blocks > n) { /* block too big... */
return bd;
}
if (bd->blocks > n) { /* block too big... */
STATIC_INLINE bdescr *
coalesce(bdescr *p)
{
STATIC_INLINE bdescr *
coalesce(bdescr *p)
{
- bdescr *bd, *q;
- nat i, blocks;
q = p->link;
if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
/* can coalesce */
p->blocks += q->blocks;
p->link = q->link;
q = p->link;
if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
/* can coalesce */
p->blocks += q->blocks;
p->link = q->link;
- blocks = q->blocks;
- for (i = 0, bd = q; i < blocks; bd++, i++) {
- bd->free = 0;
- bd->blocks = 0;
- bd->link = p;
+#ifdef DEBUG
+ {
+ nat i, blocks;
+ bdescr *bd;
+ // not strictly necessary to do this, but helpful if we have a
+ // random ptr and want to figure out what block it belongs to.
+ for (i = 0, bd = q; i < q->blocks; bd++, i++) {
+ bd->free = 0;
+ bd->blocks = 0;
+ bd->link = p;
+ }