User:Pancakes/SimpleHeapImplementation: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 18:54, 7 May 2014

Simple Heap Implementation

There are a few simple heap implementations for you to examine. I want to come back and write a little tutorial on each page to kind of walk the reader through how they work.

If you want to copy them straight out and use them in your kernel then that is fine. I put these up here so someone who might not be that interested in implementing a heap can get it done and move on to better things.

The bitmap implementation has been fairly well optimized. I can not find any major performance improvements to make. It still needs some optimization for multiple blocks such as moving full blocks to the end of the linked list maybe. Also, the entry could perhaps use a double chain where one chain links free entries and the other links used entries therefore making allocation quicker. At the moment it just jumps through all of them. Also, deallocation could be faster on the entry implementation.

I have tested both implementations quite well for corruption internally, and checked a 32-bit block at the beginning and end of the blocks for under or over runs and so far have found no corruption even after a long period of running.

If you find any bugs, problems, or have success using them just let me know at kmcg3413@gmail.com.

Simulation

I wrote a page that lets you simulate a bitmap heap with a view of memory and play back of memory accesses. It relates directly to the bitmap algorithm except it uses only 16-bit fields. You can find it at http://kmcg3413.net/jsbmheap.htm. It also contains a link back to the bitmap implementation page so you can reference the actual code and structures.

Implementations

These are the implementations. I recommend the bitmap because of it's reliability, decent performance, simplicity, and small code size make it a very attractive choice for a beginning heap.

Page	Brief Description
Bitmap Based	A very simple and decently performing implementation.
Entry Based	Not very good but shows an alternative way.
Stack Based	Very fast but only supports one block size, and if data is smaller it wastes memory depending on stack entry size. Could be chained together to provide different sizes like a SLAB allocator.
Bitmap Based With Enhanced Functionality	The bitmap implementation but supports managing physical memory and provides data aligned on arbitrary boundaries.
Linked List Bucket Heap	A very fast general purpose allocator. It can work well with large or small allocations.

Performance

The Enhanced Bitmap is noted as bm in green, and was initialized with 16-byte blocks. The Linked List Bucket Heap is noted as mrvn and is shown in light red. As you can see the performance of the bitmap implementation decreases as allocation size increases. The darkish purple is the entry based. The numbers across the bottom denote maximum allocation size. For example 256 means allocations were between 1 and 256 while 4096 means allocations where between 1 byte and 4096 bytes. Each implementation was run for a lengthy period of time and had allocations and frees made randomly. Each implementation was allowed to use more memory if it ran out.

The Linked List Bucket Heap is a great generic heap, but it is slightly more complicated and a little harder to follow code wise. The bitmap heap also consumes significant memory by meta-data of it's bitmap tables, but code wise is fairly straight forward and simple.

The numbers represent the speed gain compared with the standard malloc and free provided by my C library on the machine I produced these numbers on. It represents how many times faster, and it combines the speed of both malloc and free for an overall speed. Some implements have ultra fast free like entry based and bitmap which beat all others, but their initial allocation speed is just too slow to make them fast.

User:Pancakes/SimpleHeapImplementation: Difference between revisions

Latest revision as of 18:54, 7 May 2014

Contents

Simple Heap Implementation

Simulation

Implementations

Performance

Navigation menu

@@ Line 1: / Line 1: @@
 == Simple Heap Implementation ==
