aboutsummaryrefslogtreecommitdiffstats
path: root/src/gos/gos_x_heap.c
blob: 813d0199cc42995fbce0d55ff17db1aa1c344df6 (plain)
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/*
 * This file is subject to the terms of the GFX License. If a copy of
 * the license was not distributed with this file, you can obtain one at:
 *
 *              http://ugfx.org/license.html
 */

#include "../../gfx.h"

#if GOS_NEED_X_HEAP

#include <string.h>				// Prototype for memcpy()


#if GFX_OS_HEAP_SIZE == 0
	#include <stdlib.h>				// Prototype for malloc(), realloc() and free()

	void _gosHeapInit(void) {
	}
	void *gfxAlloc(size_t sz) {
		return malloc(sz);
	}

	void *gfxRealloc(void *ptr, size_t oldsz, size_t newsz) {
		(void) oldsz;
		return realloc(ptr, newsz);
	}

	void gfxFree(void *ptr) {
		free(ptr);
	}

#else

	// Slot structure - user memory follows
	typedef struct memslot {
		size_t			sz;			// Includes the size of this memslot.
		} memslot;

	// Free Slot - immediately follows the memslot structure
	typedef struct freeslot {
		memslot *nextfree;			// The next free slot
	} freeslot;

	#define GetSlotSize(sz)		((((sz) + (sizeof(freeslot) - 1)) & ~(sizeof(freeslot) - 1)) + sizeof(memslot))
	#define NextFree(pslot)		((freeslot *)Slot2Ptr(pslot))->nextfree
	#define Ptr2Slot(p)			((memslot *)(p) - 1)
	#define Slot2Ptr(pslot)		((pslot)+1)

	static memslot *			freeSlots;
	static char					heap[GFX_OS_HEAP_SIZE];

	void _gosHeapInit(void) {
		gfxAddHeapBlock(heap, GFX_OS_HEAP_SIZE);
	}

	void gfxAddHeapBlock(void *ptr, size_t sz) {
		if (sz < sizeof(memslot)+sizeof(freeslot))
			return;

		((memslot *)ptr)->sz = sz;
		gfxFree(Slot2Ptr((memslot *)ptr));
	}

	void *gfxAlloc(size_t sz) {
		register memslot *prev, *p, *pnew;

		if (!sz) return 0;
		sz = GetSlotSize(sz);
		for (prev = 0, p = freeSlots; p != 0; prev = p, p = NextFree(p)) {
			// Loop till we have a block big enough
			if (p->sz < sz)
				continue;
				
			// Can we save some memory by splitting this block?
			if (p->sz >= sz + sizeof(memslot)+sizeof(freeslot)) {
				pnew = (memslot *)((char *)p + sz);
				pnew->sz = p->sz - sz;
				p->sz = sz;
				NextFree(pnew) = NextFree(p);
				NextFree(p) = pnew;
			}
			
			// Remove it from the free list
			if (prev)
				NextFree(prev) = NextFree(p);
			else
				freeSlots = NextFree(p);
				
			// Return the result found
			return Slot2Ptr(p);
		}
		// No slots large enough
		return 0;
	}

	void *gfxRealloc(void *ptr, size_t oldsz, size_t sz) {
		register memslot *prev, *p, *pfree;
		(void) oldsz;

		if (!ptr)
			return gfxAlloc(sz);
		if (!sz) {
			gfxFree(ptr);
			return 0;
		}

		p = Ptr2Slot(ptr);
		sz = GetSlotSize(sz);

		// If the next slot is free (and contiguous) merge it into this one
		for (prev = 0, pfree = freeSlots; pfree != 0; prev = pfree, pfree = NextFree(pfree)) {
			if (pfree == (memslot *)((char *)p + p->sz)) {
				p->sz += pfree->sz;
				if (prev)
					NextFree(prev) = NextFree(pfree);
				else
					freeSlots = NextFree(pfree);
				break;
			}
		}

		// If this block is large enough we are nearly done
		if (sz < p->sz) {
			// Can we save some memory by splitting this block?
			if (p->sz >= sz + sizeof(memslot)+sizeof(freeslot)) {
				pfree = (memslot *)((char *)p + sz);
				pfree->sz = p->sz - sz;
				p->sz = sz;
				NextFree(pfree) = freeSlots;
				freeSlots = pfree;
			}
			return Slot2Ptr(p);
		}

		// We need to do this the hard way
		pfree = gfxAlloc(sz);
		if (pfree)
			return 0;
		memcpy(pfree, ptr, p->sz - sizeof(memslot));
		gfxFree(ptr);
		return pfree;
	}

	void gfxFree(void *ptr) {
		register memslot *prev, *p, *pfree;

		if (!ptr)
			return;

		p = Ptr2Slot(ptr);

		// Find a free slot that is contiguous precceding and merge it into us
		for (prev = 0, pfree = freeSlots; pfree != 0; prev = pfree, pfree = NextFree(pfree)) {
			if (p == (memslot *)((char *)pfree + pfree->sz)) {
				pfree->sz += p->sz;
				if (prev)
					NextFree(prev) = NextFree(pfree);
				else
					freeSlots = NextFree(pfree);
				p = pfree;
				break;
			}
		}
		
		// Find a free slot that is contiguous after and merge it into this one
		for (prev = 0, pfree = freeSlots; pfree != 0; prev = pfree, pfree = NextFree(pfree)) {
			if (pfree == (memslot *)((char *)p + p->sz)) {
				p->sz += pfree->sz;
				if (prev)
					NextFree(prev) = NextFree(pfree);
				else
					freeSlots = NextFree(pfree);
				break;
			}
		}

		// Add it into the free chain
		NextFree(p) = freeSlots;
		freeSlots = p;
	}
#endif

#endif /* GOS_NEED_X_HEAP */

#if GFX_EMULATE_MALLOC
	#include <stdlib.h>

	void* malloc(size_t size) {
		return gfxAlloc(size);
	}
	void free(void *ptr) {
		gfxFree(ptr);
	}
#endif