zone.c

   1 /*
   2 Copyright (C) 1996-1997 Id Software, Inc.
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20 // Z_zone.c
  21
  22 #include "quakedef.h"
  23
  24 #define DYNAMIC_SIZE    0xc000
  25
  26 #define ZONEID  0x1d4a11
  27 #define MINFRAGMENT     64
  28
  29 typedef struct memblock_s
  30 {
  31         int             size;           // including the header and possibly tiny fragments
  32         int     tag;            // a tag of 0 is a free block
  33         int     id;                     // should be ZONEID
  34         struct memblock_s       *next, *prev;
  35         int             pad;                    // pad to 64 bit boundary
  36 } memblock_t;
  37
  38 typedef struct
  39 {
  40         int             size;           // total bytes malloced, including header
  41         memblock_t      blocklist;              // start / end cap for linked list
  42         memblock_t      *rover;
  43 } memzone_t;
  44
  45 void Cache_FreeLow (int new_low_hunk);
  46 void Cache_FreeHigh (int new_high_hunk);
  47
  48
  49 /*
  50 ==============================================================================
  51
  52                                                 ZONE MEMORY ALLOCATION
  53
  54 There is never any space between memblocks, and there will never be two
  55 contiguous free memblocks.
  56
  57 The rover can be left pointing at a non-empty block
  58
  59 The zone calls are pretty much only used for small strings and structures,
  60 all big things are allocated on the hunk.
  61 ==============================================================================
  62 */
  63
  64 memzone_t       *mainzone;
  65
  66 void Z_ClearZone (memzone_t *zone, int size);
  67
  68
  69 /*
  70 ========================
  71 Z_ClearZone
  72 ========================
  73 */
  74 void Z_ClearZone (memzone_t *zone, int size)
  75 {
  76         memblock_t      *block;
  77
  78 // set the entire zone to one free block
  79
  80         zone->blocklist.next = zone->blocklist.prev = block =
  81                 (memblock_t *)( (byte *)zone + sizeof(memzone_t) );
  82         zone->blocklist.tag = 1;        // in use block
  83         zone->blocklist.id = 0;
  84         zone->blocklist.size = 0;
  85         zone->rover = block;
  86
  87         block->prev = block->next = &zone->blocklist;
  88         block->tag = 0;                 // free block
  89         block->id = ZONEID;
  90         block->size = size - sizeof(memzone_t);
  91 }
  92
  93
  94 /*
  95 ========================
  96 Z_Free
  97 ========================
  98 */
  99 void Z_Free (void *ptr)
 100 {
 101         memblock_t      *block, *other;
 102
 103         if (!ptr)
 104                 Sys_Error ("Z_Free: NULL pointer");
 105
 106         block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
 107         if (block->id != ZONEID)
 108                 Sys_Error ("Z_Free: freed a pointer without ZONEID");
 109         if (block->tag == 0)
 110                 Sys_Error ("Z_Free: freed a freed pointer");
 111
 112         block->tag = 0;         // mark as free
 113
 114         other = block->prev;
 115         if (!other->tag)
 116         {       // merge with previous free block
 117                 other->size += block->size;
 118                 other->next = block->next;
 119                 other->next->prev = other;
 120                 if (block == mainzone->rover)
 121                         mainzone->rover = other;
 122                 block = other;
 123         }
 124
 125         other = block->next;
 126         if (!other->tag)
 127         {       // merge the next free block onto the end
 128                 block->size += other->size;
 129                 block->next = other->next;
 130                 block->next->prev = block;
 131                 if (other == mainzone->rover)
 132                         mainzone->rover = block;
 133         }
 134 }
 135
 136
 137 /*
 138 ========================
 139 Z_Malloc
 140 ========================
 141 */
 142 void *Z_Malloc (int size)
 143 {
 144         void    *buf;
 145
 146 Z_CheckHeap (); // DEBUG
 147         buf = Z_TagMalloc (size, 1);
 148         if (!buf)
 149                 Sys_Error ("Z_Malloc: failed on allocation of %i bytes",size);
 150         Q_memset (buf, 0, size);
 151
 152         return buf;
 153 }
 154
 155 void *Z_TagMalloc (int size, int tag)
 156 {
 157         int             extra;
 158         memblock_t      *start, *rover, *new, *base;
 159
 160         if (!tag)
 161                 Sys_Error ("Z_TagMalloc: tried to use a 0 tag");
 162
 163 //
 164 // scan through the block list looking for the first free block
 165 // of sufficient size
 166 //
 167         size += sizeof(memblock_t);     // account for size of block header
 168         size += 4;                                      // space for memory trash tester
 169         size = (size + 7) & ~7;         // align to 8-byte boundary
 170
 171         base = rover = mainzone->rover;
 172         start = base->prev;
 173
 174         do
 175         {
 176                 if (rover == start)     // scaned all the way around the list
 177                         return NULL;
 178                 if (rover->tag)
 179                         base = rover = rover->next;
 180                 else
 181                         rover = rover->next;
 182         } while (base->tag || base->size < size);
 183
 184 //
 185 // found a block big enough
 186 //
 187         extra = base->size - size;
 188         if (extra >  MINFRAGMENT)
 189         {       // there will be a free fragment after the allocated block
 190                 new = (memblock_t *) ((byte *)base + size );
 191                 new->size = extra;
 192                 new->tag = 0;                   // free block
 193                 new->prev = base;
 194                 new->id = ZONEID;
 195                 new->next = base->next;
 196                 new->next->prev = new;
 197                 base->next = new;
 198                 base->size = size;
 199         }
 200
 201         base->tag = tag;                                // no longer a free block
 202
 203         mainzone->rover = base->next;   // next allocation will start looking here
 204
 205         base->id = ZONEID;
 206
 207 // marker for memory trash testing
 208         *(int *)((byte *)base + base->size - 4) = ZONEID;
 209
 210         return (void *) ((byte *)base + sizeof(memblock_t));
 211 }
 212
 213
 214 /*
 215 ========================
 216 Z_Print
 217 ========================
 218 */
 219 void Z_Print (memzone_t *zone)
 220 {
 221         memblock_t      *block;
 222
 223         Con_Printf ("zone size: %i  location: %p\n",mainzone->size,mainzone);
 224
 225         for (block = zone->blocklist.next ; ; block = block->next)
 226         {
 227                 Con_Printf ("block:%p    size:%7i    tag:%3i\n",
 228                         block, block->size, block->tag);
 229
 230                 if (block->next == &zone->blocklist)
 231                         break;                  // all blocks have been hit
 232                 if ( (byte *)block + block->size != (byte *)block->next)
 233                         Con_Printf ("ERROR: block size does not touch the next block\n");
 234                 if ( block->next->prev != block)
 235                         Con_Printf ("ERROR: next block doesn't have proper back link\n");
 236                 if (!block->tag && !block->next->tag)
 237                         Con_Printf ("ERROR: two consecutive free blocks\n");
 238         }
 239 }
 240
 241
 242 /*
 243 ========================
 244 Z_CheckHeap
 245 ========================
 246 */
 247 void Z_CheckHeap (void)
 248 {
 249         memblock_t      *block;
 250
 251         for (block = mainzone->blocklist.next ; ; block = block->next)
 252         {
 253                 if (block->next == &mainzone->blocklist)
 254                         break;                  // all blocks have been hit
 255                 if ( (byte *)block + block->size != (byte *)block->next)
 256                         Sys_Error ("Z_CheckHeap: block size does not touch the next block\n");
 257                 if ( block->next->prev != block)
 258                         Sys_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
 259                 if (!block->tag && !block->next->tag)
 260                         Sys_Error ("Z_CheckHeap: two consecutive free blocks\n");
 261         }
 262 }
 263
 264 //============================================================================
 265
 266 #define HUNK_SENTINAL   0x1df001ed
 267
 268 typedef struct
 269 {
 270         int             sentinal;
 271         int             size;           // including sizeof(hunk_t), -1 = not allocated
 272         char    name[8];
 273 } hunk_t;
 274
 275 byte    *hunk_base;
 276 int             hunk_size;
 277
 278 int             hunk_low_used;
 279 int             hunk_high_used;
 280
 281 qboolean        hunk_tempactive;
 282 int             hunk_tempmark;
 283
 284 void R_FreeTextures (void);
 285
 286 /*
 287 ==============
 288 Hunk_Check
 289
 290 Run consistancy and sentinal trahing checks
 291 ==============
 292 */
 293 void Hunk_Check (void)
 294 {
 295         hunk_t  *h;
 296
 297         for (h = (hunk_t *)hunk_base ; (byte *)h != hunk_base + hunk_low_used ; )
 298         {
 299                 if (h->sentinal != HUNK_SENTINAL)
 300                         Sys_Error ("Hunk_Check: trahsed sentinal");
 301                 if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size)
 302                         Sys_Error ("Hunk_Check: bad size");
 303                 h = (hunk_t *)((byte *)h+h->size);
 304         }
 305 }
 306
 307 /*
 308 ==============
 309 Hunk_Print
 310
 311 If "all" is specified, every single allocation is printed.
 312 Otherwise, allocations with the same name will be totaled up before printing.
 313 ==============
 314 */
 315 void Hunk_Print (qboolean all)
 316 {
 317         hunk_t  *h, *next, *endlow, *starthigh, *endhigh;
 318         int             count, sum;
 319         int             totalblocks;
 320         char    name[9];
 321
 322         name[8] = 0;
 323         count = 0;
 324         sum = 0;
 325         totalblocks = 0;
 326
 327         h = (hunk_t *)hunk_base;
 328         endlow = (hunk_t *)(hunk_base + hunk_low_used);
 329         starthigh = (hunk_t *)(hunk_base + hunk_size - hunk_high_used);
 330         endhigh = (hunk_t *)(hunk_base + hunk_size);
 331
 332         Con_Printf ("          :%8i total hunk size\n", hunk_size);
 333         Con_Printf ("-------------------------\n");
 334
 335         while (1)
 336         {
 337         //
 338         // skip to the high hunk if done with low hunk
 339         //
 340                 if ( h == endlow )
 341                 {
 342                         Con_Printf ("-------------------------\n");
 343                         Con_Printf ("          :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used);
 344                         Con_Printf ("-------------------------\n");
 345                         h = starthigh;
 346                 }
 347
 348         //
 349         // if totally done, break
 350         //
 351                 if ( h == endhigh )
 352                         break;
 353
 354         //
 355         // run consistancy checks
 356         //
 357                 if (h->sentinal != HUNK_SENTINAL)
 358                         Sys_Error ("Hunk_Check: trahsed sentinal");
 359                 if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size)
 360                         Sys_Error ("Hunk_Check: bad size");
 361
 362                 next = (hunk_t *)((byte *)h+h->size);
 363                 count++;
 364                 totalblocks++;
 365                 sum += h->size;
 366
 367         //
 368         // print the single block
 369         //
 370                 memcpy (name, h->name, 8);
 371                 if (all)
 372                         Con_Printf ("%8p :%8i %8s\n",h, h->size, name);
 373
 374         //
 375         // print the total
 376         //
 377                 if (next == endlow || next == endhigh ||
 378                 strncmp (h->name, next->name, 8) )
 379                 {
 380                         if (!all)
 381                                 Con_Printf ("          :%8i %8s (TOTAL)\n",sum, name);
 382                         count = 0;
 383                         sum = 0;
 384                 }
 385
 386                 h = next;
 387         }
 388
 389         Con_Printf ("-------------------------\n");
 390         Con_Printf ("%8i total blocks\n", totalblocks);
 391
 392 }
 393
 394 /*
 395 ===================
 396 Hunk_AllocName
 397 ===================
 398 */
 399 void *Hunk_AllocName (int size, char *name)
 400 {
 401         hunk_t  *h;
 402
 403 #ifdef PARANOID
 404         Hunk_Check ();
 405 #endif
 406
 407         if (size < 0)
 408                 Sys_Error ("Hunk_Alloc: bad size: %i", size);
 409
 410         size = sizeof(hunk_t) + ((size+15)&~15);
 411
 412         if (hunk_size - hunk_low_used - hunk_high_used < size)
 413                 Sys_Error ("Hunk_Alloc: failed on %i bytes",size);
 414
 415         h = (hunk_t *)(hunk_base + hunk_low_used);
 416         hunk_low_used += size;
 417
 418         Cache_FreeLow (hunk_low_used);
 419
 420         memset (h, 0, size);
 421
 422         h->size = size;
 423         h->sentinal = HUNK_SENTINAL;
 424         Q_strncpy (h->name, name, 8);
 425
 426         return (void *)(h+1);
 427 }
 428
 429 /*
 430 ===================
 431 Hunk_Alloc
 432 ===================
 433 */
 434 void *Hunk_Alloc (int size)
 435 {
 436         return Hunk_AllocName (size, "unknown");
 437 }
 438
 439 int     Hunk_LowMark (void)
 440 {
 441         return hunk_low_used;
 442 }
 443
 444 void Hunk_FreeToLowMark (int mark)
 445 {
 446         if (mark < 0 || mark > hunk_low_used)
 447                 Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark);
 448         memset (hunk_base + mark, 0, hunk_low_used - mark);
 449         hunk_low_used = mark;
 450 }
 451
 452 int     Hunk_HighMark (void)
 453 {
 454         if (hunk_tempactive)
 455         {
 456                 hunk_tempactive = false;
 457                 Hunk_FreeToHighMark (hunk_tempmark);
 458         }
 459
 460         return hunk_high_used;
 461 }
 462
 463 void Hunk_FreeToHighMark (int mark)
 464 {
 465         if (hunk_tempactive)
 466         {
 467                 hunk_tempactive = false;
 468                 Hunk_FreeToHighMark (hunk_tempmark);
 469         }
 470         if (mark < 0 || mark > hunk_high_used)
 471                 Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark);
 472         memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark);
 473         hunk_high_used = mark;
 474 }
 475
 476
 477 /*
 478 ===================
 479 Hunk_HighAllocName
 480 ===================
 481 */
 482 void *Hunk_HighAllocName (int size, char *name)
 483 {
 484         hunk_t  *h;
 485
 486         if (size < 0)
 487                 Sys_Error ("Hunk_HighAllocName: bad size: %i", size);
 488
 489         if (hunk_tempactive)
 490         {
 491                 Hunk_FreeToHighMark (hunk_tempmark);
 492                 hunk_tempactive = false;
 493         }
 494
 495 #ifdef PARANOID
 496         Hunk_Check ();
 497 #endif
 498
 499         size = sizeof(hunk_t) + ((size+15)&~15);
 500
 501         if (hunk_size - hunk_low_used - hunk_high_used < size)
 502         {
 503                 Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n",size);
 504                 return NULL;
 505         }
 506
 507         hunk_high_used += size;
 508         Cache_FreeHigh (hunk_high_used);
 509
 510         h = (hunk_t *)(hunk_base + hunk_size - hunk_high_used);
 511
 512         memset (h, 0, size);
 513         h->size = size;
 514         h->sentinal = HUNK_SENTINAL;
 515         Q_strncpy (h->name, name, 8);
 516
 517         return (void *)(h+1);
 518 }
 519
 520
 521 /*
 522 =================
 523 Hunk_TempAlloc
 524
 525 Return space from the top of the hunk
 526 =================
 527 */
 528 void *Hunk_TempAlloc (int size)
 529 {
 530         void    *buf;
 531
 532         size = (size+15)&~15;
 533
 534         if (hunk_tempactive)
 535         {
 536                 Hunk_FreeToHighMark (hunk_tempmark);
 537                 hunk_tempactive = false;
 538         }
 539
 540         hunk_tempmark = Hunk_HighMark ();
 541
 542         buf = Hunk_HighAllocName (size, "temp");
 543
 544         hunk_tempactive = true;
 545
 546         return buf;
 547 }
 548
 549 /*
 550 ===============================================================================
 551
 552 CACHE MEMORY
 553
 554 ===============================================================================
 555 */
 556
 557 typedef struct cache_system_s
 558 {
 559         int                                             size;           // including this header
 560         cache_user_t                    *user;
 561         char                                    name[16];
 562         struct cache_system_s   *prev, *next;
 563         struct cache_system_s   *lru_prev, *lru_next;   // for LRU flushing
 564 } cache_system_t;
 565
 566 cache_system_t *Cache_TryAlloc (int size, qboolean nobottom);
 567
 568 cache_system_t  cache_head;
 569
 570 /*
 571 ===========
 572 Cache_Move
 573 ===========
 574 */
 575 void Cache_Move ( cache_system_t *c)
 576 {
 577         cache_system_t          *new;
 578
 579 // we are clearing up space at the bottom, so only allocate it late
 580         new = Cache_TryAlloc (c->size, true);
 581         if (new)
 582         {
 583 //              Con_Printf ("cache_move ok\n");
 584
 585                 Q_memcpy ( new+1, c+1, c->size - sizeof(cache_system_t) );
 586                 new->user = c->user;
 587                 Q_memcpy (new->name, c->name, sizeof(new->name));
 588                 Cache_Free (c->user);
 589                 new->user->data = (void *)(new+1);
 590         }
 591         else
 592         {
 593 //              Con_Printf ("cache_move failed\n");
 594
 595                 Cache_Free (c->user);           // tough luck...
 596         }
 597 }
 598
 599 /*
 600 ============
 601 Cache_FreeLow
 602
 603 Throw things out until the hunk can be expanded to the given point
 604 ============
 605 */
 606 void Cache_FreeLow (int new_low_hunk)
 607 {
 608         cache_system_t  *c;
 609
 610         while (1)
 611         {
 612                 c = cache_head.next;
 613                 if (c == &cache_head)
 614                         return;         // nothing in cache at all
 615                 if ((byte *)c >= hunk_base + new_low_hunk)
 616                         return;         // there is space to grow the hunk
 617                 Cache_Move ( c );       // reclaim the space
 618         }
 619 }
 620
 621 /*
 622 ============
 623 Cache_FreeHigh
 624
 625 Throw things out until the hunk can be expanded to the given point
 626 ============
 627 */
 628 void Cache_FreeHigh (int new_high_hunk)
 629 {
 630         cache_system_t  *c, *prev;
 631
 632         prev = NULL;
 633         while (1)
 634         {
 635                 c = cache_head.prev;
 636                 if (c == &cache_head)
 637                         return;         // nothing in cache at all
 638                 if ( (byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk)
 639                         return;         // there is space to grow the hunk
 640                 if (c == prev)
 641                         Cache_Free (c->user);   // didn't move out of the way
 642                 else
 643                 {
 644                         Cache_Move (c); // try to move it
 645                         prev = c;
 646                 }
 647         }
 648 }
 649
 650 void Cache_UnlinkLRU (cache_system_t *cs)
 651 {
 652         if (!cs->lru_next || !cs->lru_prev)
 653                 Sys_Error ("Cache_UnlinkLRU: NULL link");
 654
 655         cs->lru_next->lru_prev = cs->lru_prev;
 656         cs->lru_prev->lru_next = cs->lru_next;
 657
 658         cs->lru_prev = cs->lru_next = NULL;
 659 }
 660
 661 void Cache_MakeLRU (cache_system_t *cs)
 662 {
 663         if (cs->lru_next || cs->lru_prev)
 664                 Sys_Error ("Cache_MakeLRU: active link");
 665
 666         cache_head.lru_next->lru_prev = cs;
 667         cs->lru_next = cache_head.lru_next;
 668         cs->lru_prev = &cache_head;
 669         cache_head.lru_next = cs;
 670 }
 671
 672 /*
 673 ============
 674 Cache_TryAlloc
 675
 676 Looks for a free block of memory between the high and low hunk marks
 677 Size should already include the header and padding
 678 ============
 679 */
 680 cache_system_t *Cache_TryAlloc (int size, qboolean nobottom)
 681 {
 682         cache_system_t  *cs, *new;
 683
 684 // is the cache completely empty?
 685
 686         if (!nobottom && cache_head.prev == &cache_head)
 687         {
 688                 if (hunk_size - hunk_high_used - hunk_low_used < size)
 689                         Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size);
 690
 691                 new = (cache_system_t *) (hunk_base + hunk_low_used);
 692                 memset (new, 0, sizeof(*new));
 693                 new->size = size;
 694
 695                 cache_head.prev = cache_head.next = new;
 696                 new->prev = new->next = &cache_head;
 697
 698                 Cache_MakeLRU (new);
 699                 return new;
 700         }
 701
 702 // search from the bottom up for space
 703
 704         new = (cache_system_t *) (hunk_base + hunk_low_used);
 705         cs = cache_head.next;
 706
 707         do
 708         {
 709                 if (!nobottom || cs != cache_head.next)
 710                 {
 711                         if ( (byte *)cs - (byte *)new >= size)
 712                         {       // found space
 713                                 memset (new, 0, sizeof(*new));
 714                                 new->size = size;
 715
 716                                 new->next = cs;
 717                                 new->prev = cs->prev;
 718                                 cs->prev->next = new;
 719                                 cs->prev = new;
 720
 721                                 Cache_MakeLRU (new);
 722
 723                                 return new;
 724                         }
 725                 }
 726
 727         // continue looking
 728                 new = (cache_system_t *)((byte *)cs + cs->size);
 729                 cs = cs->next;
 730
 731         } while (cs != &cache_head);
 732
 733 // try to allocate one at the very end
 734         if ( hunk_base + hunk_size - hunk_high_used - (byte *)new >= size)
 735         {
 736                 memset (new, 0, sizeof(*new));
 737                 new->size = size;
 738
 739                 new->next = &cache_head;
 740                 new->prev = cache_head.prev;
 741                 cache_head.prev->next = new;
 742                 cache_head.prev = new;
 743
 744                 Cache_MakeLRU (new);
 745
 746                 return new;
 747         }
 748
 749         return NULL;            // couldn't allocate
 750 }
 751
 752 /*
 753 ============
 754 Cache_Flush
 755
 756 Throw everything out, so new data will be demand cached
 757 ============
 758 */
 759 void Cache_Flush (void)
 760 {
 761         while (cache_head.next != &cache_head)
 762                 Cache_Free ( cache_head.next->user );   // reclaim the space
 763 }
 764
 765
 766 /*
 767 ============
 768 Cache_Print
 769
 770 ============
 771 */
 772 void Cache_Print (void)
 773 {
 774         cache_system_t  *cd;
 775
 776         for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next)
 777         {
 778                 Con_Printf ("%8i : %s\n", cd->size, cd->name);
 779         }
 780 }
 781
 782 /*
 783 ============
 784 Cache_Report
 785
 786 ============
 787 */
 788 void Cache_Report (void)
 789 {
 790         Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024*1024) );
 791 }
 792
 793 /*
 794 ============
 795 Cache_Compact
 796
 797 ============
 798 */
 799 void Cache_Compact (void)
 800 {
 801 }
 802
 803 /*
 804 ============
 805 Cache_Init
 806
 807 ============
 808 */
 809 void Cache_Init (void)
 810 {
 811         cache_head.next = cache_head.prev = &cache_head;
 812         cache_head.lru_next = cache_head.lru_prev = &cache_head;
 813
 814         Cmd_AddCommand ("flush", Cache_Flush);
 815 }
 816
 817 /*
 818 ==============
 819 Cache_Free
 820
 821 Frees the memory and removes it from the LRU list
 822 ==============
 823 */
 824 void Cache_Free (cache_user_t *c)
 825 {
 826         cache_system_t  *cs;
 827
 828         if (!c->data)
 829                 Sys_Error ("Cache_Free: not allocated");
 830
 831         cs = ((cache_system_t *)c->data) - 1;
 832
 833         cs->prev->next = cs->next;
 834         cs->next->prev = cs->prev;
 835         cs->next = cs->prev = NULL;
 836
 837         c->data = NULL;
 838
 839         Cache_UnlinkLRU (cs);
 840 }
 841
 842
 843
 844 /*
 845 ==============
 846 Cache_Check
 847 ==============
 848 */
 849 void *Cache_Check (cache_user_t *c)
 850 {
 851         cache_system_t  *cs;
 852
 853         if (!c->data)
 854                 return NULL;
 855
 856         cs = ((cache_system_t *)c->data) - 1;
 857
 858 // move to head of LRU
 859         Cache_UnlinkLRU (cs);
 860         Cache_MakeLRU (cs);
 861
 862         return c->data;
 863 }
 864
 865
 866 /*
 867 ==============
 868 Cache_Alloc
 869 ==============
 870 */
 871 void *Cache_Alloc (cache_user_t *c, int size, char *name)
 872 {
 873         cache_system_t  *cs;
 874
 875         if (c->data)
 876                 Sys_Error ("Cache_Alloc: allready allocated");
 877
 878         if (size <= 0)
 879                 Sys_Error ("Cache_Alloc: size %i", size);
 880
 881         size = (size + sizeof(cache_system_t) + 15) & ~15;
 882
 883 // find memory for it
 884         while (1)
 885         {
 886                 cs = Cache_TryAlloc (size, false);
 887                 if (cs)
 888                 {
 889                         strncpy (cs->name, name, sizeof(cs->name)-1);
 890                         c->data = (void *)(cs+1);
 891                         cs->user = c;
 892                         break;
 893                 }
 894
 895         // free the least recently used cahedat
 896                 if (cache_head.lru_prev == &cache_head)
 897                         Sys_Error ("Cache_Alloc: out of memory");
 898                                                                                                         // not enough memory at all
 899                 Cache_Free ( cache_head.lru_prev->user );
 900         }
 901
 902         return Cache_Check (c);
 903 }
 904
 905 //============================================================================
 906
 907
 908 /*
 909 ========================
 910 Memory_Init
 911 ========================
 912 */
 913 void Memory_Init (void *buf, int size)
 914 {
 915         int p;
 916         int zonesize = DYNAMIC_SIZE;
 917
 918         hunk_base = buf;
 919         hunk_size = size;
 920         hunk_low_used = 0;
 921         hunk_high_used = 0;
 922
 923         Cache_Init ();
 924         p = COM_CheckParm ("-zone");
 925         if (p)
 926         {
 927                 if (p < com_argc-1)
 928                         zonesize = Q_atoi (com_argv[p+1]) * 1024;
 929                 else
 930                         Sys_Error ("Memory_Init: you must specify a size in KB after -zone");
 931         }
 932         mainzone = Hunk_AllocName (zonesize, "zone" );
 933         Z_ClearZone (mainzone, zonesize);
 934 }
 935