summaryrefslogtreecommitdiff
path: root/apps/plugins/sdl/progs/quake/zone.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/sdl/progs/quake/zone.c')
-rw-r--r--apps/plugins/sdl/progs/quake/zone.c935
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 0000000000..e30d7f847f
--- /dev/null
+++ b/apps/plugins/sdl/progs/quake/zone.c
@@ -0,0 +1,935 @@
1/*
2Copyright (C) 1996-1997 Id Software, Inc.
3
4This program is free software; you can redistribute it and/or
5modify it under the terms of the GNU General Public License
6as published by the Free Software Foundation; either version 2
7of the License, or (at your option) any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13See the GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License
16along with this program; if not, write to the Free Software
17Foundation, 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
29typedef 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
38typedef 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
45void Cache_FreeLow (int new_low_hunk);
46void Cache_FreeHigh (int new_high_hunk);
47
48
49/*
50==============================================================================
51
52 ZONE MEMORY ALLOCATION
53
54There is never any space between memblocks, and there will never be two
55contiguous free memblocks.
56
57The rover can be left pointing at a non-empty block
58
59The zone calls are pretty much only used for small strings and structures,
60all big things are allocated on the hunk.
61==============================================================================
62*/
63
64memzone_t *mainzone;
65
66void Z_ClearZone (memzone_t *zone, int size);
67
68
69/*
70========================
71Z_ClearZone
72========================
73*/
74void 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========================
96Z_Free
97========================
98*/
99void 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========================
139Z_Malloc
140========================
141*/
142void *Z_Malloc (int size)
143{
144 void *buf;
145
146Z_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
155void *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========================
216Z_Print
217========================
218*/
219void 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========================
244Z_CheckHeap
245========================
246*/
247void 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
268typedef struct
269{
270 int sentinal;
271 int size; // including sizeof(hunk_t), -1 = not allocated
272 char name[8];
273} hunk_t;
274
275byte *hunk_base;
276int hunk_size;
277
278int hunk_low_used;
279int hunk_high_used;
280
281qboolean hunk_tempactive;
282int hunk_tempmark;
283
284void R_FreeTextures (void);
285
286/*
287==============
288Hunk_Check
289
290Run consistancy and sentinal trahing checks
291==============
292*/
293void 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==============
309Hunk_Print
310
311If "all" is specified, every single allocation is printed.
312Otherwise, allocations with the same name will be totaled up before printing.
313==============
314*/
315void 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===================
396Hunk_AllocName
397===================
398*/
399void *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===================
431Hunk_Alloc
432===================
433*/
434void *Hunk_Alloc (int size)
435{
436 return Hunk_AllocName (size, "unknown");
437}
438
439int Hunk_LowMark (void)
440{
441 return hunk_low_used;
442}
443
444void 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
452int 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
463void 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===================
479Hunk_HighAllocName
480===================
481*/
482void *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=================
523Hunk_TempAlloc
524
525Return space from the top of the hunk
526=================
527*/
528void *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
552CACHE MEMORY
553
554===============================================================================
555*/
556
557typedef 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
566cache_system_t *Cache_TryAlloc (int size, qboolean nobottom);
567
568cache_system_t cache_head;
569
570/*
571===========
572Cache_Move
573===========
574*/
575void 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============
601Cache_FreeLow
602
603Throw things out until the hunk can be expanded to the given point
604============
605*/
606void 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============
623Cache_FreeHigh
624
625Throw things out until the hunk can be expanded to the given point
626============
627*/
628void 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
650void 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
661void 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============
674Cache_TryAlloc
675
676Looks for a free block of memory between the high and low hunk marks
677Size should already include the header and padding
678============
679*/
680cache_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============
754Cache_Flush
755
756Throw everything out, so new data will be demand cached
757============
758*/
759void 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============
768Cache_Print
769
770============
771*/
772void 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============
784Cache_Report
785
786============
787*/
788void 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============
795Cache_Compact
796
797============
798*/
799void Cache_Compact (void)
800{
801}
802
803/*
804============
805Cache_Init
806
807============
808*/
809void 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==============
819Cache_Free
820
821Frees the memory and removes it from the LRU list
822==============
823*/
824void 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==============
846Cache_Check
847==============
848*/
849void *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==============
868Cache_Alloc
869==============
870*/
871void *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========================
910Memory_Init
911========================
912*/
913void 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