Subversion Repositories Kolibri OS

// Emacs style mode select   -*- C++ -*-

//-----------------------------------------------------------------------------

//

// $Id: z_zone.c,v 1.2 1997/12/29 19:51:30 pekangas Exp $

//

// Copyright (C) 1993-1996 by id Software, Inc.

//

// This source is available for distribution and/or modification

// only under the terms of the DOOM Source Code License as

// published by id Software. All rights reserved.

//

// The source is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License

// for more details.

//

// $Log: z_zone.c,v $

// Revision 1.2  1997/12/29 19:51:30  pekangas

// Ported to WinNT/95 environment using Watcom C 10.6.

// Everything expect joystick support is implemented, but networking is

// untested. Crashes way too often with problems in FixedDiv().

// Compiles with no warnings at warning level 3, uses MIDAS 1.1.1.

//

// Revision 1.1.1.1  1997/12/28 12:59:07  pekangas

// Initial DOOM source release from id Software

//

//

// DESCRIPTION:

//	Zone Memory Allocation. Neat.

//

//-----------------------------------------------------------------------------

const char

z_zone_rcsid[] = "$Id: z_zone.c,v 1.2 1997/12/29 19:51:30 pekangas Exp $";

#include "z_zone.h"

#include "i_system.h"

#include "doomdef.h"

//

// ZONE MEMORY ALLOCATION

//

// There is never any space between memblocks,

//  and there will never be two contiguous free memblocks.

// The rover can be left pointing at a non-empty block.

//

// It is of no value to free a cachable block,

//  because it will get overwritten automatically if needed.

//

#define ZONEID	0x1d4a11

typedef struct

{

    // total bytes malloced, including header

    int		size;

    // start / end cap for linked list

    memblock_t	blocklist;

    memblock_t*	rover;

} memzone_t;

memzone_t*	mainzone;

//

// Z_ClearZone

//

void Z_ClearZone (memzone_t* zone)

{

    memblock_t*		block;

    // set the entire zone to one free block

    zone->blocklist.next =

	zone->blocklist.prev =

	block = (memblock_t *)( (byte *)zone + sizeof(memzone_t) );

    zone->blocklist.user = (void *)zone;

    zone->blocklist.tag = PU_STATIC;

    zone->rover = block;

    block->prev = block->next = &zone->blocklist;

    // NULL indicates a free block.

    block->user = NULL;

    block->size = zone->size - sizeof(memzone_t);

}

//

// Z_Init

//

void Z_Init (void)

{

    memblock_t*	block;

    int		size;

    mainzone = (memzone_t *)I_ZoneBase (&size);

    mainzone->size = size;

    // set the entire zone to one free block

    mainzone->blocklist.next =

	mainzone->blocklist.prev =

	block = (memblock_t *)( (byte *)mainzone + sizeof(memzone_t) );

    mainzone->blocklist.user = (void *)mainzone;

    mainzone->blocklist.tag = PU_STATIC;

    mainzone->rover = block;

    block->prev = block->next = &mainzone->blocklist;

    // NULL indicates a free block.

    block->user = NULL;

    block->size = mainzone->size - sizeof(memzone_t);

}

//

// Z_Free

//

void Z_Free (void* ptr)

{

    memblock_t*		block;

    memblock_t*		other;

    block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));

    if (block->id != ZONEID)

	I_Error ("Z_Free: freed a pointer without ZONEID");

    if (block->user > (void **)0x100)

    {

	// smaller values are not pointers

	// Note: OS-dependend?

	// clear the user's mark

	*block->user = 0;

    }

    // mark as free

    block->user = NULL;

    block->tag = 0;

    block->id = 0;

    other = block->prev;

    if (!other->user)

    {

	// merge with previous free block

	other->size += block->size;

	other->next = block->next;

	other->next->prev = other;

	if (block == mainzone->rover)

	    mainzone->rover = other;

	block = other;

    }

    other = block->next;

    if (!other->user)

    {

	// merge the next free block onto the end

	block->size += other->size;

	block->next = other->next;

	block->next->prev = block;

	if (other == mainzone->rover)

	    mainzone->rover = block;

    }

}

//

// Z_Malloc

// You can pass a NULL user if the tag is < PU_PURGELEVEL.

//

#define MINFRAGMENT		64

void*

Z_Malloc

( int		size,

  int		tag,

  void*		user )

