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