1 #include "BSprivate.h"
2
3 /*
4 Space management routines
5 */
6
7 /*
8 Allocator for large numbers of small blocks of equal size:
9
10 Data is double alligned, as is expected by most routines.
11
12 Data structure:
13 A list of blocks.
14 */
15
16 typedef struct __BSMBlock {
17 int base_size;
18 int num_units;
19 double *top, *bottom; /* bounds of memory for this block */
20 /* used for free'ing quickly */
21 struct __BSMBlock *next; /* Pointer to next BSMBlock */
22 double *free_blocks;
23 int num_allocated;
24 double v; /* Dummy for top */
25 } BSMBlock;
26
27 /*
28 Create a new block of base_size in size
29 */
BSsbinit(long base_size,int num_units)30 BSMBlock *BSsbinit(long base_size, int num_units)
31 {
32 BSMBlock *B;
33 double *tmp, *oldtmp;
34 double **ptr;
35 int true_base_size, test_size, true_size;
36 int i;
37
38 true_base_size = (base_size + sizeof(double) - 1) / sizeof(double);
39 /* double aligned */
40 true_base_size++; /* account for next pointers */
41
42 /* try to find the next highest power of two */
43 test_size = (num_units*true_base_size)*sizeof(double) + sizeof(BSMBlock);
44 true_size = sizeof(double);
45 while (true_size-1 < test_size) {
46 true_size *= 2;
47 }
48 true_size--;
49 num_units = (true_size - sizeof(BSMBlock)) / sizeof(double);
50 num_units /= true_base_size;
51
52 MY_MALLOCN(B,(BSMBlock *),true_size,1);
53 B->base_size = base_size;
54 B->num_units = num_units;
55 B->top = &B->v;
56 B->bottom = &(B->top[num_units*true_base_size]);
57 B->num_allocated = 0;
58 B->next = NULL;
59
60 /* set up the free list */
61 tmp = B->top;
62 B->free_blocks = tmp;
63 oldtmp = tmp;
64 for (i=1;i<num_units;i++) {
65 tmp += true_base_size;
66 ptr = (double **) oldtmp;
67 ptr[0] = tmp; /* set next of previous ptr to current */
68 oldtmp = tmp;
69 }
70 ptr = (double **) tmp;
71 ptr[0] = NULL;
72 return(B);
73 }
74
BSsbmalloc(BSMBlock ** B)75 double *BSsbmalloc(BSMBlock **B )
76 {
77 double *p;
78 BSMBlock *BB = *B;
79 BSMBlock *tmp_next, *prev;
80 double **ptr;
81 int found;
82
83 /* Find a block with free space, or create one */
84 found = 0;
85 prev = NULL;
86 while ((BB != NULL) && (!found)) {
87 if (BB->free_blocks != NULL) {
88 found = 1;
89 } else {
90 prev = BB;
91 BB = BB->next;
92 }
93 }
94 if (found == 0) {
95 BB = (*B);
96 /* get new block */
97 (*B) = BSsbinit( BB->base_size, BB->num_units*2 ); CHKERRN(0);
98 if ((*B) == NULL) return(NULL);
99 (*B)->next = BB;
100 BB = (*B);
101 } else if (BB != (*B)) {
102 tmp_next = BB->next;
103 BB->next = (*B);
104 prev->next = tmp_next;
105 (*B) = BB;
106 }
107
108 BB->num_allocated++;
109 ptr = (double **) BB->free_blocks;
110 p = &(BB->free_blocks[1]);
111 BB->free_blocks = ptr[0];
112 return(p);
113 }
114
115 /*
116 Free a block allocated with sbmalloc
117 */
BSsbfree(double * p,BSMBlock ** B)118 void BSsbfree(double *p, BSMBlock **B)
119 {
120 BSMBlock *t, *prev;
121 double **ptr;
122
123 prev= NULL;
124 t = *B;
125 while (t != NULL) {
126 /* is p in this block ? */
127 if (p >= t->top && p< t->bottom) {
128 t->num_allocated--;
129 ptr = (double **) (p - 1);
130 ptr[0] = t->free_blocks;
131 t->free_blocks = (double *) ptr;
132 /* we don't free the main blocks, that is done when BSmem_clean */
133 /* is called to clean all the blocks up */
134 /* move this block to the front */
135 if (prev != NULL) {
136 prev->next = t->next;
137 t->next = (*B);
138 (*B) = t;
139 }
140 return;
141 }
142 prev = t;
143 t = (BSMBlock *)t->next;
144 }
145 MY_SETERRC(MEM_ERROR,"Bad free, could not find block\n");
146 }
147
BSmem_clean(BSMBlock ** B)148 void BSmem_clean(BSMBlock **B)
149 {
150 BSMBlock *cur, *prev;
151
152 cur = *B;
153 while (cur != NULL) {
154 prev = cur;
155 cur = cur->next;
156 MY_FREE(prev);
157 }
158 (*B) = NULL;
159 }
160