summaryrefslogtreecommitdiff
path: root/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator
diff options
context:
space:
mode:
Diffstat (limited to 'digital/avr/modules/usb/lufa/LUFA/MemoryAllocator')
-rw-r--r--digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c226
-rw-r--r--digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h182
2 files changed, 408 insertions, 0 deletions
diff --git a/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c
new file mode 100644
index 00000000..a91e0f35
--- /dev/null
+++ b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c
@@ -0,0 +1,226 @@
+/*
+ LUFA Library
+ Copyright (C) Dean Camera, 2009.
+
+ dean [at] fourwalledcubicle [dot] com
+ www.fourwalledcubicle.com
+*/
+
+/*
+ Copyright 2009 Dean Camera (dean [at] fourwalledcubicle [dot] com)
+
+ Permission to use, copy, modify, and distribute this software
+ and its documentation for any purpose and without fee is hereby
+ granted, provided that the above copyright notice appear in all
+ copies and that both that the copyright notice and this
+ permission notice and warranty disclaimer appear in supporting
+ documentation, and that the name of the author not be used in
+ advertising or publicity pertaining to distribution of the
+ software without specific, written prior permission.
+
+ The author disclaim all warranties with regard to this
+ software, including all implied warranties of merchantability
+ and fitness. In no event shall the author be liable for any
+ special, indirect or consequential damages or any damages
+ whatsoever resulting from loss of use, data or profits, whether
+ in an action of contract, negligence or other tortious action,
+ arising out of or in connection with the use or performance of
+ this software.
+*/
+
+#define INCLUDE_FROM_DYNALLOC_C
+#include "DynAlloc.h"
+
+struct
+{
+ char Mem_Heap[NUM_BLOCKS * BLOCK_SIZE];
+ void* Mem_Handles[NUM_HANDLES];
+ uint8_t Mem_Block_Flags[(NUM_BLOCKS / 4) + ((NUM_BLOCKS % 4) ? 1 : 0)];
+ uint8_t FlagMaskLookupMask[4];
+ uint8_t FlagMaskLookupNum[4];
+} Mem_MemData = {FlagMaskLookupMask: {(3 << 0), (3 << 2), (3 << 4), (3 << 6)},
+ FlagMaskLookupNum: { 0, 2, 4, 6}};
+
+static uint8_t Mem_GetBlockFlags(const Block_Number_t BlockNum)
+{
+ const Block_Number_t BlockIndex = (BlockNum >> 2);
+ const uint8_t FlagMask = Mem_MemData.FlagMaskLookupMask[BlockNum & 0x03];
+ const uint8_t FlagMaskShift = Mem_MemData.FlagMaskLookupNum[BlockNum & 0x03];
+
+ return ((Mem_MemData.Mem_Block_Flags[BlockIndex] & FlagMask) >> FlagMaskShift);
+}
+
+static void Mem_SetBlockFlags(const Block_Number_t BlockNum, const uint8_t Flags)
+{
+ const Block_Number_t BlockIndex = (BlockNum >> 2);
+ const uint8_t FlagMask = Mem_MemData.FlagMaskLookupMask[BlockNum & 0x03];
+ const uint8_t FlagMaskShift = Mem_MemData.FlagMaskLookupNum[BlockNum & 0x03];
+
+ Mem_MemData.Mem_Block_Flags[BlockIndex] &= ~FlagMask;
+ Mem_MemData.Mem_Block_Flags[BlockIndex] |= (Flags << FlagMaskShift);
+}
+
+static inline void Mem_Defrag(void)
+{
+ Block_Number_t FreeStartBlock = 0;
+ char* FreeStartPtr = NULL;
+ char* UsedStartPtr = NULL;
+ Block_Number_t CurrBlock;
+
+ for (CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++)
+ {
+ if (!(Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK))
+ {
+ FreeStartPtr = &Mem_MemData.Mem_Heap[CurrBlock * BLOCK_SIZE];
+ FreeStartBlock = CurrBlock;
+ break;
+ }
+ }
+
+ if (FreeStartPtr == NULL)
+ return;
+
+ while (++CurrBlock < NUM_BLOCKS)
+ {
+ uint8_t CurrBlockFlags = Mem_GetBlockFlags(CurrBlock);
+
+ if (CurrBlockFlags & BLOCK_USED_MASK)
+ {
+ UsedStartPtr = &Mem_MemData.Mem_Heap[CurrBlock * BLOCK_SIZE];
+
+ for (Handle_Number_t HandleNum = 0; HandleNum < NUM_HANDLES; HandleNum++)
+ {
+ if (Mem_MemData.Mem_Handles[HandleNum] == UsedStartPtr)
+ {
+ Mem_MemData.Mem_Handles[HandleNum] = FreeStartPtr;
+ break;
+ }
+ }
+
+ memcpy(FreeStartPtr, UsedStartPtr, BLOCK_SIZE);
+ FreeStartPtr += BLOCK_SIZE;
+
+ Mem_SetBlockFlags(FreeStartBlock++, CurrBlockFlags);
+ Mem_SetBlockFlags(CurrBlock, 0);
+ }
+ }
+}
+
+static inline bool Mem_FindFreeBlocks(Block_Number_t* const RetStartPtr, const Block_Number_t Blocks)
+{
+ Block_Number_t FreeInCurrSec = 0;
+
+ for (Block_Number_t CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++)
+ {
+ if (Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK)
+ FreeInCurrSec = 0;
+ else
+ FreeInCurrSec++;
+
+ if (FreeInCurrSec >= Blocks)
+ {
+ *RetStartPtr = CurrBlock;
+ return true;
+ }
+ }
+
+ return false;
+}
+
+Mem_Handle_t Mem_Alloc(const Alloc_Size_t Bytes)
+{
+ Block_Number_t ReqBlocks = (Bytes / BLOCK_SIZE);
+ Block_Number_t StartBlock;
+
+ if (Bytes % BLOCK_SIZE)
+ ReqBlocks++;
+
+ if (!(Mem_FindFreeBlocks(&StartBlock, ReqBlocks)))
+ {
+ Mem_Defrag();
+
+ if (!(Mem_FindFreeBlocks(&StartBlock, ReqBlocks)))
+ return NULL;
+ }
+
+ for (Block_Number_t UsedBlock = 0; UsedBlock < (ReqBlocks - 1); UsedBlock++)
+ Mem_SetBlockFlags((StartBlock + UsedBlock), (BLOCK_USED_MASK | BLOCK_LINKED_MASK));
+
+ Mem_SetBlockFlags((StartBlock + (ReqBlocks - 1)), BLOCK_USED_MASK);
+
+ for (Handle_Number_t AllocEntry = 0; AllocEntry < NUM_HANDLES; AllocEntry++)
+ {
+ Mem_Handle_t CurrHdl = (Mem_Handle_t)&Mem_MemData.Mem_Handles[AllocEntry];
+
+ if (DEREF(CurrHdl, void*) == NULL)
+ {
+ DEREF(CurrHdl, void*) = &Mem_MemData.Mem_Heap[StartBlock * BLOCK_SIZE];
+ return CurrHdl;
+ }
+ }
+
+ return NULL;
+}
+
+Mem_Handle_t Mem_Realloc(Mem_Handle_t CurrAllocHdl, const Alloc_Size_t Bytes)
+{
+ Mem_Free(CurrAllocHdl);
+ return Mem_Alloc(Bytes);
+}
+
+Mem_Handle_t Mem_Calloc(const Alloc_Size_t Bytes)
+{
+ Mem_Handle_t AllocHdl = Mem_Alloc(Bytes);
+
+ if (AllocHdl != NULL)
+ memset(DEREF(AllocHdl, void*), 0x00, Bytes);
+
+ return AllocHdl;
+}
+
+void Mem_Free(Mem_Handle_t CurrAllocHdl)
+{
+ char* MemBlockPtr = DEREF(CurrAllocHdl, char*);
+ Block_Number_t CurrBlock = ((uint16_t)(MemBlockPtr - Mem_MemData.Mem_Heap) / BLOCK_SIZE);
+ uint8_t CurrBlockFlags;
+
+ if ((CurrAllocHdl == NULL) || (MemBlockPtr == NULL))
+ return;
+
+ do
+ {
+ CurrBlockFlags = Mem_GetBlockFlags(CurrBlock);
+ Mem_SetBlockFlags(CurrBlock, 0);
+
+ CurrBlock++;
+ }
+ while (CurrBlockFlags & BLOCK_LINKED_MASK);
+
+ DEREF(CurrAllocHdl, void*) = NULL;
+}
+
+Block_Number_t Mem_TotalFreeBlocks(void)
+{
+ Block_Number_t FreeBlocks = 0;
+
+ for (Block_Number_t CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++)
+ {
+ if (!(Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK))
+ FreeBlocks++;
+ }
+
+ return FreeBlocks;
+}
+
+Handle_Number_t Mem_TotalFreeHandles(void)
+{
+ Handle_Number_t FreeHandles = 0;
+
+ for (Handle_Number_t CurrHandle = 0; CurrHandle < NUM_HANDLES; CurrHandle++)
+ {
+ if (Mem_MemData.Mem_Handles[CurrHandle] == NULL)
+ FreeHandles++;
+ }
+
+ return FreeHandles;
+}
diff --git a/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h
new file mode 100644
index 00000000..6fd743ea
--- /dev/null
+++ b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h
@@ -0,0 +1,182 @@
+/*
+ LUFA Library
+ Copyright (C) Dean Camera, 2009.
+
+ dean [at] fourwalledcubicle [dot] com
+ www.fourwalledcubicle.com
+*/
+
+/*
+ Copyright 2009 Dean Camera (dean [at] fourwalledcubicle [dot] com)
+
+ Permission to use, copy, modify, and distribute this software
+ and its documentation for any purpose and without fee is hereby
+ granted, provided that the above copyright notice appear in all
+ copies and that both that the copyright notice and this
+ permission notice and warranty disclaimer appear in supporting
+ documentation, and that the name of the author not be used in
+ advertising or publicity pertaining to distribution of the
+ software without specific, written prior permission.
+
+ The author disclaim all warranties with regard to this
+ software, including all implied warranties of merchantability
+ and fitness. In no event shall the author be liable for any
+ special, indirect or consequential damages or any damages
+ whatsoever resulting from loss of use, data or profits, whether
+ in an action of contract, negligence or other tortious action,
+ arising out of or in connection with the use or performance of
+ this software.
+*/
+
+/** \file
+ *
+ * Dynamic, auto-defragmenting block memory allocator library. This library provides a convenient replacement for
+ * the standard avr-libc dynamic memory allocation routines. Memory is handed out in block chunks, to reduce the
+ * management memory overhead.
+ *
+ * Unlike the normal memory allocation routines, this library gives out handles to memory which must be dereferenced
+ * at the exact time of use, rather than handing back direct memory pointers. By using library managed handles
+ * instead of pointers, allocated memory blocks can be shifted around as needed transparently to defragment the
+ * memory as more blocks are requested.
+ *
+ * The memory heap is static, thus the total memory usage of the compiled application (as reported by the avr-size
+ * tool of the AVR-GCC toolchain) includes the dynamic memory heap.
+ *
+ * The constants NUM_BLOCKS, BLOCK_SIZE and NUM_HANDLES must be defined in the project makefile (and passed to the
+ * preprocessor via the -D GCC switch) for this library to compile.
+ *
+ * NUM_BLOCKS indicates the number of memory blocks in the memory psudoheap which can be chaned together and handed
+ * to the application via a memory handle. NUM_HANDLES is the maximum number of memory handles (pointing to one or
+ * more chained memory blocks) which can be handed out simultaneously before requring a handle (and its associated
+ * memory) to be freed. BLOCK_SIZE gives the number of bytes in each memory block.
+ */
+
+#ifndef __DYN_ALLOC__
+#define __DYN_ALLOC__
+
+ /* Includes : */
+ #include <avr/io.h>
+ #include <stdbool.h>
+ #include <string.h>
+
+ /* Preprocessor Checks: */
+ #if (!defined(NUM_BLOCKS) || !defined(BLOCK_SIZE) || !defined(NUM_HANDLES))
+ #error NUM_BLOCKS, BLOCK_SIZE and NUM_HANDLES must be defined before use via makefile.
+ #endif
+
+ /* Public Interface - May be used in end-application: */
+ /* Macros: */
+ /** Macro to dereference a given memory handle into the given type. The given type should be a pointer
+ * if the memory is to contain an array of items, or should be a standard type (such as a primative or
+ * structure) if the memory is to hold a single item of a single type. */
+ #define DEREF(handle, type) (*(type*)handle)
+
+ /** Constant, giving the total heap size in bytes. */
+ #define ALLOCABLE_BYTES (1UL * NUM_BLOCKS * BLOCK_SIZE)
+
+ /* Type Defines: */
+ /** Memory handle type, used to store handles given by the library functions. */
+ typedef const void** Mem_Handle_t;
+
+ #if (ALLOCABLE_BYTES > 0xFFFF) || defined(__DOXYGEN__)
+ /** Type define for the size (in bytes) for an allocation for passing to the library functions.
+ * The exact type width varies depending on the value of ALLOCABLE_BYTES to ensure that a single
+ * allocation can request the entire heap if needed.
+ */
+ typedef uint32_t Alloc_Size_t;
+ #elif (ALLOCABLE_BYTES > 0xFF)
+ typedef uint16_t Alloc_Size_t;
+ #else
+ typedef uint8_t Alloc_Size_t;
+ #endif
+
+ #if (NUM_BLOCKS > 0xFFFF) || defined(__DOXYGEN__)
+ /** Type define for a block number in the heap. The exact type width varies depending on the
+ * value of NUM_BLOCKS to ensure that the type can store an index to any block in the block pool.
+ */
+ typedef uint32_t Block_Number_t;
+ #elif (NUM_BLOCKS > 0xFF)
+ typedef uint16_t Block_Number_t;
+ #else
+ typedef uint8_t Block_Number_t;
+ #endif
+
+ #if (NUM_HANDLES > 0xFFFF) || defined(__DOXYGEN__)
+ /** Type define for a handle number. The exact type width varies depending on the value of NUM_HANDLES
+ * to ensure that the type can store the index of any handle in the handle pool.
+ */
+ typedef uint32_t Handle_Number_t;
+ #elif (NUM_HANDLES > 0xFF)
+ typedef uint16_t Handle_Number_t;
+ #else
+ typedef uint8_t Handle_Number_t;
+ #endif
+
+ /* Function Prototypes: */
+ /** Allocates a given number of blocks from the heap (calculated from the requested number of bytes) and
+ * returns a handle to the newly allocated memory.
+ *
+ * \param Bytes The number of bytes requested to be allocated from the heap
+ *
+ * \return NULL handle if the allocation fails, or handle to the allocated memory if the allocation succeeds
+ */
+ Mem_Handle_t Mem_Alloc(const Alloc_Size_t Bytes);
+
+ /** Allocates a given number of blocks from the heap (calculated from the requested number of bytes) and
+ * returns a handle to the newly allocated memory. Calloced memory is automatically cleared to all 0x00
+ * values at the time of allocation.
+ *
+ * \param Bytes The number of pre-cleared bytes requested to be allocated from the heap
+ *
+ * \return NULL handle if the allocation fails, or handle to the allocated memory if the allocation succeeds
+ */
+ Mem_Handle_t Mem_Calloc(const Alloc_Size_t Bytes);
+
+ /** Deallocates a given memory handle, and attempts to allocates the given number of blocks from the heap
+ * (calculated from the requested number of bytes) immediately following the deallocation. The new memory
+ * may be located in the same area as the previous memory, but this is not guaranteed.
+ *
+ * \param CurrAllocHdl Handle to an already allocated section of memory in the heap to deallocate
+ * \param Bytes The number of bytes requested to be allocated from the heap following the
+ * deallocation
+ *
+ * \return NULL handle if the allocation fails, or handle to the allocated memory if the allocation succeeds
+ *
+ * \warning Even if the allocation fails, the deallocation will still occur. Care should be taken to ensure
+ * that the previously allocated memory is not used following an unsuccessful realloc().
+ */
+ Mem_Handle_t Mem_Realloc(Mem_Handle_t CurrAllocHdl, const Alloc_Size_t Bytes);
+
+ /** Deallocates a given previously allocated section of memory from the heap.
+ *
+ * \param CurrAllocHdl Handle to a previously allocated section of memory in the heap
+ */
+ void Mem_Free(Mem_Handle_t CurrAllocHdl);
+
+ /** Returns the total number of unallocated blocks in the heap.
+ *
+ * \return Number of free blocks in the heap, as a Block_Number_t integer
+ */
+ Block_Number_t Mem_TotalFreeBlocks(void);
+
+ /** Returns the total number of unallocated handles in the handle pool.
+ *
+ * \return Number of free handles in the handle pool, as a Handle_Number_t integer
+ */
+ Handle_Number_t Mem_TotalFreeHandles(void);
+
+ /* Private Interface - For use in library only: */
+ #if !defined(__DOXYGEN__)
+ /* Macros: */
+ #define BLOCK_USED_MASK (1 << 0)
+ #define BLOCK_LINKED_MASK (1 << 1)
+
+ /* Function Prototypes: */
+ #if defined(INCLUDE_FROM_DYNALLOC_C)
+ static uint8_t Mem_GetBlockFlags(const Block_Number_t BlockNum);
+ static void Mem_SetBlockFlags(const Block_Number_t BlockNum, const uint8_t Flags);
+ static void Mem_Defrag(void);
+ #endif
+ #endif
+
+#endif