kHlpBareHeap.c@ 24

Last change on this file since 24 was 2, checked in by bird, 17 years ago
Imported http://svn.netlabs.org/repos/libc/trunk/kStuff, revision 3612.
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 20.0 KB

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

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

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

Download in other formats: