diff options
Diffstat (limited to 'apps/plugins/sdl/progs/quake/zone.c')
| -rw-r--r-- | apps/plugins/sdl/progs/quake/zone.c | 935 |
1 files changed, 935 insertions, 0 deletions
diff --git a/apps/plugins/sdl/progs/quake/zone.c b/apps/plugins/sdl/progs/quake/zone.c new file mode 100644 index 0000000..e30d7f8 --- /dev/null +++ b/apps/plugins/sdl/progs/quake/zone.c @@ -0,0 +1,935 @@ +/* +Copyright (C) 1996-1997 Id Software, Inc. + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + +See the GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +*/ +// Z_zone.c + +#include "quakedef.h" + +#define DYNAMIC_SIZE 0xc000 + +#define ZONEID 0x1d4a11 +#define MINFRAGMENT 64 + +typedef struct memblock_s +{ + int size; // including the header and possibly tiny fragments + int tag; // a tag of 0 is a free block + int id; // should be ZONEID + struct memblock_s *next, *prev; + int pad; // pad to 64 bit boundary +} memblock_t; + +typedef struct +{ + int size; // total bytes malloced, including header + memblock_t blocklist; // start / end cap for linked list + memblock_t *rover; +} memzone_t; + +void Cache_FreeLow (int new_low_hunk); +void Cache_FreeHigh (int new_high_hunk); + + +/* +============================================================================== + + 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 + +The zone calls are pretty much only used for small strings and structures, +all big things are allocated on the hunk. +============================================================================== +*/ + +memzone_t *mainzone; + +void Z_ClearZone (memzone_t *zone, int size); + + +/* +======================== +Z_ClearZone +======================== +*/ +void Z_ClearZone (memzone_t *zone, int size) +{ + 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.tag = 1; // in use block + zone->blocklist.id = 0; + zone->blocklist.size = 0; + zone->rover = block; + + block->prev = block->next = &zone->blocklist; + block->tag = 0; // free block + block->id = ZONEID; + block->size = size - sizeof(memzone_t); +} + + +/* +======================== +Z_Free +======================== +*/ +void Z_Free (void *ptr) +{ + memblock_t *block, *other; + + if (!ptr) + Sys_Error ("Z_Free: NULL pointer"); + + block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t)); + if (block->id != ZONEID) + Sys_Error ("Z_Free: freed a pointer without ZONEID"); + if (block->tag == 0) + Sys_Error ("Z_Free: freed a freed pointer"); + + block->tag = 0; // mark as free + + other = block->prev; + if (!other->tag) + { // 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->tag) + { // 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 +======================== +*/ +void *Z_Malloc (int size) +{ + void *buf; + +Z_CheckHeap (); // DEBUG + buf = Z_TagMalloc (size, 1); + if (!buf) + Sys_Error ("Z_Malloc: failed on allocation of %i bytes",size); + Q_memset (buf, 0, size); + + return buf; +} + +void *Z_TagMalloc (int size, int tag) +{ + int extra; + memblock_t *start, *rover, *new, *base; + + if (!tag) + Sys_Error ("Z_TagMalloc: tried to use a 0 tag"); + +// +// scan through the block list looking for the first free block +// of sufficient size +// + size += sizeof(memblock_t); // account for size of block header + size += 4; // space for memory trash tester + size = (size + 7) & ~7; // align to 8-byte boundary + + base = rover = mainzone->rover; + start = base->prev; + + do + { + 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; + } + + base->tag = tag; // no longer a free block + + mainzone->rover = base->next; // next allocation will start looking here + + base->id = ZONEID; + +// marker for memory trash testing + *(int *)((byte *)base + base->size - 4) = ZONEID; + + return (void *) ((byte *)base + sizeof(memblock_t)); +} + + +/* +======================== +Z_Print +======================== +*/ +void Z_Print (memzone_t *zone) +{ + memblock_t *block; + + Con_Printf ("zone size: %i location: %p\n",mainzone->size,mainzone); + + for (block = zone->blocklist.next ; ; block = block->next) + { + Con_Printf ("block:%p size:%7i tag:%3i\n", + block, block->size, block->tag); + + if (block->next == &zone->blocklist) + break; // all blocks have been hit + if ( (byte *)block + block->size != (byte *)block->next) + Con_Printf ("ERROR: block size does not touch the next block\n"); + if ( block->next->prev != block) + Con_Printf ("ERROR: next block doesn't have proper back link\n"); + if (!block->tag && !block->next->tag) + Con_Printf ("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) + break; // all blocks have been hit + if ( (byte *)block + block->size != (byte *)block->next) + Sys_Error ("Z_CheckHeap: block size does not touch the next block\n"); + if ( block->next->prev != block) + Sys_Error ("Z_CheckHeap: next block doesn't have proper back link\n"); + if (!block->tag && !block->next->tag) + Sys_Error ("Z_CheckHeap: two consecutive free blocks\n"); + } +} + +//============================================================================ + +#define HUNK_SENTINAL 0x1df001ed + +typedef struct +{ + int sentinal; + int size; // including sizeof(hunk_t), -1 = not allocated + char name[8]; +} hunk_t; + +byte *hunk_base; +int hunk_size; + +int hunk_low_used; +int hunk_high_used; + +qboolean hunk_tempactive; +int hunk_tempmark; + +void R_FreeTextures (void); + +/* +============== +Hunk_Check + +Run consistancy and sentinal trahing checks +============== +*/ +void Hunk_Check (void) +{ + hunk_t *h; + + for (h = (hunk_t *)hunk_base ; (byte *)h != hunk_base + hunk_low_used ; ) + { + if (h->sentinal != HUNK_SENTINAL) + Sys_Error ("Hunk_Check: trahsed sentinal"); + if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size) + Sys_Error ("Hunk_Check: bad size"); + h = (hunk_t *)((byte *)h+h->size); + } +} + +/* +============== +Hunk_Print + +If "all" is specified, every single allocation is printed. +Otherwise, allocations with the same name will be totaled up before printing. +============== +*/ +void Hunk_Print (qboolean all) +{ + hunk_t *h, *next, *endlow, *starthigh, *endhigh; + int count, sum; + int totalblocks; + char name[9]; + + name[8] = 0; + count = 0; + sum = 0; + totalblocks = 0; + + h = (hunk_t *)hunk_base; + endlow = (hunk_t *)(hunk_base + hunk_low_used); + starthigh = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); + endhigh = (hunk_t *)(hunk_base + hunk_size); + + Con_Printf (" :%8i total hunk size\n", hunk_size); + Con_Printf ("-------------------------\n"); + + while (1) + { + // + // skip to the high hunk if done with low hunk + // + if ( h == endlow ) + { + Con_Printf ("-------------------------\n"); + Con_Printf (" :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used); + Con_Printf ("-------------------------\n"); + h = starthigh; + } + + // + // if totally done, break + // + if ( h == endhigh ) + break; + + // + // run consistancy checks + // + if (h->sentinal != HUNK_SENTINAL) + Sys_Error ("Hunk_Check: trahsed sentinal"); + if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size) + Sys_Error ("Hunk_Check: bad size"); + + next = (hunk_t *)((byte *)h+h->size); + count++; + totalblocks++; + sum += h->size; + + // + // print the single block + // + memcpy (name, h->name, 8); + if (all) + Con_Printf ("%8p :%8i %8s\n",h, h->size, name); + + // + // print the total + // + if (next == endlow || next == endhigh || + strncmp (h->name, next->name, 8) ) + { + if (!all) + Con_Printf (" :%8i %8s (TOTAL)\n",sum, name); + count = 0; + sum = 0; + } + + h = next; + } + + Con_Printf ("-------------------------\n"); + Con_Printf ("%8i total blocks\n", totalblocks); + +} + +/* +=================== +Hunk_AllocName +=================== +*/ +void *Hunk_AllocName (int size, char *name) +{ + hunk_t *h; + +#ifdef PARANOID + Hunk_Check (); +#endif + + if (size < 0) + Sys_Error ("Hunk_Alloc: bad size: %i", size); + + size = sizeof(hunk_t) + ((size+15)&~15); + + if (hunk_size - hunk_low_used - hunk_high_used < size) + Sys_Error ("Hunk_Alloc: failed on %i bytes",size); + + h = (hunk_t *)(hunk_base + hunk_low_used); + hunk_low_used += size; + + Cache_FreeLow (hunk_low_used); + + memset (h, 0, size); + + h->size = size; + h->sentinal = HUNK_SENTINAL; + Q_strncpy (h->name, name, 8); + + return (void *)(h+1); +} + +/* +=================== +Hunk_Alloc +=================== +*/ +void *Hunk_Alloc (int size) +{ + return Hunk_AllocName (size, "unknown"); +} + +int Hunk_LowMark (void) +{ + return hunk_low_used; +} + +void Hunk_FreeToLowMark (int mark) +{ + if (mark < 0 || mark > hunk_low_used) + Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark); + memset (hunk_base + mark, 0, hunk_low_used - mark); + hunk_low_used = mark; +} + +int Hunk_HighMark (void) +{ + if (hunk_tempactive) + { + hunk_tempactive = false; + Hunk_FreeToHighMark (hunk_tempmark); + } + + return hunk_high_used; +} + +void Hunk_FreeToHighMark (int mark) +{ + if (hunk_tempactive) + { + hunk_tempactive = false; + Hunk_FreeToHighMark (hunk_tempmark); + } + if (mark < 0 || mark > hunk_high_used) + Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark); + memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark); + hunk_high_used = mark; +} + + +/* +=================== +Hunk_HighAllocName +=================== +*/ +void *Hunk_HighAllocName (int size, char *name) +{ + hunk_t *h; + + if (size < 0) + Sys_Error ("Hunk_HighAllocName: bad size: %i", size); + + if (hunk_tempactive) + { + Hunk_FreeToHighMark (hunk_tempmark); + hunk_tempactive = false; + } + +#ifdef PARANOID + Hunk_Check (); +#endif + + size = sizeof(hunk_t) + ((size+15)&~15); + + if (hunk_size - hunk_low_used - hunk_high_used < size) + { + Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n",size); + return NULL; + } + + hunk_high_used += size; + Cache_FreeHigh (hunk_high_used); + + h = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); + + memset (h, 0, size); + h->size = size; + h->sentinal = HUNK_SENTINAL; + Q_strncpy (h->name, name, 8); + + return (void *)(h+1); +} + + +/* +================= +Hunk_TempAlloc + +Return space from the top of the hunk +================= +*/ +void *Hunk_TempAlloc (int size) +{ + void *buf; + + size = (size+15)&~15; + + if (hunk_tempactive) + { + Hunk_FreeToHighMark (hunk_tempmark); + hunk_tempactive = false; + } + + hunk_tempmark = Hunk_HighMark (); + + buf = Hunk_HighAllocName (size, "temp"); + + hunk_tempactive = true; + + return buf; +} + +/* +=============================================================================== + +CACHE MEMORY + +=============================================================================== +*/ + +typedef struct cache_system_s +{ + int size; // including this header + cache_user_t *user; + char name[16]; + struct cache_system_s *prev, *next; + struct cache_system_s *lru_prev, *lru_next; // for LRU flushing +} cache_system_t; + +cache_system_t *Cache_TryAlloc (int size, qboolean nobottom); + +cache_system_t cache_head; + +/* +=========== +Cache_Move +=========== +*/ +void Cache_Move ( cache_system_t *c) +{ + cache_system_t *new; + +// we are clearing up space at the bottom, so only allocate it late + new = Cache_TryAlloc (c->size, true); + if (new) + { +// Con_Printf ("cache_move ok\n"); + + Q_memcpy ( new+1, c+1, c->size - sizeof(cache_system_t) ); + new->user = c->user; + Q_memcpy (new->name, c->name, sizeof(new->name)); + Cache_Free (c->user); + new->user->data = (void *)(new+1); + } + else + { +// Con_Printf ("cache_move failed\n"); + + Cache_Free (c->user); // tough luck... + } +} + +/* +============ +Cache_FreeLow + +Throw things out until the hunk can be expanded to the given point +============ +*/ +void Cache_FreeLow (int new_low_hunk) +{ + cache_system_t *c; + + while (1) + { + c = cache_head.next; + if (c == &cache_head) + return; // nothing in cache at all + if ((byte *)c >= hunk_base + new_low_hunk) + return; // there is space to grow the hunk + Cache_Move ( c ); // reclaim the space + } +} + +/* +============ +Cache_FreeHigh + +Throw things out until the hunk can be expanded to the given point +============ +*/ +void Cache_FreeHigh (int new_high_hunk) +{ + cache_system_t *c, *prev; + + prev = NULL; + while (1) + { + c = cache_head.prev; + if (c == &cache_head) + return; // nothing in cache at all + if ( (byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk) + return; // there is space to grow the hunk + if (c == prev) + Cache_Free (c->user); // didn't move out of the way + else + { + Cache_Move (c); // try to move it + prev = c; + } + } +} + +void Cache_UnlinkLRU (cache_system_t *cs) +{ + if (!cs->lru_next || !cs->lru_prev) + Sys_Error ("Cache_UnlinkLRU: NULL link"); + + cs->lru_next->lru_prev = cs->lru_prev; + cs->lru_prev->lru_next = cs->lru_next; + + cs->lru_prev = cs->lru_next = NULL; +} + +void Cache_MakeLRU (cache_system_t *cs) +{ + if (cs->lru_next || cs->lru_prev) + Sys_Error ("Cache_MakeLRU: active link"); + + cache_head.lru_next->lru_prev = cs; + cs->lru_next = cache_head.lru_next; + cs->lru_prev = &cache_head; + cache_head.lru_next = cs; +} + +/* +============ +Cache_TryAlloc + +Looks for a free block of memory between the high and low hunk marks +Size should already include the header and padding +============ +*/ +cache_system_t *Cache_TryAlloc (int size, qboolean nobottom) +{ + cache_system_t *cs, *new; + +// is the cache completely empty? + + if (!nobottom && cache_head.prev == &cache_head) + { + if (hunk_size - hunk_high_used - hunk_low_used < size) + Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size); + + new = (cache_system_t *) (hunk_base + hunk_low_used); + memset (new, 0, sizeof(*new)); + new->size = size; + + cache_head.prev = cache_head.next = new; + new->prev = new->next = &cache_head; + + Cache_MakeLRU (new); + return new; + } + +// search from the bottom up for space + + new = (cache_system_t *) (hunk_base + hunk_low_used); + cs = cache_head.next; + + do + { + if (!nobottom || cs != cache_head.next) + { + if ( (byte *)cs - (byte *)new >= size) + { // found space + memset (new, 0, sizeof(*new)); + new->size = size; + + new->next = cs; + new->prev = cs->prev; + cs->prev->next = new; + cs->prev = new; + + Cache_MakeLRU (new); + + return new; + } + } + + // continue looking + new = (cache_system_t *)((byte *)cs + cs->size); + cs = cs->next; + + } while (cs != &cache_head); + +// try to allocate one at the very end + if ( hunk_base + hunk_size - hunk_high_used - (byte *)new >= size) + { + memset (new, 0, sizeof(*new)); + new->size = size; + + new->next = &cache_head; + new->prev = cache_head.prev; + cache_head.prev->next = new; + cache_head.prev = new; + + Cache_MakeLRU (new); + + return new; + } + + return NULL; // couldn't allocate +} + +/* +============ +Cache_Flush + +Throw everything out, so new data will be demand cached +============ +*/ +void Cache_Flush (void) +{ + while (cache_head.next != &cache_head) + Cache_Free ( cache_head.next->user ); // reclaim the space +} + + +/* +============ +Cache_Print + +============ +*/ +void Cache_Print (void) +{ + cache_system_t *cd; + + for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next) + { + Con_Printf ("%8i : %s\n", cd->size, cd->name); + } +} + +/* +============ +Cache_Report + +============ +*/ +void Cache_Report (void) +{ + Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024*1024) ); +} + +/* +============ +Cache_Compact + +============ +*/ +void Cache_Compact (void) +{ +} + +/* +============ +Cache_Init + +============ +*/ +void Cache_Init (void) +{ + cache_head.next = cache_head.prev = &cache_head; + cache_head.lru_next = cache_head.lru_prev = &cache_head; + + Cmd_AddCommand ("flush", Cache_Flush); +} + +/* +============== +Cache_Free + +Frees the memory and removes it from the LRU list +============== +*/ +void Cache_Free (cache_user_t *c) +{ + cache_system_t *cs; + + if (!c->data) + Sys_Error ("Cache_Free: not allocated"); + + cs = ((cache_system_t *)c->data) - 1; + + cs->prev->next = cs->next; + cs->next->prev = cs->prev; + cs->next = cs->prev = NULL; + + c->data = NULL; + + Cache_UnlinkLRU (cs); +} + + + +/* +============== +Cache_Check +============== +*/ +void *Cache_Check (cache_user_t *c) +{ + cache_system_t *cs; + + if (!c->data) + return NULL; + + cs = ((cache_system_t *)c->data) - 1; + +// move to head of LRU + Cache_UnlinkLRU (cs); + Cache_MakeLRU (cs); + + return c->data; +} + + +/* +============== +Cache_Alloc +============== +*/ +void *Cache_Alloc (cache_user_t *c, int size, char *name) +{ + cache_system_t *cs; + + if (c->data) + Sys_Error ("Cache_Alloc: allready allocated"); + + if (size <= 0) + Sys_Error ("Cache_Alloc: size %i", size); + + size = (size + sizeof(cache_system_t) + 15) & ~15; + +// find memory for it + while (1) + { + cs = Cache_TryAlloc (size, false); + if (cs) + { + strncpy (cs->name, name, sizeof(cs->name)-1); + c->data = (void *)(cs+1); + cs->user = c; + break; + } + + // free the least recently used cahedat + if (cache_head.lru_prev == &cache_head) + Sys_Error ("Cache_Alloc: out of memory"); + // not enough memory at all + Cache_Free ( cache_head.lru_prev->user ); + } + + return Cache_Check (c); +} + +//============================================================================ + + +/* +======================== +Memory_Init +======================== +*/ +void Memory_Init (void *buf, int size) +{ + int p; + int zonesize = DYNAMIC_SIZE; + + hunk_base = buf; + hunk_size = size; + hunk_low_used = 0; + hunk_high_used = 0; + + Cache_Init (); + p = COM_CheckParm ("-zone"); + if (p) + { + if (p < com_argc-1) + zonesize = Q_atoi (com_argv[p+1]) * 1024; + else + Sys_Error ("Memory_Init: you must specify a size in KB after -zone"); + } + mainzone = Hunk_AllocName (zonesize, "zone" ); + Z_ClearZone (mainzone, zonesize); +} + |