Mercurial > repos > rhope
comparison runtime/fixed_alloc.c @ 62:b218af069da7
merge
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Sat, 10 Oct 2009 16:43:37 -0400 |
parents | 1b86a1ee500a |
children | a24eb366195c |
comparison
equal
deleted
inserted
replaced
61:fa24ef3b026f | 62:b218af069da7 |
---|---|
1 #include "fixed_alloc.h" | |
2 #include <stdlib.h> | |
3 | |
4 uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE]; | |
5 | |
6 void fixed_alloc_init() | |
7 { | |
8 int i; | |
9 for(i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; ++i) | |
10 max_free[i] = (BLOCK_SIZE - sizeof(mem_block)+1)*8/((i*STRIDE+MIN_SIZE)*8+1); | |
11 } | |
12 | |
13 mem_manager * new_mem_manager() | |
14 { | |
15 int i; | |
16 mem_manager * ret = malloc(sizeof(mem_manager)); | |
17 memset(ret, 0, sizeof(mem_manager)); | |
18 return ret; | |
19 } | |
20 | |
21 void * falloc(size_t size, mem_manager * manager) | |
22 { | |
23 uint16_t i,bit; | |
24 uint16_t bucket; | |
25 mem_block * block,*temp; | |
26 if(size > MAX_SIZE) | |
27 return malloc(size); | |
28 //puts("falloc"); | |
29 size = ADJUST_SIZE(size); | |
30 bucket = (size-MIN_SIZE)/STRIDE; | |
31 block = manager->inuse[bucket]; | |
32 if(!block) | |
33 { | |
34 block = manager->freelist; | |
35 if(block) | |
36 { | |
37 --manager->freecount; | |
38 manager->freelist = block->next; | |
39 } | |
40 else | |
41 { | |
42 block = block_alloc(BLOCK_SIZE); | |
43 } | |
44 manager->inuse[bucket] = block; | |
45 block->next = NULL; | |
46 block->last = NULL; | |
47 block->numfree = max_free[bucket]; | |
48 block->firstfree = 0; | |
49 memset(block->bitmap, 0xFF, max_free[bucket]/8+1); | |
50 } | |
51 //printf("block: %X,numfree: %d, firstfree: %d, maxfree: %d\n", block, block->numfree, block->firstfree, max_free[bucket]); | |
52 /*if(block->numfree > max_free[bucket]) | |
53 { | |
54 puts("uh oh!"); | |
55 exit(1); | |
56 }*/ | |
57 //find first free | |
58 i = block->firstfree; | |
59 while(!block->bitmap[i]) | |
60 ++i; | |
61 //printf("i:%d,bitmap:%X\n", i, block->bitmap[i]); | |
62 bit = 0; | |
63 while(!((1 << bit) & block->bitmap[i])) | |
64 ++bit; | |
65 //update free bitmask | |
66 block->bitmap[i] ^= 1 << bit; | |
67 //If current bitmap has no more free elements, set firstfree to the next bitmap | |
68 if(!block->bitmap[i]) | |
69 block->firstfree = i+1; | |
70 else | |
71 block->firstfree = i; | |
72 --block->numfree; | |
73 if(!block->numfree) | |
74 { | |
75 //Remove from linked list if there are no more free elements | |
76 manager->inuse[bucket] = block->next; | |
77 if(block->next) | |
78 block->next->last = block->last; | |
79 } | |
80 i = i*8+bit; | |
81 //printf("%X\n", ((char *)block)+BLOCK_SIZE-((i+1)*size)); | |
82 return (void *)(((char *)block)+BLOCK_SIZE-((i+1)*size)); | |
83 } | |
84 | |
85 void ffree(void * ptr, size_t size, mem_manager * manager) | |
86 { | |
87 mem_block * block,*temp; | |
88 uint16_t i,bit,bucket; | |
89 if(size > MAX_SIZE) | |
90 { | |
91 free(ptr); | |
92 return; | |
93 } | |
94 //puts("ffree"); | |
95 size = ADJUST_SIZE(size); | |
96 block = GET_BLOCK(ptr); | |
97 i = (((((char *)block) + BLOCK_SIZE) - ((char *)ptr))/size)-1; | |
98 bit = i & 0x7; | |
99 i = (i&0xFFFFFFF8) >> 3; | |
100 //printf("ptr:%X,block:%X,i:%d,bit:%d\n", ptr,block,bit,i); | |
101 block->bitmap[i] |= 1 << bit; | |
102 if(i < block->firstfree) | |
103 block->firstfree = i; | |
104 ++block->numfree; | |
105 bucket = (size-MIN_SIZE)/STRIDE; | |
106 //printf("numfree:%d,max_free:%d,last:%X,next:%X\n", block->numfree, max_free[bucket], block->last, block->next); | |
107 /*if(block->numfree > max_free[bucket]) | |
108 { | |
109 puts("uh oh!"); | |
110 exit(1); | |
111 }*/ | |
112 if(block->numfree == max_free[bucket]) | |
113 { | |
114 //Block is now unused, remove it from the inuse list | |
115 if(block->last) | |
116 block->last->next = block->next; | |
117 else | |
118 manager->inuse[bucket] = block->next; | |
119 if(block->next) | |
120 block->next->last = block->last; | |
121 if(manager->freecount == MAX_FREE) | |
122 block_free(block, BLOCK_SIZE); | |
123 else | |
124 { | |
125 block->next = manager->freelist; | |
126 manager->freelist = block; | |
127 ++manager->freecount; | |
128 } | |
129 } else if(block->numfree == 1) { | |
130 //Block was previously full, add it to the inuse list | |
131 block->next = manager->inuse[bucket]; | |
132 block->last = NULL; | |
133 manager->inuse[bucket] = block; | |
134 if(block->next) | |
135 block->next->last = block; | |
136 } else if(block->next && block->next->numfree < block->numfree) { | |
137 //We want to use more filled blockes before less filled ones | |
138 //so we can return empty ones to the OS more often | |
139 //so if we now have more free nodes in this block than the | |
140 //next one swap them | |
141 temp = block->next; | |
142 block->next = temp->next; | |
143 temp->last = block->last; | |
144 block->last = temp; | |
145 temp->next = block; | |
146 if(block->next) | |
147 block->next->last = block; | |
148 if(temp->last) | |
149 temp->last->next = temp; | |
150 else | |
151 manager->inuse[bucket] = temp; | |
152 } | |
153 } |