source: trunk/mem.c @ 1

Last change on this file since 1 was 1, checked in by moo, 9 years ago

initial import to online

File size: 5.5 KB
Line 
1#include <php.h>
2#include <stdlib.h>
3#include "mem.h"
4#include "align.h"
5#define PADD(p, a) (((char*)p) + a)
6
7// {{{ mem
8struct _xc_block_t {
9#ifdef ALLOC_DEBUG
10    unsigned int magic;
11#endif
12    xc_memsize_t size; /* reserved even after alloc */
13    xc_block_t *next;  /* not used after alloc */
14};
15
16struct _xc_mem_t {
17    xc_memsize_t size;
18    xc_memsize_t avail;       /* total free */
19    xc_block_t headblock[1];  /* just as a pointer to first block*/
20};
21
22#ifndef offsetof
23#   define offsetof(type, field) ((int) ((char *) &((type *) 0)->field))
24#endif
25#define SizeOf(type, field) sizeof( ((type *) 0)->field )
26#define BLOCK_HEADER_SIZE() (ALIGN( offsetof(xc_block_t, size) + SizeOf(xc_block_t, size) ))
27
28#define BLOCK_MAGIC ((unsigned int) 0x87655678)
29
30/* }}} */
31static inline void xc_block_setup(xc_block_t *b, xc_memsize_t size, xc_block_t *next) /* {{{ */
32{
33#ifdef ALLOC_DEBUG
34    b->magic = BLOCK_MAGIC;
35#endif
36    b->size = size;
37    b->next = next;
38}
39/* }}} */
40#ifdef ALLOC_DEBUG
41static void xc_block_check(xc_block_t *b) /* {{{ */
42{
43    if (b->magic != BLOCK_MAGIC) {
44        fprintf(stderr, "0x%X != 0x%X magic wrong \n", b->magic, BLOCK_MAGIC);
45    }
46}
47/* }}} */
48#else
49#   define xc_block_check(b) do { } while(0)
50#endif
51
52
53void *xc_mem_malloc(xc_mem_t *mem, xc_memsize_t size) /* {{{ */
54{
55    xc_block_t *prev, *cur;
56    xc_block_t *newb, *b;
57    xc_memsize_t realsize;
58    xc_memsize_t minsize;
59    void *p;
60    /* [xc_block_t:size|size] */
61    realsize = BLOCK_HEADER_SIZE() + size;
62    /* realsize is ALIGNed so next block start at ALIGNed address */
63    realsize = ALIGN(realsize);
64
65    do {
66        p = NULL;
67        if (mem->avail < realsize) {
68            break;
69        }
70
71        b = NULL;
72        minsize = INT_MAX;
73
74        /* prev|cur */
75
76        for (prev = mem->headblock; prev->next; prev = cur) {
77            /* while (prev->next != 0) { */
78            cur = prev->next;
79            xc_block_check(cur);
80            if (cur->size == realsize) {
81                /* found a perfect fit, stop searching */
82                b = prev;
83                break;
84            }
85            /* make sure we can split on the block */
86            else if (cur->size > (sizeof(xc_block_t) + realsize) &&
87                    cur->size < minsize) {
88                /* cur is acceptable and memller */
89                b = prev;
90                minsize = cur->size;
91            }
92            prev = cur;
93        }
94
95        if (b == NULL) {
96            break;
97        }
98
99        prev = b;
100
101        cur = prev->next;
102        p = PADD(cur, BLOCK_HEADER_SIZE());
103
104        /* update the block header */
105        mem->avail -= realsize;
106
107        /*perfect fit, just unlink */
108        if (cur->size == realsize) {
109            prev->next = cur->next;
110            break;
111        }
112
113        /* make new free block after alloced space */
114
115        /* save, as it might be overwrited by newb (cur->size is ok) */
116        b = cur->next;
117
118        /* prev|cur     |next=b */
119
120        newb = (xc_block_t *)PADD(cur, realsize);
121        xc_block_setup(newb, cur->size - realsize, b);
122        cur->size = realsize;
123        /* prev|cur|newb|next
124         *            `--^
125         */
126
127#ifdef ALLOC_DEBUG
128        fprintf(stderr, "avail: %d (%dKB). size: %d %d (%dKB) new next: %p offset: %d %dKB\n"
129                , mem->avail, mem->avail/1024
130                , size
131                , realsize, realsize/1024
132                , newb
133                , ((char*)newb - mem->rw), ((char*)newb - mem->rw) / 1024
134                );
135#endif
136        prev->next = newb;
137        /* prev|cur|newb|next
138         *    `-----^
139         */
140
141    } while (0);
142
143    return p;
144}
145/* }}} */
146int xc_mem_free(xc_mem_t *mem, const void *p) /* {{{ return block size freed */
147{
148    xc_block_t *cur, *b;
149    int size;
150
151    cur = (xc_block_t *) (((char *) p) - BLOCK_HEADER_SIZE());
152    xc_block_check(cur);
153    assert((char*)mem < (char*)cur && (char*)cur < (char*)mem + mem->size);
154
155    /* find free block right before the p */
156    b = mem->headblock;
157    while (b->next != 0 && b->next < cur) {
158        b = b->next;
159    }
160
161    /* restore block */
162    cur->next = b->next;
163    b->next = cur;
164    size = cur->size;
165
166    mem->avail += size;
167
168    /* combine prev|cur */
169    if (PADD(b, b->size) == (char *)cur) {
170        b->size += cur->size;
171        b->next = cur->next;
172        cur = b;
173    }
174
175    /* combine cur|next */
176    b = cur->next;
177    if (PADD(cur, cur->size) == (char *)b) {
178        cur->size += b->size;
179        cur->next = b->next;
180    }
181    return size;
182}
183/* }}} */
184void *xc_mem_calloc(xc_mem_t *mem, xc_memsize_t memb, xc_memsize_t size) /* {{{ */
185{
186    xc_memsize_t realsize = memb * size;
187    void *p = xc_mem_malloc(mem, realsize);
188
189    memset(p, 0, realsize);
190    return p;
191}
192/* }}} */
193void *xc_mem_realloc(xc_mem_t *mem, const void *p, xc_memsize_t size) /* {{{ */
194{
195    void *newp = xc_mem_malloc(mem, size);
196    memcpy(newp, p, size);
197    xc_mem_free(mem, p);
198    return newp;
199}
200/* }}} */
201char *xc_mem_strndup(xc_mem_t *mem, const char *str, xc_memsize_t len) /* {{{ */
202{
203    void *p = xc_mem_malloc(mem, len + 1);
204    memcpy(p, str, len + 1);
205    return p;
206}
207/* }}} */
208char *xc_mem_strdup(xc_mem_t *mem, const char *str) /* {{{ */
209{
210    return xc_mem_strndup(mem, str, strlen(str));
211}
212/* }}} */
213
214xc_memsize_t xc_mem_avail(xc_mem_t *mem) /* {{{ */
215{
216    return mem->avail;
217}
218/* }}} */
219xc_memsize_t xc_mem_size(xc_mem_t *mem) /* {{{ */
220{
221    return mem->size;
222}
223/* }}} */
224
225const xc_block_t *xc_mem_freeblock_first(xc_mem_t *mem) /* {{{ */
226{
227    return mem->headblock->next;
228}
229/* }}} */
230const xc_block_t *xc_mem_freeblock_next(const xc_block_t *block) /* {{{ */
231{
232    return block->next;
233}
234/* }}} */
235xc_memsize_t xc_mem_block_size(const xc_block_t *block) /* {{{ */
236{
237    return block->size;
238}
239/* }}} */
240xc_memsize_t xc_mem_block_offset(const xc_mem_t *mem, const xc_block_t *block) /* {{{ */
241{
242    return ((char *) block) - ((char *) mem);
243}
244/* }}} */
245
246xc_mem_t *xc_mem_init(void *ptr, xc_memsize_t size) /* {{{ */
247{
248    xc_mem_t *mem = (xc_mem_t *) ptr;
249    xc_block_t  *b;
250
251    mem->size = size;
252    mem->avail = size - ALIGN(sizeof(xc_mem_t));
253
254    /* pointer to first block */
255    b = mem->headblock;
256    xc_block_setup(b, 0, (xc_block_t *)(mem + ALIGN(sizeof(xc_mem_t))));
257
258    /* first block*/
259    b = b->next;
260    xc_block_setup(b, mem->avail, 0);
261
262    return mem;
263}
264/* }}} */
265void xc_mem_destroy(xc_mem_t *mem) /* {{{ */
266{
267}
268/* }}} */
Note: See TracBrowser for help on using the repository browser.