+There are a few simple heap implementations for you to examine. I want to come back and
-This is a fairly simple heap implementation. It has not been well tested so it could have a bug somewhere, but so far it seems to work well and I have not run into any problems. It basically works by you assigning blocks of memory to the heap. Each block of
+write a little tutorial on each page to kind of walk the reader through how they work.
-memory is separate. So the maximum allocation you can make is the size of the largest block minus the header. Also, over time the
-heap can become kind of fragmented from calls to alloc and free which eventually create spots between allocations and this can
-reduce your maximum allocation size. A good fallback would be for you to add another block to the heap if an allocation can not be
-made in the event the heap becomes highly fragmented. I do not add another block here because I wanted to keep this implementation with out any dependencies. The best way would likely be to wrap these calls in another layer than can handle the failed call to
-the allocation function and try to add another block (and also check adding another block will work).
+If you want to copy them straight out and use them in your kernel then that is fine. I put these
-Also, I forgot to mention there is a maximum block size set at 2,147,483,647 bytes (31-bit). This is because each header/chunk inside the block only has 31 bits to specify it's size (free or used). The highest bit (32nd bit) is used to flag if the header/chunk is used or free. However, the implementation is so short and simple that if you needed to support bigger blocks and allocations you could simply expand the header to handle any. I just settled for 2GB because I think that is good for most hobby projects, while still keeping the overhead low on memory consumption and still being quite fast.
+up here so someone who might not be that interested in implementing a heap can get it done and
+move on to better things.
+The bitmap implementation has been fairly well optimized. I can not find any major performance improvements to make. It still needs some optimization for multiple blocks such as moving full blocks to the end of the linked list maybe. Also, the entry could perhaps use a double chain where one chain links free entries and the other links used entries therefore making allocation quicker. At the moment it just jumps through all of them. Also, deallocation could be faster on the entry implementation.
-A good idea is to build a wrapper around these calls (not only for your kernel to call k_heapAddBlock) to provide a debugging ability. What you do is catch all alloc calls and add some extra bytes onto the size. Then place a special signature at the
-beginning and end to catch under-flows and overflows for writing. It is not easy to catch over reading or under reading, but
-at least you can catch when your heap has become corrupted!
+I have tested both implementations quite well for corruption internally, and checked a 32-bit block at the beginning and end of the blocks for under or over runs and so far have found no corruption even after a long period of running.
-=== k_heapInit ===
-This initializes the heap structure. Nothing too complex.
-=== k_heapAddBlock ===
-You use this to add a block to the heap. Like, h_heapAddBlock(&heap, 0x1000, 0x2000) would add 2KB starting at 1KB.
-=== k_heapAlloc ===
-This will allocate a chunk which can be used.
-=== k_heapFree ===
-This will free a chunk.
-=== Example Usage ===
-<pre>
-    KHEAP       kheap;
-    char        *ptr;
+''If you find any bugs, problems, or have success using them just let me know at [mailto:kmcg3413@gmail.com kmcg3413@gmail.com].''
-    k_heapInit(&kheap);                          /* initialize the heap */
-    k_heapAddBlock(&kheap, 0x100000, 0x100000);  /* add block to heap (starting 1MB mark and length of 1MB) */
-    ptr = (char*)k_heapAlloc(&kheap, 256);               /* allocate 256 bytes (malloc) */
-    k_heapFree(&kheap, ptr);                             /* free the pointer (free) */
-</pre>
-Also, you could wrap the functions so that ''kheap'' does not need to be passed thus making the calls
-much more simple and easy to write. I thought it was better to give the programmer the ability to have
-multiple heaps than to restrict them. So if you only want to use one heap then create an abstraction
-layer that hands in the ''kheap'' argument.
-=== C/C++ Code ===
+== Simulation ==
+I wrote a page that lets you simulate a bitmap heap with a view of memory and play back of memory accesses. It relates directly to the bitmap algorithm except it uses only 16-bit fields. You can find it
-<pre>
+at [http://kmcg3413.net/jsbmheap.htm http://kmcg3413.net/jsbmheap.htm]. It also contains a link back to the bitmap implementation page so you can reference the actual code and structures.
-/*
-    Copyright 2014 Leonard Kevin McGuire Jr (www.kmcg3413.net) (kmcg3413@gmail.com)
+== Implementations ==
-    This program is free software; you can redistribute it and/or modify
+These are the implementations. I recommend the bitmap because of it's reliability, decent performance, simplicity, and small code size make it a very attractive choice for a beginning heap.
-    it under the terms of the GNU Lesser General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
+{| class="wikitable"
-    This program is distributed in the hope that it will be useful,
+|-
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
+! Page
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+! Brief Description
-    GNU Lesser General Public License for more details.
+|-
+| [[User:Pancakes/BitmapHeapImplementation|Bitmap Based]]
+| A very simple and decently performing implementation.
+|-
+| [[User:Pancakes/EntryBasedHeapImplementation|Entry Based]]
+| Not very good but shows an alternative way.
+|-
+| [[User:Pancakes/StackBasedHeapImplementation|Stack Based]]
+| Very fast but only supports one block size, and if data is smaller it wastes memory depending on stack entry size. Could be chained together to provide different sizes like a SLAB allocator.
+|-
+| [[User:Pancakes/BitmapHeapImplementationEnhanced|Bitmap Based With Enhanced Functionality]]
+| The bitmap implementation but supports managing physical memory and provides data aligned on arbitrary boundaries.
+|-
+| [[User:mrvn/LinkedListBucketHeapImplementation|Linked List Bucket Heap]]
+| A very fast general purpose allocator. It can work well with large or small allocations.
+|}
+==== Performance ====
-    You should have received a copy of the GNU Lesser General Public License
-    along with this program; if not, write to the Free Software
-    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+The ''Enhanced Bitmap'' is noted as ''bm'' in green, and was initialized with 16-byte blocks. The ''Linked List Bucket Heap'' is noted as ''mrvn'' and is shown in light red. As you can see the performance of the bitmap implementation decreases as allocation size increases. The darkish purple is the entry based. The numbers across the bottom denote maximum allocation size. For example 256 means allocations were between 1 and 256 while 4096 means allocations where between 1 byte and 4096 bytes. Each implementation was run for a lengthy period of time and had allocations and frees made randomly. Each implementation was allowed to use more memory if it ran out.
-    This code is so simple that there is NO reason to copyright it, but I know
-    some people out there who have yet to truly understand what they are doing
-    might be fearful of using it with out some kind of copyright.
-*/
-typedef unsigned int uint32;
-typedef unsigned char uint8;
-typedef unsigned int uintptr;
+<html><body><svg height="300" width="700">
-#define KHEAPFLAG_USED			0x80000000
+<text style="font-size: 8pt;" x="0" y="271.4770860505417" fill="rgb(0,0,0)">eb</text>
+<text style="font-size: 8pt;" x="0" y="260.5681727301949" fill="rgb(0,0,0)">bm</text>
+<text style="font-size: 8pt;" x="0" y="201.04345987460465" fill="rgb(0,0,0)">sb</text>
+<text style="font-size: 8pt;" x="0" y="238.8811744121518" fill="rgb(0,0,0)">mrvn</text>
+<line x1="40" y1="271.4770860505417" x2="39.0" y2="271.4770860505417" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="40" y="271.4770860505417" fill="rgb(153,0,255)">0.3</text>
+<line x1="40" y1="260.5681727301949" x2="39.0" y2="260.5681727301949" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="40" y="260.5681727301949" fill="rgb(153,255,153)">0.4</text>
+<line x1="40" y1="201.04345987460465" x2="39.0" y2="201.04345987460465" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="40" y="201.04345987460465" fill="rgb(0,255,255)">1.1</text>
+<line x1="40" y1="238.8811744121518" x2="39.0" y2="238.8811744121518" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="40" y="238.8811744121518" fill="rgb(255,153,153)">0.7</text>
+<text style="font-size: 8pt;" x="40" y="300" fill="rgb(0,0,0)">16</text>
+<line x1="80" y1="271.59097505774" x2="40" y2="271.4770860505417" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="80" y="271.59097505774" fill="rgb(153,0,255)">0.3</text>
+<line x1="80" y1="266.1457872407004" x2="40" y2="260.5681727301949" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="80" y="266.1457872407004" fill="rgb(153,255,153)">0.3</text>
+<line x1="80" y1="197.9335788586706" x2="40" y2="201.04345987460465" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="80" y="197.9335788586706" fill="rgb(0,255,255)">1.1</text>
+<line x1="80" y1="243.85223645946513" x2="40" y2="238.8811744121518" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="80" y="243.85223645946513" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="80" y="300" fill="rgb(0,0,0)">32</text>
+<line x1="120" y1="273.3687218988938" x2="80" y2="271.59097505774" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="120" y="273.3687218988938" fill="rgb(153,0,255)">0.3</text>
+<line x1="120" y1="273.2187003317216" x2="80" y2="266.1457872407004" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="120" y="273.2187003317216" fill="rgb(153,255,153)">0.3</text>
+<line x1="120" y1="184.0375802848887" x2="80" y2="197.9335788586706" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="120" y="184.0375802848887" fill="rgb(0,255,255)">1.3</text>
+<line x1="120" y1="247.36927461158245" x2="80" y2="243.85223645946513" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="120" y="247.36927461158245" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="120" y="300" fill="rgb(0,0,0)">64</text>
+<line x1="160" y1="280.0267366728067" x2="120" y2="273.3687218988938" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="160" y="280.0267366728067" fill="rgb(153,0,255)">0.2</text>
+<line x1="160" y1="278.3306191945452" x2="120" y2="273.2187003317216" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="160" y="278.3306191945452" fill="rgb(153,255,153)">0.2</text>
+<line x1="160" y1="193.80312762756847" x2="120" y2="184.0375802848887" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="160" y="193.80312762756847" fill="rgb(0,255,255)">1.2</text>
+<line x1="160" y1="250.4264809169783" x2="120" y2="247.36927461158245" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="160" y="250.4264809169783" fill="rgb(255,153,153)">0.5</text>
+<text style="font-size: 8pt;" x="160" y="300" fill="rgb(0,0,0)">128</text>
+<line x1="200" y1="283.2616949646197" x2="160" y2="280.0267366728067" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="200" y="283.2616949646197" fill="rgb(153,0,255)">0.1</text>
+<line x1="200" y1="283.15126703525505" x2="160" y2="278.3306191945452" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="200" y="283.15126703525505" fill="rgb(153,255,153)">0.1</text>
+<line x1="200" y1="179.8772379141531" x2="160" y2="193.80312762756847" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="200" y="179.8772379141531" fill="rgb(0,255,255)">1.3</text>
+<line x1="200" y1="247.57494334396884" x2="160" y2="250.4264809169783" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="200" y="247.57494334396884" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="200" y="300" fill="rgb(0,0,0)">256</text>
+<line x1="240" y1="284.98919175692185" x2="200" y2="283.2616949646197" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="240" y="284.98919175692185" fill="rgb(153,0,255)">0.1</text>
+<line x1="240" y1="288.2320350909907" x2="200" y2="283.15126703525505" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="240" y="288.2320350909907" fill="rgb(153,255,153)">0.1</text>
+<line x1="240" y1="115.37561513335092" x2="200" y2="179.8772379141531" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="240" y="115.37561513335092" fill="rgb(0,255,255)">2.1</text>
+<line x1="240" y1="241.2029598079109" x2="200" y2="247.57494334396884" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="240" y="241.2029598079109" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="240" y="300" fill="rgb(0,0,0)">512</text>
+<line x1="280" y1="287.3975513306974" x2="240" y2="284.98919175692185" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="280" y="287.3975513306974" fill="rgb(153,0,255)">0.1</text>
+<line x1="280" y1="293.3565931075834" x2="240" y2="288.2320350909907" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="280" y="293.3565931075834" fill="rgb(153,255,153)">0.0</text>
+<line x1="280" y1="93.56361255075586" x2="240" y2="115.37561513335092" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="280" y="93.56361255075586" fill="rgb(0,255,255)">2.4</text>
+<line x1="280" y1="243.0694390692868" x2="240" y2="241.2029598079109" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="280" y="243.0694390692868" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="280" y="300" fill="rgb(0,0,0)">1024</text>
+<line x1="320" y1="289.8395296655668" x2="280" y2="287.3975513306974" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="320" y="289.8395296655668" fill="rgb(153,0,255)">0.1</text>
+<line x1="320" y1="291.4247206595326" x2="280" y2="293.3565931075834" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="320" y="291.4247206595326" fill="rgb(153,255,153)">0.0</text>
+<line x1="320" y1="91.37795492547124" x2="280" y2="93.56361255075586" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="320" y="91.37795492547124" fill="rgb(0,255,255)">2.4</text>
+<line x1="320" y1="240.37311671765553" x2="280" y2="243.0694390692868" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="320" y="240.37311671765553" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="320" y="300" fill="rgb(0,0,0)">2048</text>
+<line x1="360" y1="291.82936406358374" x2="320" y2="289.8395296655668" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="360" y="291.82936406358374" fill="rgb(153,0,255)">0.0</text>
+<line x1="360" y1="291.685536015328" x2="320" y2="291.4247206595326" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="360" y="291.685536015328" fill="rgb(153,255,153)">0.0</text>
+<line x1="360" y1="84.43282646493722" x2="320" y2="91.37795492547124" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="360" y="84.43282646493722" fill="rgb(0,255,255)">2.5</text>
+<line x1="360" y1="242.36747130138255" x2="320" y2="240.37311671765553" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="360" y="242.36747130138255" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="360" y="300" fill="rgb(0,0,0)">4096</text>
+<line x1="400" y1="293.64362664521053" x2="360" y2="291.82936406358374" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="400" y="293.64362664521053" fill="rgb(153,0,255)">0.0</text>
+<line x1="400" y1="291.0443879550437" x2="360" y2="291.685536015328" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="400" y="291.0443879550437" fill="rgb(153,255,153)">0.1</text>
+<line x1="400" y1="75.78456882308708" x2="360" y2="84.43282646493722" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="400" y="75.78456882308708" fill="rgb(0,255,255)">2.6</text>
+<line x1="400" y1="244.82608599404003" x2="360" y2="242.36747130138255" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="400" y="244.82608599404003" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="400" y="300" fill="rgb(0,0,0)">8192</text>
+<line x1="440" y1="292.83027753490535" x2="400" y2="293.64362664521053" style="stroke:rgb(153,0,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="440" y="292.83027753490535" fill="rgb(153,0,255)">0.0</text>
+<line x1="440" y1="289.20005644117305" x2="400" y2="291.0443879550437" style="stroke:rgb(153,255,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="440" y="289.20005644117305" fill="rgb(153,255,153)">0.1</text>
+<line x1="440" y1="0.0" x2="400" y2="75.78456882308708" style="stroke:rgb(0,255,255);stroke-width:2"/>
+<text style="font-size: 8pt;" x="440" y="0.0" fill="rgb(0,255,255)">3.4</text>
+<line x1="440" y1="240.93068766785797" x2="400" y2="244.82608599404003" style="stroke:rgb(255,153,153);stroke-width:2"/>
+<text style="font-size: 8pt;" x="440" y="240.93068766785797" fill="rgb(255,153,153)">0.6</text>
+<text style="font-size: 8pt;" x="440" y="300" fill="rgb(0,0,0)">16384</text>
+</svg></body></html>
-typedef struct _KHEAPHDR {
-	uint32				flagsize;
-} KHEAPHDR;
+The ''Linked List Bucket Heap'' is a great generic heap, but it is slightly more complicated and a little harder to follow code wise. The bitmap heap also consumes significant memory by meta-data of it's bitmap tables, but code wise is fairly straight forward and simple.
-typedef struct _KHEAPBLOCK {
-	uint32				size;
-	uint32				used;
-	struct _KHEAPBLOCK	*next;
-} KHEAPBLOCK;
+''The numbers represent the speed gain compared with the standard malloc and free provided by my C library on the machine I produced these numbers on. It represents how many times faster, and it combines the speed of both malloc and free for an overall speed. Some implements have ultra fast free like entry based and bitmap which beat all others, but their initial allocation speed is just too slow to make them fast.''
-typedef struct _KHEAP {
-	KHEAPBLOCK			*fblock;
-} KHEAP;
-void k_heapInit(KHEAP *heap) {
-		heap->fblock = 0;
-}
-int k_heapAddBlock(KHEAP *heap, uint32 addr, uint32 size) {
-	KHEAPBLOCK			*hb;
-	KHEAPHDR			*hdr;
-	hb = (KHEAPBLOCK*)addr;
-	hb->size = size - sizeof(KHEAPBLOCK) - sizeof(KHEAPHDR);
-	hb->used = 0;
-	hb->next = heap->fblock;
-	heap->fblock = hb;
-	hdr = (KHEAPHDR*)&hb[1];
-	hdr->flagsize = hb->size - sizeof(KHEAPHDR);
-	return 1;
-}
-/*
-	Look behind and forward to see if we can merge back into some chunks.
-*/
-void k_heapFree(KHEAP *heap, void *ptr) {
-	KHEAPHDR			*hdr, *phdr, *nhdr;
-	KHEAPBLOCK			*hb;
-	uint32				sz;
-	uint8				fg;
-	hdr = (KHEAPHDR*)ptr;
-	hdr[-1].flagsize &= ~0x80000000;
-	phdr = 0;
-	/* find the block we are located in */
-	for (hb = heap->fblock; hb; hb = hb->next) {
-		if (((uintptr)ptr > (uintptr)hb) && ((uintptr)ptr < (uintptr)hb + hb->size)) {
-			/* we have found the heap block */
-			/* try to identify the header before and after */
-			hdr = (KHEAPHDR*)&hb[1];
-			while ((uintptr)hdr < (uintptr)hb + sizeof(KHEAPBLOCK) + hb->size) {
-				fg = hdr->flagsize >> 31;
-				sz = hdr->flagsize & 0x7fffffff;
-				nhdr = (KHEAPHDR*)((uintptr)&hdr[1] + sz);
-				if ((uintptr)&hdr[1] == (uintptr)ptr) {
-					/* we have found the header for our 'ptr' */
-					if ((uintptr)nhdr < (uintptr)hb + sizeof(KHEAPBLOCK) + hb->size) {
-						/* okay we have a header in font of us, can we combine with it */
-						if (!(nhdr->flagsize & 0x80000000)) {
-							/* combine with it */
-							hdr->flagsize += sizeof(KHEAPHDR) + nhdr->flagsize;
-							hb->used -= sizeof(KHEAPHDR);
-						}
-						/* can we combine with previous header? */
-						if (phdr) {
-							if (!(phdr->flagsize & 0x80000000)) {
-								phdr->flagsize += sizeof(KHEAPHDR) + hdr->flagsize;
-								hb->used -= sizeof(KHEAPHDR);
-							}
-						}
-					}
-					hb->used -= hdr->flagsize;
-					return;
-				}
-				phdr = hdr;
-				hdr = nhdr;
-			}
-		}
-	}
-	/* uhoh.. this should not happen.. */
-	return;
-}
-/*
-	This will allocate a chunk of memory by the specified size, and if
-	no memory chunk can be found it will return zero.
-*/
-void* k_heapAlloc(KHEAP *heap, uint32 size) {
-	KHEAPBLOCK			*hb;
-	KHEAPHDR			*hdr, *_hdr;
-	uint32				sz;
-	uint8				fg;
-	/* first find heap block with enough space */
-	for (hb = heap->fblock; hb; hb = hb->next) {
-		if ((hb->size - hb->used) >= (size + sizeof(KHEAPHDR))) {
-			/* find actual free block */
-			hdr = (KHEAPHDR*)&hb[1];
-			while ((uintptr)hdr < (uintptr)hb + sizeof(KHEAPBLOCK) + hb->size) {
-				fg = hdr->flagsize >> 31;
-				sz = hdr->flagsize & 0x7fffffff;
-				if (!fg) {
-					if (sz >= size) {
-						// else take whole chunk
-						if (sz > size + sizeof(KHEAPHDR) + 16) {
-							/* has enough left over (break into two) */
-							_hdr = (KHEAPHDR*)((uint32)&hdr[1] + size);
-							/* take out data size and header size */
-							_hdr->flagsize = sz - size - sizeof(KHEAPHDR);
-							/* set to used and set new size */
-							hdr->flagsize = 0x80000000 | size;
-							hb->used += sizeof(KHEAPHDR);
-						} else {
-							/* simply set to used */
-							hdr->flagsize |= 0x80000000;
-						}
-						hb->used += size;
-						return &hdr[1];
-					}
-				}
-				hdr = (KHEAPHDR*)((uintptr)&hdr[1] + sz);
-			}
-		}
-	}
-	return 0;
-}
-</pre>

User:Pancakes/SimpleHeapImplementation: Difference between revisions

Latest revision as of 18:54, 7 May 2014

Simple Heap Implementation

Simulation

Implementations

Performance

Navigation menu

Search