What xheap is:
Xheap is a portable memory allocator and manager. Xheap is perfect for embedded applications, or anywhere you need particularly efficient memory management. Xheap uses a binary subdivision hack to achieve the following design goals:
1) Very fast allocates and frees,
2) Low additional memory overhead,
3) Reduces effects of memory fragmentation,
4) No block headers amongst the memory blocks (they're stored safely elsewhere)
5) Can be used at interrupt time.
The most interesting thing about xheap is that allocator returns only blocks of power of 2 sizes. This constraint allows xheap to be extremely efficient.
When used while keeping this constraint in mind, Xheap yields excellent application performance. MemUtils.h contains some good ways to use the heap effectively to gain space efficiency along with speed efficiency.
How to use xheap:
First, build a library that you can include in other projects. Include the files xheap.c, MemUtils.c, and CXHeap.cp if you prefer thinking of the memory heap as an object. The file xhlibprj.h should be included since it contains a few project switches. Then, link with this library when building applications, or other code projects.
You can use xheap directly from C, by declaring a heap structure, filling in your platform-specific implementation, calling xheap_Start, and you're on your way.
Or, you can use xheap from C++, by using the CXHeap and CXMemBlkList classes in MemUtils.h
Special considerations:
1) All blocks returned from the allocator are power of 2 sizes (such as 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, etc). if you ask for 15 bytes, you get block of 16. if you ask for 9 bytes, you get block of 16. If used like a traditional memory manager, this feature can lead to a far less than optimal overall memory footprint.
Generally, the only time you should call xheap_NewPtr (and xheap_DisposePtr) directly is for unique one-time memory requests. You might use xheap_BestFit() to optimize your long-term memory usage and at the same time, fully utilize xheap's 2^x sized memory blocks. If you must call xheap_NewPtr directly, the bottom line is: do whatever you can do choose a size equal to or just less than a power of 2 size.
To make life easier, I recommend using the block list memory utility (built on top of xheap) wherever possible. Block lists are optimized for the common pattern of repeated requests for blocks of the same size. These are found in MemUtils.h.
2) Xheap has no built-in process collision prevention or detection. Although you may safely call the allocator or deallocator at interrupt time, you have to implement yourself whatever is necessary not to collide with another thread or interrupt also using the same xheap.
If you are using xheap during interrupt time, you must also be sure to disable xheap callbacks to the system while in your interrupt handler. See usage_examples.c for code snippet that does this.
How xheap works:
The memory for a heap is allocated from the underlying OS in large parcels. Then, xheap memory manager divides the large memory parcels into management structures, and the client's memory area. The clients memory heap is always a power of 2 sized (2Mb maximum). The file xheapprv.h describes the main data structure for maintaining the heap.
When the heap's first memory block is fully allocated to the client, xheap requests a new large memory parcel from the underlying OS, and begins to partition the new memory for new allocation requests, on an as-needed basis. When several memory parcels are being held, xheap prefers to allocate from the oldest parcels first, whereby effectively decanting smaller requests and keeping fragmentation to a minimum.
Why I wrote xheap:
I'm a fast code fanatic. I just love to make programs scream. Xheap is highly optimized to do its job fast and get out of the way of application performance. Also, there's always a need in real time software for an interrupt safe memory manager, especially on the Macintosh.
I'm also a space freak. I can't stand programs that take up more room than necessary. But its hard to avoid memory fragmentation (and hence inefficient memory usage) over time when your crazy user does all sorts of crazy things during a long session with your program. Xheap is designed to cluster like-sized blocks, and greatly reduces the raw size categories, to such an extent that smart memory management emerges organically.
This piece of code is the result of many years of polishing.
Thanks goes to:
I first came up with the idea for this binary subdivision hack while at Lone Wolf Corporation, later called MediaLink Corporation. I was working on several applications at once and all had similar realtime constraints. This led me to become interested enough in the basic problem to write the first version of the algorithm. The code was reusable so I could add these fast memory allocation routines to any application.
Additional thanks go to Dan Gallivan, Mark Lacas, Mike Kurtinitis, Rick Spirtes, and Dave Warman for technical advice along the way.
What you can do with xheap:
Essentially, anything you want. You do not have to release your code into Open Source to use this Open Source code. You may use this code for commercial purposes, if mention is given to xheap and the author as described below.
Xheap is copyright Geoffrey P. Coco and Expressive Logic and is licensed as described in the xheap_LICENSE file.
If you sell or distribute software using xheap code in portion or entirety, I ask that you give attribution to xheap and the author, in your documentation, product literature, or online about box.
Of course, this software is provided "As Is", and no warranty is made as to its function, stability or performance.
If you want to submit changes or bug fixes, for now send them to me at voodoo@exlogic.net. For large contributions that you want to protect and correctly attribute to you, use the xheap_LICENSE and tweak the ending to identify yourself as the contributor.
Contributions can also be sent to me, and I will make an effort to include the contribution in the next official release.
