-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmemsys.c
162 lines (142 loc) · 7.79 KB
/
memsys.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/*----------------------------------------------------------------------
File : memsys.c
Contents: memory management system for equally sized (small) objects
Author : Christian Borgelt
History : 2004.12.10 file created from fpgrowth.c
2008.01.23 counting of used objects added
2008.11.18 recording of maximum number of used blocks added
2010.07.30 arrays of unassigned objects added, ms_clear()
2010.08.03 state stack, functions ms_push(), ms_pop() added
2010.09.07 persistent allocation error indicator added
2010.12.07 several explicit type casts added (for C++)
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "memsys.h"
#ifdef STORAGE
#include "storage.h"
#endif
/*----------------------------------------------------------------------
Main Functions
----------------------------------------------------------------------*/
MEMSYS* ms_create (size_t size, size_t cnt)
{ /* --- create a memory system */
MEMSYS *ms; /* created memory system */
assert((cnt > 0) && (size > 0)); /* check the function arguments */
ms = (MEMSYS*)malloc(sizeof(MEMSYS));
if (!ms) return NULL; /* create a memory management system */
ms->size = (size+sizeof(void*)-1) /sizeof(void*);
/* ms->size: the size of an object in void* units (rounded up) */
ms->mbsz = cnt *ms->size +2; /* 2: successor and predecessor */
/* ms->mbsz: the size of a memory block in void* units */
ms->free = ms->next = ms->curr = ms->list = NULL;
ms->used = ms->umax = 0; /* initialize the variables */
ms->cap = ms->top = ms->err = 0; ms->stack = NULL;
return ms; /* return the created memory system */
} /* ms_create() */
/*--------------------------------------------------------------------*/
void ms_delete (MEMSYS *ms)
{ /* --- delete a memory system */
void **b; /* buffers for deallocation */
assert(ms); /* check the function argument */
for (b = ms->list; b; b = ms->list) {
ms->list = (void**)*b; free(b); }
while (ms->list) { /* delete the list of blocks */
b = ms->list; ms->list = (void**)*b; free(b); }
if (ms->stack) free(ms->stack); /* delete a possible stack */
free(ms); /* and the base structure */
} /* ms_delete() */
/*--------------------------------------------------------------------*/
void ms_clear (MEMSYS *ms, int shrink)
{ /* --- clear a memory system */
void **b; /* buffer for a memory block */
if (!(b = ms->list)) /* if there are no memory blocks, */
ms->next = ms->curr = NULL; /* clear the unassigned objects */
else { /* if there are memory blocks, */
if (shrink) { /* if to shrink the memory block list */
while (*b) { ms->list = (void**)*b; free(b); b = ms->list; }
b[1] = NULL; /* delete all but the last block */
} /* and clear its successor pointer */
ms->curr = b; /* set the only memory block that */
ms->next = b+2; /* is left as the current block */
} /* and set next unassigned object */
ms->free = NULL; /* clear the list of free objects */
ms->used = ms->umax = 0; /* there are no used objects and */
ms->cap = ms->top = 0; /* the memory state stack is empty */
ms->err = 0; /* clear the error indicator */
} /* ms_clear() */
/*--------------------------------------------------------------------*/
void* ms_alloc (MEMSYS *ms)
{ /* --- allocate an object */
void **obj; /* allocated object */
void **b; /* next/new memory block */
assert(ms); /* check the function argument */
if ((obj = ms->free)) { /* if there is a free object, */
++ms->used; /* count the object as used, */
ms->free = (void**)*(void**)obj;
return obj; /* remove it from the free list */
} /* and return it */
/* The new value of ms->used cannot exceed ms->umax, because all */
/* objects on the free list have been in use before and thus have */
/* already been counted for the maximum number of used objects. */
if (ms->next) /* if there are new objects, */
obj = ms->next; /* get the next new object */
else if (((b = ms->curr)) && b[1]) {
ms->curr = b = (void**)b[1];/* if there is a successor block */
ms->next = obj = b+2; } /* and get its first object */
else { /* if there is no new object left */
b = (void**)malloc(ms->mbsz *sizeof(void*));
if (!b) { ms->err = -1; return NULL; }
b[1] = NULL; /* allocate a new memory block and */
b[0] = ms->list; /* add it at the end of the list */
if (ms->list) ms->list[1] = b;
ms->list = ms->curr = b; /* make the block the current one */
ms->next = obj = b+2; /* and get the first object */
} /* in this memory block */
ms->next += ms->size; /* advance the object array position */
if (ms->next >= ms->curr +ms->mbsz)
ms->next = NULL; /* check for end of object array */
if (++ms->used > ms->umax) /* count the allocated object */
ms->umax = ms->used; /* and update the maximum */
return obj; /* return the retrieved object */
} /* ms_alloc() */
/*--------------------------------------------------------------------*/
void ms_free (MEMSYS *ms, void *obj)
{ /* --- deallocate an f.p. tree node */
assert(ms && obj); /* check the function arguments */
assert(ms->used > 0); /* check the number of used objects */
*(void**)obj = ms->free; /* insert the freed object */
ms->free = (void**)obj; /* at the head of the free list */
ms->used--; /* count the deallocated object */
} /* ms_free() */
/*--------------------------------------------------------------------*/
int ms_push (MEMSYS *ms)
{ /* --- store the current state */
int n; /* new stack size */
MSSTATE *s; /* buffer for reallocation */
assert(ms && !ms->free); /* check the function argument */
if (ms->top >= ms->cap) { /* if the state stack is full */
n = ms->cap +((ms->cap > 32) ? ms->cap >> 1 : 32);
s = (MSSTATE*)realloc(ms->stack, n *sizeof(MSSTATE));
if (!s) return -1; /* enlarge the state stack */
ms->stack = s; ms->cap = n; /* and set the enlarged stack */
} /* and its new size */
s = ms->stack +ms->top; /* get the next free stack element */
s->next = ms->next; /* not the current state */
s->curr = ms->curr; /* of the memory system */
s->used = ms->used;
return ++ms->top; /* return the new stack size */
} /* ms_push() */
/*--------------------------------------------------------------------*/
int ms_pop (MEMSYS *ms)
{ /* --- retrieve the last state */
MSSTATE *s; /* to access the top stack element */
assert(ms && !ms->free); /* check the function argument */
if (ms->top <= 0) return -1; /* check for an empty stack */
s = ms->stack +(--ms->top); /* get the top stack element */
ms->next = s->next; /* restore the last state */
ms->curr = s->curr; /* of the memory system */
ms->used = s->used;
return ms->top; /* return the new stack size */
} /* ms_pop() */