//----------------------------------------------------------- // // Memory library ( Malloc, Free, Defrag ) // // // Author: Mattias Hansson // Copyright (c) : 2000-2025 Mattias Hansson // License: GNU LGPL 2 // Language: 65CM v0.4+ // Dependencies: // Target: generic 6502 // // Purpose: Dynamic memory allocation using free list // with heap defragmentation support // // Modernized with: // - Free list algorithm // - ZP pointer for array-style access // - Heap defragmentation (coalesces adjacent free blocks) // - Free list statistics //----------------------------------------------------------- //----------------------------------------------------------- // Internals: // // Free list memory allocator. // // Block structure: // - Free blocks: [size:WORD][next:WORD][...free space...] // - Allocated blocks: [size:WORD][...user data...] // // User receives pointer to data area (block + 2). // Size field includes 2-byte header. // // ZP usage (can be overridden): // - $fa-$fb: current block pointer // // Functions: // lib_mem_init - Initialize heap with one large free block // lib_mem_malloc - Allocate memory block // lib_mem_free - Release allocated memory block // lib_mem_defrag - Coalesce adjacent free blocks (maintenance) // lib_mem_stats - Return free list statistics //----------------------------------------------------------- #IFNDEF __LIB_MEM #DEFINE __LIB_MEM = 1 #PRAGMA _P_USE_LONG_JUMP 1 #IFNDEF __LIB_MEM_START #DEFINE __LIB_MEM_START = $$5000 #IFEND #IFNDEF __LIB_MEM_END #DEFINE __LIB_MEM_END = $$9fff #IFEND #IFNDEF __LIB_MEM_ZP_CURRENT #DEFINE __LIB_MEM_ZP_CURRENT = $$fa #IFEND #IFNDEF NULL #DEFINE NULL = 0 #IFEND GOTO lib_memlib_skip WORD lib_memlib_current WORD lib_memlib_free_head //----------------------------------------------------------- // Init: Initialize heap with one large free block //----------------------------------------------------------- FUNC lib_mem_init WORD current @ __LIB_MEM_ZP_CURRENT WORD CONST memstart = __LIB_MEM_START WORD CONST memend = __LIB_MEM_END lib_memlib_free_head = memstart lib_memlib_current = memstart current = lib_memlib_current WORD CONST total_size = memend-memstart+1 POKEW current[0] , total_size POKEW current[2] , NULL FEND //----------------------------------------------------------- // Malloc: Allocate memory block // Returns pointer to user data area or NULL if no space //----------------------------------------------------------- FUNC lib_mem_malloc({WORD size_t} out:{WORD result}) WORD current @ __LIB_MEM_ZP_CURRENT WORD prev WORD block_size WORD needed_size WORD remaining WORD next_free WORD split_addr WORD alloc_addr result = NULL IF size_t = 0 EXIT ENDIF needed_size = size_t + 2 current = lib_memlib_free_head prev = NULL WHILE current != NULL block_size = PEEKW current[0] IF block_size >= needed_size next_free = PEEKW current[2] alloc_addr = current remaining = block_size - needed_size IF remaining >= 6 POKEW current[0] , needed_size split_addr = current + needed_size current = split_addr POKEW current[0] , remaining POKEW current[2] , next_free IF prev = NULL lib_memlib_free_head = split_addr ELSE current = prev POKEW current[2] , split_addr ENDIF ELSE IF prev = NULL lib_memlib_free_head = next_free ELSE current = prev POKEW current[2] , next_free ENDIF ENDIF result = alloc_addr + 2 EXIT ENDIF prev = current WORD temp temp = PEEKW current[2] current = temp WEND FEND //----------------------------------------------------------- // Free: Release allocated memory block //----------------------------------------------------------- FUNC lib_mem_free({WORD m_ptr}) WORD current @ __LIB_MEM_ZP_CURRENT WORD block_start IF m_ptr = NULL EXIT ENDIF block_start = m_ptr - 2 current = block_start POKEW current[2] , lib_memlib_free_head lib_memlib_free_head = block_start FEND //----------------------------------------------------------- // Defrag: Walk heap and merge adjacent free blocks //----------------------------------------------------------- FUNC lib_mem_defrag WORD current @ __LIB_MEM_ZP_CURRENT WORD scan_addr WORD next_addr WORD block_size WORD next_size WORD prev_free WORD free_node WORD next_next WORD CONST memstart = __LIB_MEM_START WORD CONST memend = __LIB_MEM_END scan_addr = memstart WHILE scan_addr < memend current = scan_addr block_size = PEEKW current[0] IF block_size = 0 EXIT ENDIF current = lib_memlib_free_head prev_free = NULL free_node = NULL WHILE current != NULL IF current = scan_addr free_node = current BREAK ENDIF prev_free = current WORD _tmpx _tmpx = PEEKW current[2] current = _tmpx WEND IF free_node != NULL next_addr = scan_addr + block_size WHILE next_addr < memend current = next_addr next_size = PEEKW current[0] IF next_size = 0 EXIT ENDIF current = lib_memlib_free_head prev_free = NULL free_node = NULL WHILE current != NULL IF current = next_addr free_node = current BREAK ENDIF prev_free = current _tmpx = PEEKW current[2] current = _tmpx WEND IF free_node = NULL BREAK ENDIF current = next_addr next_next = PEEKW current[2] IF prev_free = NULL lib_memlib_free_head = next_next ELSE current = prev_free POKEW current[2] , next_next ENDIF block_size = block_size + next_size current = scan_addr POKEW current[0] , block_size next_addr = scan_addr + block_size WEND ENDIF current = scan_addr block_size = PEEKW current[0] scan_addr = scan_addr + block_size WEND FEND //----------------------------------------------------------- // Stats: Return free list statistics // free_blocks - Number of entries in the free list // total_free - Total free bytes // largest_free - Size of largest free block //----------------------------------------------------------- FUNC lib_mem_stats(out:{WORD free_blocks} out:{WORD total_free} out:{WORD largest_free}) WORD current @ __LIB_MEM_ZP_CURRENT WORD block_size free_blocks = 0 total_free = 0 largest_free = 0 current = lib_memlib_free_head WHILE current != NULL block_size = PEEKW current[0] free_blocks = free_blocks + 1 total_free = total_free + block_size IF block_size > largest_free largest_free = block_size ENDIF WORD _tmpx _tmpx = PEEKW current[2] current = _tmpx WEND FEND LABEL lib_memlib_skip #PRAGMA _P_USE_LONG_JUMP 0 #IFEND