176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * free.c 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Very simple linked-list based malloc()/free(). 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdlib.h> 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "malloc.h" 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct free_arena_header *__free_block(struct free_arena_header *ah) 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *pah, *nah; 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah = ah->a.prev; 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah = ah->a.next; 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (pah->a.type == ARENA_TYPE_FREE && 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (char *)pah + pah->a.size == (char *)ah) { 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Coalesce into the previous block */ 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah->a.size += ah->a.size; 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah->a.next = nah; 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->a.prev = pah; 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DEBUG_MALLOC 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.type = ARENA_TYPE_DEAD; 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah = pah; 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah = ah->a.prev; 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Need to add this block to the free chain */ 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.type = ARENA_TYPE_FREE; 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->next_free = __malloc_head.next_free; 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->prev_free = &__malloc_head; 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __malloc_head.next_free = ah; 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->next_free->prev_free = ah; 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* In either of the previous cases, we might be able to merge 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman with the subsequent block... */ 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (nah->a.type == ARENA_TYPE_FREE && 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (char *)ah + ah->a.size == (char *)nah) { 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.size += nah->a.size; 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Remove the old block from the chains */ 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->next_free->prev_free = nah->prev_free; 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->prev_free->next_free = nah->next_free; 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.next = nah->a.next; 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->a.next->a.prev = ah; 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DEBUG_MALLOC 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->a.type = ARENA_TYPE_DEAD; 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Return the block that contains the called block */ 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return ah; 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanvoid free(void *ptr) 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *ah; 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!ptr) 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return; 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah = (struct free_arena_header *) 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ((struct arena_header *)ptr - 1); 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __free_block(ah); 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Here we could insert code to return memory to the system. */ 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 74