1/* @LICENSE(CUSTOM) */ 2 3/* An implementation of malloc as described in the K&R C programming book */ 4 5#include <allocman/mspace/k_r_malloc.h> 6#include <stddef.h> /* For NULL */ 7#include <stdlib.h> 8#include <string.h> /* For memcpy */ 9 10void mspace_k_r_malloc_init(mspace_k_r_malloc_t *k_r_malloc, size_t cookie, k_r_malloc_header_t * (*morecore)(size_t cookie, mspace_k_r_malloc_t *k_r_malloc, size_t new_units)) 11{ 12 k_r_malloc->freep = NULL; 13 k_r_malloc->cookie = cookie; 14 k_r_malloc->morecore = morecore; 15} 16 17void *mspace_k_r_malloc_alloc(mspace_k_r_malloc_t *k_r_malloc, size_t nbytes) 18{ 19 k_r_malloc_header_t *p, *prevp; 20 size_t nunits; 21 nunits = (nbytes + sizeof(k_r_malloc_header_t) - 1) / sizeof(k_r_malloc_header_t) + 1; 22 if ((prevp = k_r_malloc->freep) == NULL) { /* no free list yet */ 23 k_r_malloc->base.s.ptr = k_r_malloc->freep = prevp = &k_r_malloc->base; 24 k_r_malloc->base.s.size = 0; 25 } 26 for (p = prevp->s.ptr;; prevp = p, p = p->s.ptr) { 27 if (p->s.size >= nunits) { /* big enough */ 28 if (p->s.size == nunits) { /* exactly */ 29 prevp->s.ptr = p->s.ptr; 30 } else { /* allocate tail end */ 31 p->s.size -= nunits; 32 p += p->s.size; 33 p->s.size = nunits; 34 } 35 k_r_malloc->freep = prevp; 36 return (void *) (p + 1); 37 } 38 if (p == k_r_malloc->freep) { /* wrapped around free list */ 39 if ((p = (k_r_malloc_header_t *) k_r_malloc->morecore(k_r_malloc->cookie, k_r_malloc, nunits)) == NULL) { 40 return NULL; /* none left */ 41 } else { 42 /* Put the thing in */ 43 p->s.size = nunits; 44 mspace_k_r_malloc_free(k_r_malloc, p + 1); 45 p = k_r_malloc->freep; 46 } 47 } 48 } 49} 50 51void mspace_k_r_malloc_free(mspace_k_r_malloc_t *k_r_malloc, void *ap) 52{ 53 k_r_malloc_header_t *bp, *p; 54 55 if (ap == NULL) { 56 return; 57 } 58 59 bp = (k_r_malloc_header_t *) ap - 1; /* point to block header */ 60 for (p = k_r_malloc->freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) 61 if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) { 62 break; /* freed block at start or end of area */ 63 } 64 65 if (bp + bp->s.size == p->s.ptr) { /* join to upper nbr */ 66 bp->s.size += p->s.ptr->s.size; 67 bp->s.ptr = p->s.ptr->s.ptr; 68 } else { 69 bp->s.ptr = p->s.ptr; 70 } 71 72 if (p + p->s.size == bp) { /* join to lower nbr */ 73 p->s.size += bp->s.size; 74 p->s.ptr = bp->s.ptr; 75 } else { 76 p->s.ptr = bp; 77 } 78 79 k_r_malloc->freep = p; 80 81} 82