kHlpBareHeap.c

Last change on this file was 29, checked in by bird, 16 years ago
Finally got around execute the switch to the MIT license.
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 20.0 KB

Line
1	/* $Id: kHlpBareHeap.c 29 2009-07-01 20:30:29Z bird $ */
2	/** @file
3	* kHlpBare - Heap.
4	*/
5
6	/*
7	* Copyright (c) 2006-2007 Knut St. Osmundsen <[email protected]>
8	*
9	* Permission is hereby granted, free of charge, to any person
10	* obtaining a copy of this software and associated documentation
11	* files (the "Software"), to deal in the Software without
12	* restriction, including without limitation the rights to use,
13	* copy, modify, merge, publish, distribute, sublicense, and/or sell
14	* copies of the Software, and to permit persons to whom the
15	* Software is furnished to do so, subject to the following
16	* conditions:
17	*
18	* The above copyright notice and this permission notice shall be
19	* included in all copies or substantial portions of the Software.
20	*
21	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22	* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
23	* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24	* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
25	* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
26	* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
28	* OTHER DEALINGS IN THE SOFTWARE.
29	*/
30
31	#define KHLPHEAP_STRICT
32
33	/*******************************************************************************
34	* Header Files *
35	*******************************************************************************/
36	#include <k/kHlpAlloc.h>
37	#include <k/kHlpString.h>
38	#include <k/kHlpAssert.h>
39
40	#if K_OS == K_OS_OS2
41	# define INCL_BASE
42	# define INCL_ERRORS
43	# include <os2.h>
44
45	#elif K_OS == K_OS_WINDOWS
46	# include <Windows.h>
47
48	#else
49	# include <k/kHlpAlloc.h>
50	#endif
51
52
53	/*******************************************************************************
54	* Structures and Typedefs *
55	*******************************************************************************/
56	/**
57	* A heap block.
58	*/
59	typedef struct KHLPHEAPBLOCK
60	{
61	/** Next block in the global list. */
62	struct KHLPHEAPBLOCK *pNext;
63	/** Previous block in the global list. */
64	struct KHLPHEAPBLOCK *pPrev;
65	/** The size of this block including this header. */
66	KSIZE cb;
67	/** The flags. */
68	KSIZE fFlags;
69	} KHLPHEAPBLOCK, *PKHLPHEAPBLOCK;
70
71	/** Indicates whether the block is free (set) or allocated (clear). */
72	#define KHLPHEAPBLOCK_FLAG_FREE ((KSIZE)1)
73	/** Valid flag mask. */
74	#define KHLPHEAPBLOCK_FLAG_MASK ((KSIZE)1)
75
76	/** Checks if the block is freed. */
77	#define KHLPHEAPBLOCK_IS_FREE(pB) ( (pB)->fFlags & KHLPHEAPBLOCK_FLAG_FREE )
78	/** Check if the block is allocated. */
79	#define KHLPHEAPBLOCK_IS_ALLOCATED(pB) !KHLPHEAPBLOCK_IS_FREE(pB)
80	/** Checks if the two blocks are adjacent.
81	* Assumes pB1 < pB2. */
82	#define KHLPHEAPBLOCK_IS_ADJACENT(pB1, pB2) \
83	( ((KUPTR)(pB1) + (pB1)->cb) == (KUPTR)(pB2) )
84
85	/** The block alignment. */
86	#define KHLPHEAPBLOCK_ALIGNMENT sizeof(KHLPHEAPBLOCK)
87
88	/** @def KHLPHEAP_ASSERT
89	* Heap assertion. */
90	/** @def KHLPHEAP_ASSERT_BLOCK
91	* Assert that a heap block is valid. */
92	/** @def KHLPHEAP_ASSERT_FREE
93	* Assert that a heap free block is valid. */
94	#ifdef KHLPHEAP_STRICT
95	# define KHLPHEAP_ASSERT(expr) kHlpAssert(expr)
96
97	# define KHLPHEAP_ASSERT_BLOCK(pHeap, pBlock) \
98	do { \
99	KHLPHEAP_ASSERT(!((pBlock)->fFlags & ~KHLPHEAPBLOCK_FLAG_MASK)); \
100	KHLPHEAP_ASSERT(!((pBlock)->cb & (KHLPHEAPBLOCK_ALIGNMENT - 1))); \
101	KHLPHEAP_ASSERT((KUPTR)(pBlock)->pPrev < (KUPTR)(pBlock)); \
102	KHLPHEAP_ASSERT((KUPTR)(pBlock)->pNext > (KUPTR)(pBlock) \|\| !(pBlock)->pNext); \
103	} while (0)
104
105	# define KHLPHEAP_ASSERT_FREE(pHeap, pFree) \
106	do { \
107	KHLPHEAP_ASSERT_BLOCK(pHeap, &(pFree)->Core); \
108	KHLPHEAP_ASSERT((KUPTR)(pFree)->pPrev < (KUPTR)(pFree)); \
109	KHLPHEAP_ASSERT((KUPTR)(pFree)->pNext > (KUPTR)(pFree) \|\| !(pFree)->pNext); \
110	} while (0)
111
112	#else
113	# define KHLPHEAP_ASSERT(expr) do { } while (0)
114	# define KHLPHEAP_ASSERT_BLOCK(pH, pB) do { } while (0)
115	# define KHLPHEAP_ASSERT_FREE(pH, pF) do { } while (0)
116	#endif
117
118
119	/**
120	* A free heap block.
121	*/
122	typedef struct KHLPHEAPFREE
123	{
124	/** The core bit which we have in common with used blocks. */
125	KHLPHEAPBLOCK Core;
126	/** The next free block. */
127	struct KHLPHEAPFREE *pNext;
128	/** The previous free block. */
129	struct KHLPHEAPFREE *pPrev;
130	} KHLPHEAPFREE, *PKHLPHEAPFREE;
131
132
133	/**
134	* A heap segment.
135	*/
136	typedef struct KHLPHEAPSEG
137	{
138	/** The base address of the segment. */
139	void *pvBase;
140	/** The length of the segment (in bytes). */
141	KSIZE cb;
142	} KHLPHEAPSEG, *PKHLPHEAPSEG;
143
144	/**
145	* Bundle of heap segments.
146	*/
147	typedef struct KHLPHEAPSEGS
148	{
149	/** Pointer to the next segment bundle. */
150	struct KHLPHEAPSEGS *pNext;
151	/** The number of segments used. */
152	KU32 cSegs;
153	/** Array of chunks. */
154	KHLPHEAPSEG aSegs[64];
155	} KHLPHEAPSEGS, *PKHLPHEAPSEGS;
156
157
158	/**
159	* Heap anchor block.
160	*/
161	typedef struct KHLPHEAPANCHOR
162	{
163	/** Head of the block list. */
164	PKHLPHEAPBLOCK pHead;
165	/** Tail of the block list. */
166	PKHLPHEAPBLOCK pTail;
167	/** Head of the free list. */
168	PKHLPHEAPFREE pFreeHead;
169	/** Head segment bundle.
170	* The order of this list is important, but a bit peculiar.
171	* Logically, SegsHead::pNext is the tail pointer. */
172	KHLPHEAPSEGS SegsHead;
173	} KHLPHEAPANCHOR, *PKHLPHEAPANCHOR;
174
175
176
177	/*******************************************************************************
178	* Global Variables *
179	*******************************************************************************/
180	/** The heap anchor block. */
181	static KHLPHEAPANCHOR g_Heap;
182
183
184	/*******************************************************************************
185	* Internal Functions *
186	*******************************************************************************/
187	static int khlpHeapInit(PKHLPHEAPANCHOR pHeap);
188	static void khlpHeapDelete(PKHLPHEAPANCHOR pHeap);
189	static void * khlpHeapAlloc(PKHLPHEAPANCHOR pHeap, KSIZE cb);
190	static void khlpHeapFree(PKHLPHEAPANCHOR pHeap, void *pv);
191	static KSIZE khlpHeapBlockSize(PKHLPHEAPANCHOR pHeap, void *pv);
192	static void khlpHeapDonate(PKHLPHEAPANCHOR pHeap, void *pv, KSIZE cb);
193	static int khlpHeapSegAlloc(PKHLPHEAPSEG pSeg, KSIZE cb);
194	static void khlpHeapSegFree(PKHLPHEAPSEG pSeg);
195
196
197	/**
198	* Initializes the kLdr heap.
199	*
200	* @returns 0 on success, non-zero OS specific status code on failure.
201	*/
202	KHLP_DECL(int) kHlpHeapInit(void)
203	{
204	return khlpHeapInit(&g_Heap);
205	}
206
207
208	/**
209	* Terminates the kLdr heap.
210	*/
211	KHLP_DECL(void) kHlpHeapTerm(void)
212	{
213	khlpHeapDelete(&g_Heap);
214	}
215
216
217	KHLP_DECL(void *) kHlpAlloc(KSIZE cb)
218	{
219	return khlpHeapAlloc(&g_Heap, cb);
220	}
221
222
223	KHLP_DECL(void *) kHlpAllocZ(KSIZE cb)
224	{
225	void *pv = khlpHeapAlloc(&g_Heap, cb);
226	if (pv)
227	kHlpMemSet(pv, 0, cb);
228	return pv;
229	}
230
231
232	KHLP_DECL(void ) kHlpDup(const void pv, KSIZE cb)
233	{
234	void *pvNew = khlpHeapAlloc(&g_Heap, cb);
235	if (pvNew)
236	kHlpMemCopy(pvNew, pv, cb);
237	return pvNew;
238	}
239
240
241	KHLP_DECL(char ) kHlpStrDup(const char psz)
242	{
243	return (char *)kHlpDup(psz, kHlpStrLen(psz) + 1);
244	}
245
246
247	KHLP_DECL(void ) kHlpRealloc(void pv, KSIZE cb)
248	{
249	void *pvNew;
250	if (!cb)
251	{
252	kHlpFree(pv);
253	pvNew = NULL;
254	}
255	else if (!pv)
256	pvNew = khlpHeapAlloc(&g_Heap, cb);
257	else
258	{
259	KSIZE cbToCopy = khlpHeapBlockSize(&g_Heap, pv);
260	pvNew = khlpHeapAlloc(&g_Heap, cb);
261	if (pvNew)
262	{
263	kHlpMemCopy(pvNew, pv, cb);
264	kHlpFree(pv);
265	}
266	}
267	return pvNew;
268	}
269
270
271	KHLP_DECL(void) kHlpFree(void *pv)
272	{
273	khlpHeapFree(&g_Heap, pv);
274	}
275
276
277	/**
278	* Donates memory to the heap.
279	*
280	* @param pv The address of the memory.
281	* @param cb The amount of memory.
282	*/
283	KHLP_DECL(void) kHlpHeapDonate(void *pv, KSIZE cb)
284	{
285	khlpHeapDonate(&g_Heap, pv, cb);
286	}
287
288
289
290	/**
291	* Initializes the heap anchor.
292	*
293	* @returns 0 on success, non-zero on failure.
294	* @param pHeap The heap anchor to be initialized.
295	*/
296	static int khlpHeapInit(PKHLPHEAPANCHOR pHeap)
297	{
298	pHeap->pHead = NULL;
299	pHeap->pTail = NULL;
300	pHeap->pFreeHead = NULL;
301	pHeap->SegsHead.pNext = NULL;
302	pHeap->SegsHead.cSegs = 0;
303	return 0;
304	}
305
306
307	/**
308	* Deletes a heap.
309	* This will free all resources (memory) associated with the heap.
310	*
311	* @param pHeap The heap to be deleted.
312	*/
313	static void khlpHeapDelete(PKHLPHEAPANCHOR pHeap)
314	{
315	/*
316	* Free the segments, LIFO order.
317	* The head element is the last to be free, while the
318	* head.pNext is really the tail pointer - neat or what?
319	*/
320	while ( pHeap->SegsHead.cSegs
321	\|\| pHeap->SegsHead.pNext)
322	{
323	/* find the tail. */
324	KU32 iSeg;
325	PKHLPHEAPSEGS pSegs = pHeap->SegsHead.pNext;
326	if (!pSegs)
327	pSegs = &pHeap->SegsHead;
328	else
329	{
330	pHeap->SegsHead.pNext = pSegs->pNext;
331	pSegs->pNext = NULL;
332	}
333
334	/* free the segments */
335	iSeg = pSegs->cSegs;
336	while (iSeg-- > 0)
337	khlpHeapSegFree(&pSegs->aSegs[iSeg]);
338	pSegs->cSegs = 0;
339	}
340
341	/* Zap the anchor. */
342	pHeap->pHead = NULL;
343	pHeap->pTail = NULL;
344	pHeap->pFreeHead = NULL;
345	pHeap->SegsHead.pNext = NULL;
346	pHeap->SegsHead.cSegs = 0;
347	}
348
349
350	/**
351	* Internal heap block allocator.
352	*/
353	static void * kldrHeapAllocSub(PKHLPHEAPANCHOR pHeap, KSIZE cb)
354	{
355	/*
356	* Find a fitting free block.
357	*/
358	const KSIZE cbReq = K_ALIGN_Z(cb + sizeof(KHLPHEAPBLOCK), KHLPHEAPBLOCK_ALIGNMENT);
359	PKHLPHEAPFREE pCur = pHeap->pFreeHead;
360	while (pCur)
361	{
362	if (pCur->Core.cb >= cbReq)
363	{
364	if (pCur->Core.cb != cbReq)
365	{
366	/* check and see if there is a better match close by. */
367	PKHLPHEAPFREE pCur2 = pCur->pNext;
368	unsigned i = 16;
369	while (i-- > 0 && pCur2)
370	{
371	if (pCur2->Core.cb >= cbReq)
372	{
373	if (pCur2->Core.cb == cbReq)
374	{
375	pCur = pCur2;
376	break;
377	}
378	if (pCur2->Core.cb < pCur->Core.cb)
379	pCur = pCur2;
380	}
381
382	/* next */
383	KHLPHEAP_ASSERT_FREE(pHeap, pCur2);
384	pCur2 = pCur2->pNext;
385	}
386	}
387	break;
388	}
389
390	/* next */
391	KHLPHEAP_ASSERT_FREE(pHeap, pCur);
392	pCur = pCur->pNext;
393	}
394	if (!pCur)
395	return NULL;
396	KHLPHEAP_ASSERT_FREE(pHeap, pCur);
397
398	/*
399	* Do we need to split out a block?
400	*/
401	if (pCur->Core.cb - cbReq >= KHLPHEAPBLOCK_ALIGNMENT * 2)
402	{
403	PKHLPHEAPBLOCK pNew;
404
405	pCur->Core.cb -= cbReq;
406
407	pNew = (PKHLPHEAPBLOCK)((KUPTR)pCur + pCur->Core.cb);
408	pNew->fFlags = 0;
409	pNew->cb = cbReq;
410	pNew->pNext = pCur->Core.pNext;
411	if (pNew->pNext)
412	pNew->pNext->pPrev = pNew;
413	else
414	pHeap->pTail = pNew;
415	pNew->pPrev = &pCur->Core;
416	pCur->Core.pNext = pNew;
417
418	KHLPHEAP_ASSERT_FREE(pHeap, pCur);
419	KHLPHEAP_ASSERT_BLOCK(pHeap, pNew);
420	return pNew + 1;
421	}
422
423	/*
424	* No, just unlink it from the free list and return.
425	*/
426	if (pCur->pNext)
427	pCur->pNext->pPrev = pCur->pPrev;
428	if (pCur->pPrev)
429	pCur->pPrev->pNext = pCur->pNext;
430	else
431	pHeap->pFreeHead = pCur->pNext;
432	pCur->Core.fFlags &= ~KHLPHEAPBLOCK_FLAG_FREE;
433
434	KHLPHEAP_ASSERT_BLOCK(pHeap, &pCur->Core);
435	return &pCur->Core + 1;
436	}
437
438
439	/**
440	* Allocate a heap block.
441	*
442	* @returns Pointer to the allocated heap block on success. On failure NULL is returned.
443	* @param pHeap The heap.
444	* @param cb The requested heap block size.
445	*/
446	static void * khlpHeapAlloc(PKHLPHEAPANCHOR pHeap, KSIZE cb)
447	{
448	void *pv;
449
450	/* adjust the requested block size. */
451	cb = K_ALIGN_Z(cb, KHLPHEAPBLOCK_ALIGNMENT);
452	if (!cb)
453	cb = KHLPHEAPBLOCK_ALIGNMENT;
454
455	/* try allocate the block. */
456	pv = kldrHeapAllocSub(pHeap, cb);
457	if (!pv)
458	{
459	/*
460	* Failed, add another segment and try again.
461	*/
462	KHLPHEAPSEG Seg;
463	if (khlpHeapSegAlloc(&Seg, cb + sizeof(KHLPHEAPSEGS) + sizeof(KHLPHEAPBLOCK) * 16))
464	return NULL;
465
466	/* donate before insterting the segment, this makes sure we got heap to expand the segment list. */
467	khlpHeapDonate(pHeap, Seg.pvBase, Seg.cb);
468
469	/* insert the segment. */
470	if (pHeap->SegsHead.cSegs < sizeof(pHeap->SegsHead.aSegs) / sizeof(pHeap->SegsHead.aSegs[0]))
471	pHeap->SegsHead.aSegs[pHeap->SegsHead.cSegs++] = Seg;
472	else if ( pHeap->SegsHead.pNext
473	&& pHeap->SegsHead.pNext->cSegs < sizeof(pHeap->SegsHead.aSegs) / sizeof(pHeap->SegsHead.aSegs[0]))
474	pHeap->SegsHead.pNext->aSegs[pHeap->SegsHead.pNext->cSegs++] = Seg;
475	else
476	{
477	PKHLPHEAPSEGS pSegs = (PKHLPHEAPSEGS)kldrHeapAllocSub(pHeap, sizeof(*pSegs));
478	KHLPHEAP_ASSERT(pSegs);
479	pSegs->pNext = pHeap->SegsHead.pNext;
480	pHeap->SegsHead.pNext = pSegs;
481	pSegs->aSegs[0] = Seg;
482	pSegs->cSegs = 1;
483	}
484
485	/* retry (should succeed) */
486	pv = kldrHeapAllocSub(pHeap, cb);
487	KHLPHEAP_ASSERT(pv);
488	}
489
490	return pv;
491	}
492
493
494	/**
495	* Frees a heap block.
496	*
497	* @param pHeap The heap.
498	* @param pv The pointer returned by khlpHeapAlloc().
499	*/
500	static void khlpHeapFree(PKHLPHEAPANCHOR pHeap, void *pv)
501	{
502	PKHLPHEAPFREE pFree, pLeft, pRight;
503
504	/* ignore NULL pointers. */
505	if (!pv)
506	return;
507
508	pFree = (PKHLPHEAPFREE)((PKHLPHEAPBLOCK)pv - 1);
509	KHLPHEAP_ASSERT_BLOCK(pHeap, &pFree->Core);
510	KHLPHEAP_ASSERT(KHLPHEAPBLOCK_IS_ALLOCATED(&pFree->Core));
511
512	/*
513	* Merge or link with left node?
514	*/
515	pLeft = (PKHLPHEAPFREE)pFree->Core.pPrev;
516	if ( pLeft
517	&& KHLPHEAPBLOCK_IS_FREE(&pLeft->Core)
518	&& KHLPHEAPBLOCK_IS_ADJACENT(&pLeft->Core, &pFree->Core)
519	)
520	{
521	/* merge left */
522	pLeft->Core.pNext = pFree->Core.pNext;
523	if (pFree->Core.pNext)
524	pFree->Core.pNext->pPrev = &pLeft->Core;
525	else
526	pHeap->pTail = &pLeft->Core;
527
528	pLeft->Core.cb += pFree->Core.cb;
529	pFree->Core.fFlags = ~0;
530	pFree = pLeft;
531	}
532	else
533	{
534	/* link left */
535	while (pLeft && !KHLPHEAPBLOCK_IS_FREE(&pLeft->Core))
536	pLeft = (PKHLPHEAPFREE)pLeft->Core.pPrev;
537	if (pLeft)
538	{
539	pFree->pPrev = pLeft;
540	pFree->pNext = pLeft->pNext;
541	if (pLeft->pNext)
542	pLeft->pNext->pPrev = pFree;
543	pLeft->pNext = pFree;
544	}
545	else
546	{
547	pFree->pPrev = NULL;
548	pFree->pNext = pHeap->pFreeHead;
549	if (pHeap->pFreeHead)
550	pHeap->pFreeHead->pPrev = pFree;
551	pHeap->pFreeHead = pFree;
552	}
553	pFree->Core.fFlags \|= KHLPHEAPBLOCK_FLAG_FREE;
554	}
555	KHLPHEAP_ASSERT_FREE(pHeap, pFree);
556
557	/*
558	* Merge right?
559	*/
560	pRight = (PKHLPHEAPFREE)pFree->Core.pNext;
561	if ( pRight
562	&& KHLPHEAPBLOCK_IS_FREE(&pRight->Core)
563	&& KHLPHEAPBLOCK_IS_ADJACENT(&pFree->Core, pRight)
564	)
565	{
566	/* unlink pRight from the global list. */
567	pFree->Core.pNext = pRight->Core.pNext;
568	if (pRight->Core.pNext)
569	pRight->Core.pNext->pPrev = &pFree->Core;
570	else
571	pHeap->pTail = &pFree->Core;
572
573	/* unlink pRight from the free list. */
574	pFree->pNext = pRight->pNext;
575	if (pRight->pNext)
576	pRight->pNext->pPrev = pFree;
577
578	/* update size and invalidate pRight. */
579	pFree->Core.cb += pRight->Core.cb;
580	pRight->Core.fFlags = ~0;
581	}
582	}
583
584
585	/**
586	* Calcs the size of a heap block.
587	*
588	* @returns The block size (in bytes).
589	* @param pHeap The heap.
590	* @param pv Pointer to an in-use heap block.
591	*/
592	static KSIZE khlpHeapBlockSize(PKHLPHEAPANCHOR pHeap, void *pv)
593	{
594	PKHLPHEAPBLOCK pBlock = (PKHLPHEAPBLOCK)pv - 1;
595	KHLPHEAP_ASSERT_BLOCK(pHeap, pBlock);
596	KHLPHEAP_ASSERT(KHLPHEAPBLOCK_IS_ALLOCATED(pBlock));
597	return (KU8 )pBlock->pNext - (KU8 )pv;
598	}
599
600
601	/**
602	* Donates memory to the heap.
603	*
604	* The donated memory is returned to the donator when the heap is deleted.
605	*
606	* @param pHeap The heap
607	* @param pv The pointer to the donated memory.
608	* @param cb Size of the donated memory.
609	*/
610	static void khlpHeapDonate(PKHLPHEAPANCHOR pHeap, void *pv, KSIZE cb)
611	{
612	PKHLPHEAPBLOCK pBlock;
613
614	/*
615	* Don't bother with small donations.
616	*/
617	if (cb < KHLPHEAPBLOCK_ALIGNMENT * 4)
618	return;
619
620	/*
621	* Align the donation on a heap block boundrary.
622	*/
623	if ((KUPTR)pv & (KHLPHEAPBLOCK_ALIGNMENT - 1))
624	{
625	cb -= (KUPTR)pv & 31;
626	pv = K_ALIGN_P(pv, KHLPHEAPBLOCK_ALIGNMENT);
627	}
628	cb &= ~(KSIZE)(KHLPHEAPBLOCK_ALIGNMENT - 1);
629
630	/*
631	* Create an allocated block, link it and free it.
632	*/
633	pBlock = (PKHLPHEAPBLOCK)pv;
634	pBlock->pNext = NULL;
635	pBlock->pPrev = NULL;
636	pBlock->cb = cb;
637	pBlock->fFlags = 0;
638
639	/* insert */
640	if ((KUPTR)pBlock < (KUPTR)pHeap->pHead)
641	{
642	/* head */
643	pBlock->pNext = pHeap->pHead;
644	pHeap->pHead->pPrev = pBlock;
645	pHeap->pHead = pBlock;
646	}
647	else if ((KUPTR)pBlock > (KUPTR)pHeap->pTail)
648	{
649	if (pHeap->pTail)
650	{
651	/* tail */
652	pBlock->pPrev = pHeap->pTail;
653	pHeap->pTail->pNext = pBlock;
654	pHeap->pTail = pBlock;
655	}
656	else
657	{
658	/* first */
659	pHeap->pHead = pBlock;
660	pHeap->pTail = pBlock;
661	}
662	}
663	else
664	{
665	/* in list (unlikely) */
666	PKHLPHEAPBLOCK pPrev = pHeap->pHead;
667	PKHLPHEAPBLOCK pCur = pPrev->pNext;
668	for (;;)
669	{
670	KHLPHEAP_ASSERT_BLOCK(pHeap, pCur);
671	if ((KUPTR)pCur > (KUPTR)pBlock)
672	break;
673	pPrev = pCur;
674	pCur = pCur->pNext;
675	}
676
677	pBlock->pNext = pCur;
678	pBlock->pPrev = pPrev;
679	pPrev->pNext = pBlock;
680	pCur->pPrev = pBlock;
681	}
682	KHLPHEAP_ASSERT_BLOCK(pHeap, pBlock);
683
684	/* free it */
685	khlpHeapFree(pHeap, pBlock + 1);
686	}
687
688
689
690	/**
691	* Allocates a new segment.
692	*
693	* @returns 0 on success, non-zero OS status code on failure.
694	* @param pSeg Where to put the info about the allocated segment.
695	* @param cbMin The minimum segment size.
696	*/
697	static int khlpHeapSegAlloc(PKHLPHEAPSEG pSeg, KSIZE cbMin)
698	{
699	#if K_OS == K_OS_OS2
700	APIRET rc;
701
702	pSeg->cb = (cbMin + 0xffff) & ~(KSIZE)0xffff;
703	pSeg->pvBase = NULL;
704	rc = DosAllocMem(&pSeg->pvBase, pSeg->cb, PAG_COMMIT \| PAG_READ \| PAG_WRITE \| OBJ_ANY);
705	if (rc == ERROR_INVALID_PARAMETER)
706	rc = DosAllocMem(&pSeg->pvBase, pSeg->cb, PAG_COMMIT \| PAG_READ \| PAG_WRITE);
707	if (rc)
708	{
709	pSeg->pvBase = NULL;
710	pSeg->cb = 0;
711	return rc;
712	}
713
714	#elif K_OS == K_OS_WINDOWS
715	pSeg->cb = (cbMin + 0xffff) & ~(KSIZE)0xffff;
716	pSeg->pvBase = VirtualAlloc(NULL, pSeg->cb, MEM_COMMIT, PAGE_READWRITE);
717	if (!pSeg->pvBase)
718	{
719	pSeg->cb = 0;
720	return GetLastError();
721	}
722
723	#else
724	int rc;
725
726	pSeg->cb = (cbMin + 0xffff) & ~(KSIZE)0xffff;
727	pSeg->pvBase = NULL;
728	rc = kHlpPageAlloc(&pSeg->pvBase, pSeg->cb, KPROT_READWRITE, K_FALSE);
729	if (rc)
730	{
731	pSeg->pvBase = NULL;
732	pSeg->cb = 0;
733	return rc;
734	}
735
736	#endif
737
738	return 0;
739	}
740
741
742	/**
743	* Frees a segment.
744	*
745	* @param pSeg The segment to be freed.
746	*/
747	static void khlpHeapSegFree(PKHLPHEAPSEG pSeg)
748	{
749	#if K_OS == K_OS_OS2
750	APIRET rc = DosFreeMem(pSeg->pvBase);
751	KHLPHEAP_ASSERT(!rc); (void)rc;
752
753	#elif K_OS == K_OS_WINDOWS
754	BOOL fRc = VirtualFree(pSeg->pvBase, 0 /pSeg->cb/, MEM_RELEASE);
755	KHLPHEAP_ASSERT(fRc); (void)fRc;
756
757	#else
758	int rc = kHlpPageFree(pSeg->pvBase, pSeg->cb);
759	KHLPHEAP_ASSERT(!rc); (void)rc;
760
761	#endif
762	}
763

Note: See TracBrowser for help on using the repository browser.

source: kStuff/trunk/kHlp/Bare/kHlpBareHeap.c

Download in other formats: