home *** CD-ROM | disk | FTP | other *** search
/ ST-Computer Leser-CD 2000 January / LCD_01_2000.iso / games / doom / pmdoom / src / z_zone.c < prev   
C/C++ Source or Header  |  1999-12-17  |  10KB  |  468 lines
  1. /*  Emacs style mode select   -*- C++ -*-  */
  2. /* ----------------------------------------------------------------------------- */
  3. /*  */
  4. /*  $Id:$ */
  5. /*  */
  6. /*  Copyright (C) 1993-1996 by id Software, Inc. */
  7. /*  */
  8. /*  This source is available for distribution and/or modification */
  9. /*  only under the terms of the DOOM Source Code License as */
  10. /*  published by id Software. All rights reserved. */
  11. /*  */
  12. /*  The source is distributed in the hope that it will be useful, */
  13. /*  but WITHOUT ANY WARRANTY; without even the implied warranty of */
  14. /*  FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License */
  15. /*  for more details. */
  16. /*  */
  17. /*  $Log:$ */
  18. /*  */
  19. /*  DESCRIPTION: */
  20. /*     Zone Memory Allocation. Neat. */
  21. /*  */
  22. /* ----------------------------------------------------------------------------- */
  23.  
  24. static const char
  25. rcsid[] = "$Id: z_zone.c,v 1.4 1997/02/03 16:47:58 b1 Exp $";
  26.  
  27. #include "z_zone.h"
  28. #include "i_system.h"
  29. #include "doomdef.h"
  30.  
  31.  
  32. /*  */
  33. /*  ZONE MEMORY ALLOCATION */
  34. /*  */
  35. /*  There is never any space between memblocks, */
  36. /*   and there will never be two contiguous free memblocks. */
  37. /*  The rover can be left pointing at a non-empty block. */
  38. /*  */
  39. /*  It is of no value to free a cachable block, */
  40. /*   because it will get overwritten automatically if needed. */
  41. /*   */
  42.  
  43. #define ZONEID    0x1d4a11
  44.  
  45.  
  46. typedef struct
  47. {
  48.     /*  total bytes malloced, including header */
  49.     int        size;
  50.  
  51.     /*  start / end cap for linked list */
  52.     memblock_t    blocklist;
  53.     
  54.     memblock_t*    rover;
  55.     
  56. } memzone_t;
  57.  
  58.  
  59.  
  60. memzone_t*    mainzone;
  61.  
  62.  
  63.  
  64. /*  */
  65. /*  Z_ClearZone */
  66. /*  */
  67. void Z_ClearZone (memzone_t* zone)
  68. {
  69.     memblock_t*        block;
  70.     
  71.     /*  set the entire zone to one free block */
  72.     zone->blocklist.next =
  73.     zone->blocklist.prev =
  74.     block = (memblock_t *)( (byte *)zone + sizeof(memzone_t) );
  75.     
  76.     zone->blocklist.user = (void *)zone;
  77.     zone->blocklist.tag = PU_STATIC;
  78.     zone->rover = block;
  79.     
  80.     block->prev = block->next = &zone->blocklist;
  81.     
  82.     /*  NULL indicates a free block. */
  83.     block->user = NULL;    
  84.  
  85.     block->size = zone->size - sizeof(memzone_t);
  86. }
  87.  
  88.  
  89.  
  90. /*  */
  91. /*  Z_Init */
  92. /*  */
  93. void Z_Init (void)
  94. {
  95.     memblock_t*    block;
  96.     int        size;
  97.  
  98.     mainzone = (memzone_t *)I_ZoneBase (&size);
  99.     mainzone->size = size;
  100.  
  101.     /*  set the entire zone to one free block */
  102.     mainzone->blocklist.next =
  103.     mainzone->blocklist.prev =
  104.     block = (memblock_t *)( (byte *)mainzone + sizeof(memzone_t) );
  105.  
  106.     mainzone->blocklist.user = (void *)mainzone;
  107.     mainzone->blocklist.tag = PU_STATIC;
  108.     mainzone->rover = block;
  109.     
  110.     block->prev = block->next = &mainzone->blocklist;
  111.  
  112.     /*  NULL indicates a free block. */
  113.     block->user = NULL;
  114.     
  115.     block->size = mainzone->size - sizeof(memzone_t);
  116. }
  117.  
  118.  
  119. /*  */
  120. /*  Z_Free */
  121. /*  */
  122. void Z_Free (void* ptr)
  123. {
  124.     memblock_t*        block;
  125.     memblock_t*        other;
  126.     
  127.     block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
  128.  
  129.     if (block->id != ZONEID)
  130.     I_Error ("Z_Free: freed a pointer without ZONEID");
  131.         
  132.     if (block->user > (void **)0x100)
  133.     {
  134.     /*  smaller values are not pointers */
  135.     /*  Note: OS-dependend? */
  136.     
  137.     /*  clear the user's mark */
  138.     *block->user = 0;
  139.     }
  140.  
  141.     /*  mark as free */
  142.     block->user = NULL;    
  143.     block->tag = 0;
  144.     block->id = 0;
  145.     
  146.     other = block->prev;
  147.  
  148.     if (!other->user)
  149.     {
  150.     /*  merge with previous free block */
  151.     other->size += block->size;
  152.     other->next = block->next;
  153.     other->next->prev = other;
  154.  
  155.     if (block == mainzone->rover)
  156.         mainzone->rover = other;
  157.  
  158.     block = other;
  159.     }
  160.     
  161.     other = block->next;
  162.     if (!other->user)
  163.     {
  164.     /*  merge the next free block onto the end */
  165.     block->size += other->size;
  166.     block->next = other->next;
  167.     block->next->prev = block;
  168.  
  169.     if (other == mainzone->rover)
  170.         mainzone->rover = block;
  171.     }
  172. }
  173.  
  174.  
  175.  
  176. /*  */
  177. /*  Z_Malloc */
  178. /*  You can pass a NULL user if the tag is < PU_PURGELEVEL. */
  179. /*  */
  180. #define MINFRAGMENT        64
  181.  
  182.  
  183. void*
  184. Z_Malloc
  185. ( int        size,
  186.   int        tag,
  187.   void*        user )
  188. {
  189.     int        extra;
  190.     memblock_t*    start;
  191.     memblock_t* rover;
  192.     memblock_t* newblock;
  193.     memblock_t*    base;
  194.  
  195.     size = (size + 3) & ~3;
  196.     
  197.     /*  scan through the block list, */
  198.     /*  looking for the first free block */
  199.     /*  of sufficient size, */
  200.     /*  throwing out any purgable blocks along the way. */
  201.  
  202.     /*  account for size of block header */
  203.     size += sizeof(memblock_t);
  204.     
  205.     /*  if there is a free block behind the rover, */
  206.     /*   back up over them */
  207.     base = mainzone->rover;
  208.     
  209.     if (!base->prev->user)
  210.     base = base->prev;
  211.     
  212.     rover = base;
  213.     start = base->prev;
  214.     
  215.     do
  216.     {
  217.     if (rover == start)
  218.     {
  219.         /*  scanned all the way around the list */
  220.         I_Error ("Z_Malloc: failed on allocation of %i bytes", size);
  221.     }
  222.     
  223.     if (rover->user)
  224.     {
  225.         if (rover->tag < PU_PURGELEVEL)
  226.         {
  227.         /*  hit a block that can't be purged, */
  228.         /*   so move base past it */
  229.         base = rover = rover->next;
  230.         }
  231.         else
  232.         {
  233.         /*  free the rover block (adding the size to base) */
  234.  
  235.         /*  the rover can be the base block */
  236.         base = base->prev;
  237.         Z_Free ((byte *)rover+sizeof(memblock_t));
  238.         base = base->next;
  239.         rover = base->next;
  240.         }
  241.     }
  242.     else
  243.         rover = rover->next;
  244.     } while (base->user || base->size < size);
  245.  
  246.     
  247.     /*  found a block big enough */
  248.     extra = base->size - size;
  249.     
  250.     if (extra >  MINFRAGMENT)
  251.     {
  252.     /*  there will be a free fragment after the allocated block */
  253.     newblock = (memblock_t *) ((byte *)base + size );
  254.     newblock->size = extra;
  255.     
  256.     /*  NULL indicates free block. */
  257.     newblock->user = NULL;    
  258.     newblock->tag = 0;
  259.     newblock->prev = base;
  260.     newblock->next = base->next;
  261.     newblock->next->prev = newblock;
  262.  
  263.     base->next = newblock;
  264.     base->size = size;
  265.     }
  266.     
  267.     if (user)
  268.     {
  269.     /*  mark as an in use block */
  270.     base->user = user;            
  271.     *(void **)user = (void *) ((byte *)base + sizeof(memblock_t));
  272.     }
  273.     else
  274.     {
  275.     if (tag >= PU_PURGELEVEL)
  276.         I_Error ("Z_Malloc: an owner is required for purgable blocks");
  277.  
  278.     /*  mark as in use, but unowned     */
  279.     base->user = (void *)2;        
  280.     }
  281.     base->tag = tag;
  282.  
  283.     /*  next allocation will start looking here */
  284.     mainzone->rover = base->next;    
  285.     
  286.     base->id = ZONEID;
  287.     
  288.     return (void *) ((byte *)base + sizeof(memblock_t));
  289. }
  290.  
  291.  
  292.  
  293. /*  */
  294. /*  Z_FreeTags */
  295. /*  */
  296. void
  297. Z_FreeTags
  298. ( int        lowtag,
  299.   int        hightag )
  300. {
  301.     memblock_t*    block;
  302.     memblock_t*    next;
  303.     
  304.     for (block = mainzone->blocklist.next ;
  305.      block != &mainzone->blocklist ;
  306.      block = next)
  307.     {
  308.     /*  get link before freeing */
  309.     next = block->next;
  310.  
  311.     /*  free block? */
  312.     if (!block->user)
  313.         continue;
  314.     
  315.     if (block->tag >= lowtag && block->tag <= hightag)
  316.         Z_Free ( (byte *)block+sizeof(memblock_t));
  317.     }
  318. }
  319.  
  320.  
  321.  
  322. /*  */
  323. /*  Z_DumpHeap */
  324. /*  Note: TFileDumpHeap( stdout ) ? */
  325. /*  */
  326. void
  327. Z_DumpHeap
  328. ( int        lowtag,
  329.   int        hightag )
  330. {
  331.     memblock_t*    block;
  332.     
  333.     printf ("zone size: %i  location: %p\n",
  334.         mainzone->size,mainzone);
  335.     
  336.     printf ("tag range: %i to %i\n",
  337.         lowtag, hightag);
  338.     
  339.     for (block = mainzone->blocklist.next ; ; block = block->next)
  340.     {
  341.     if (block->tag >= lowtag && block->tag <= hightag)
  342.         printf ("block:%p    size:%7i    user:%p    tag:%3i\n",
  343.             block, block->size, block->user, block->tag);
  344.         
  345.     if (block->next == &mainzone->blocklist)
  346.     {
  347.         /*  all blocks have been hit */
  348.         break;
  349.     }
  350.     
  351.     if ( (byte *)block + block->size != (byte *)block->next)
  352.         printf ("ERROR: block size does not touch the next block\n");
  353.  
  354.     if ( block->next->prev != block)
  355.         printf ("ERROR: next block doesn't have proper back link\n");
  356.  
  357.     if (!block->user && !block->next->user)
  358.         printf ("ERROR: two consecutive free blocks\n");
  359.     }
  360. }
  361.  
  362.  
  363. /*  */
  364. /*  Z_FileDumpHeap */
  365. /*  */
  366. void Z_FileDumpHeap (FILE* f)
  367. {
  368.     memblock_t*    block;
  369.     
  370.     fprintf (f,"zone size: %i  location: %p\n",mainzone->size,mainzone);
  371.     
  372.     for (block = mainzone->blocklist.next ; ; block = block->next)
  373.     {
  374.     fprintf (f,"block:%p    size:%7i    user:%p    tag:%3i\n",
  375.          block, block->size, block->user, block->tag);
  376.         
  377.     if (block->next == &mainzone->blocklist)
  378.     {
  379.         /*  all blocks have been hit */
  380.         break;
  381.     }
  382.     
  383.     if ( (byte *)block + block->size != (byte *)block->next)
  384.         fprintf (f,"ERROR: block size does not touch the next block\n");
  385.  
  386.     if ( block->next->prev != block)
  387.         fprintf (f,"ERROR: next block doesn't have proper back link\n");
  388.  
  389.     if (!block->user && !block->next->user)
  390.         fprintf (f,"ERROR: two consecutive free blocks\n");
  391.     }
  392. }
  393.  
  394.  
  395.  
  396. /*  */
  397. /*  Z_CheckHeap */
  398. /*  */
  399. void Z_CheckHeap (void)
  400. {
  401.     memblock_t*    block;
  402.     
  403.     for (block = mainzone->blocklist.next ; ; block = block->next)
  404.     {
  405.     if (block->next == &mainzone->blocklist)
  406.     {
  407.         /*  all blocks have been hit */
  408.         break;
  409.     }
  410.     
  411.     if ( (byte *)block + block->size != (byte *)block->next)
  412.         I_Error ("Z_CheckHeap: block size does not touch the next block\n");
  413.  
  414.     if ( block->next->prev != block)
  415.         I_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
  416.  
  417.     if (!block->user && !block->next->user)
  418.         I_Error ("Z_CheckHeap: two consecutive free blocks\n");
  419.     }
  420. }
  421.  
  422.  
  423.  
  424.  
  425. /*  */
  426. /*  Z_ChangeTag */
  427. /*  */
  428. void
  429. Z_ChangeTag2
  430. ( void*        ptr,
  431.   int        tag )
  432. {
  433.     memblock_t*    block;
  434.     
  435.     block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
  436.  
  437.     if (block->id != ZONEID)
  438.     I_Error ("Z_ChangeTag: freed a pointer without ZONEID");
  439.  
  440.     if (tag >= PU_PURGELEVEL && (unsigned)block->user < 0x100)
  441.     I_Error ("Z_ChangeTag: an owner is required for purgable blocks");
  442.  
  443.     block->tag = tag;
  444. }
  445.  
  446.  
  447.  
  448. /*  */
  449. /*  Z_FreeMemory */
  450. /*  */
  451. int Z_FreeMemory (void)
  452. {
  453.     memblock_t*        block;
  454.     int            free;
  455.     
  456.     free = 0;
  457.     
  458.     for (block = mainzone->blocklist.next ;
  459.      block != &mainzone->blocklist;
  460.      block = block->next)
  461.     {
  462.     if (!block->user || block->tag >= PU_PURGELEVEL)
  463.         free += block->size;
  464.     }
  465.     return free;
  466. }
  467.  
  468.