{

    int		extra;

    memblock_t*	start;

    memblock_t* rover;

    memblock_t* newblock;

    memblock_t*	base;

    size = (size + 3) & ~3;

    // scan through the block list,

    // looking for the first free block

    // of sufficient size,

    // throwing out any purgable blocks along the way.

    // account for size of block header

    size += sizeof(memblock_t);

    // if there is a free block behind the rover,

    //  back up over them

    base = mainzone->rover;

    if (!base->prev->user)

	base = base->prev;

    rover = base;

    start = base->prev;

    do

    {

	if (rover == start)

	{

	    // scanned all the way around the list

	    I_Error ("Z_Malloc: failed on allocation of %i bytes", size);

	}

	if (rover->user)

	{

	    if (rover->tag < PU_PURGELEVEL)

	    {

		// hit a block that can't be purged,

		//  so move base past it

		base = rover = rover->next;

	    }

	    else

	    {

		// free the rover block (adding the size to base)

		// the rover can be the base block

		base = base->prev;

		Z_Free ((byte *)rover+sizeof(memblock_t));

		base = base->next;

		rover = base->next;

	    }

	}

	else

	    rover = rover->next;

    } while (base->user || 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

	newblock = (memblock_t *) ((byte *)base + size );

	newblock->size = extra;

	// NULL indicates free block.

	newblock->user = NULL;

	newblock->tag = 0;

	newblock->prev = base;

	newblock->next = base->next;

	newblock->next->prev = newblock;

	base->next = newblock;

	base->size = size;

    }

    if (user)

    {

	// mark as an in use block

	base->user = user;

	*(void **)user = (void *) ((byte *)base + sizeof(memblock_t));

    }

    else

    {

	if (tag >= PU_PURGELEVEL)

	    I_Error ("Z_Malloc: an owner is required for purgable blocks");

	// mark as in use, but unowned

	base->user = (void *)2;

    }

    base->tag = tag;

    // next allocation will start looking here

    mainzone->rover = base->next;

    base->id = ZONEID;

    return (void *) ((byte *)base + sizeof(memblock_t));

}

//

// Z_FreeTags

//

void

Z_FreeTags

( int		lowtag,

  int		hightag )

{

    memblock_t*	block;

    memblock_t*	next;

    for (block = mainzone->blocklist.next ;

	 block != &mainzone->blocklist ;

	 block = next)

    {

	// get link before freeing

	next = block->next;

	// free block?

	if (!block->user)

	    continue;

	if (block->tag >= lowtag && block->tag <= hightag)

	    Z_Free ( (byte *)block+sizeof(memblock_t));

    }

}

//

// Z_DumpHeap

// Note: TFileDumpHeap( stdout ) ?

//

void

Z_DumpHeap

( int		lowtag,

  int		hightag )

{

    memblock_t*	block;

    printf ("zone size: %i  location: %p\n",

	    mainzone->size,mainzone);

    printf ("tag range: %i to %i\n",

	    lowtag, hightag);

    for (block = mainzone->blocklist.next ; ; block = block->next)

    {

	if (block->tag >= lowtag && block->tag <= hightag)

	    printf ("block:%p    size:%7i    user:%p    tag:%3i\n",

		    block, block->size, block->user, block->tag);

	if (block->next == &mainzone->blocklist)

	{

	    // all blocks have been hit

	    break;

	}

	if ( (byte *)block + block->size != (byte *)block->next)

	    printf ("ERROR: block size does not touch the next block\n");

	if ( block->next->prev != block)

	    printf ("ERROR: next block doesn't have proper back link\n");

	if (!block->user && !block->next->user)

	    printf ("ERROR: two consecutive free blocks\n");

    }

}

//

// Z_FileDumpHeap

//

void Z_FileDumpHeap (FILE* f)

{

    memblock_t*	block;

    fprintf (f,"zone size: %i  location: %p\n",mainzone->size,mainzone);

    for (block = mainzone->blocklist.next ; ; block = block->next)

    {

	fprintf (f,"block:%p    size:%7i    user:%p    tag:%3i\n",

		 block, block->size, block->user, block->tag);

	if (block->next == &mainzone->blocklist)

	{

	    // all blocks have been hit

	    break;

	}

	if ( (byte *)block + block->size != (byte *)block->next)

	    fprintf (f,"ERROR: block size does not touch the next block\n");

	if ( block->next->prev != block)

	    fprintf (f,"ERROR: next block doesn't have proper back link\n");

	if (!block->user && !block->next->user)

	    fprintf (f,"ERROR: two consecutive free blocks\n");

    }

}

//

// Z_CheckHeap

//

void Z_CheckHeap (void)

{

    memblock_t*	block;

    for (block = mainzone->blocklist.next ; ; block = block->next)

    {

	if (block->next == &mainzone->blocklist)

	{

	    // all blocks have been hit

	    break;

	}

	if ( (byte *)block + block->size != (byte *)block->next)

	    I_Error ("Z_CheckHeap: block size does not touch the next block\n");

	if ( block->next->prev != block)

	    I_Error ("Z_CheckHeap: next block doesn't have proper back link\n");

	if (!block->user && !block->next->user)

	    I_Error ("Z_CheckHeap: two consecutive free blocks\n");

    }

}

//

// Z_ChangeTag

//

void

Z_ChangeTag2

( void*		ptr,

  int		tag )

{

    memblock_t*	block;

    block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));

    if (block->id != ZONEID)

	I_Error ("Z_ChangeTag: freed a pointer without ZONEID");

    if (tag >= PU_PURGELEVEL && (unsigned)block->user < 0x100)

	I_Error ("Z_ChangeTag: an owner is required for purgable blocks");

    block->tag = tag;

}

//

// Z_FreeMemory

//

int Z_FreeMemory (void)

{

    memblock_t*		block;

    int			free;

    free = 0;

    for (block = mainzone->blocklist.next ;

	 block != &mainzone->blocklist;

	 block = block->next)

    {

	if (!block->user || block->tag >= PU_PURGELEVEL)

	    free += block->size;

    }

    return free;

}