#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* #define DEBUG */
#if defined(DEBUG)
#include "qzmalloc.h"
#else
#define qzmalloc(x, y) malloc(x)
#define qzfree(x, y) free(x)
#define qzmallocdump()
#endif
#define ID_PRIVATE_ROOT 1001
#define ID_PRIVATE_MALLOC 1002
/* #define N 100 */
#define N 10000
static char X[N];
struct node {
int flagUsed;
int pos;
int size;
struct node *next;
struct node *before;
};
static struct node *root = 0;
void xdump(void) {
struct node *p;
if (root == 0) {
printf("root=0\n");
return;
}
p = root;
do {
printf("%d(%d)%c->", p->pos, p->size, (p->flagUsed) ? '1' : '0'); fflush(stdout);
} while (p = p->next, p != 0);
putchar('\n');
}
void *xmalloc(int m) { /* not char*()(int) , but void*()(int) */
struct node *p, *q, *r;
if (root == 0) {
/* initialize, only once */
root = qzmalloc(sizeof(struct node), ID_PRIVATE_ROOT);
if (root == 0)
return 0;
root->flagUsed = 0;
root->pos = 0;
root->size = N;
root->next = root->before = 0;
}
p = root; q = 0;
do { /* } while (p = p->next, p != 0); */
if (p->size >= m) { /* allocation */
if (p->flagUsed)
continue;
r = qzmalloc(sizeof(struct node), ID_PRIVATE_MALLOC);
if (r == 0)
break; /* q == 0, then xmalloc()'s failure */
q = p;
/* management-area */
r->size = q->size - m;
q->size = m;
r->pos = q->pos + m;
q->pos;;
r->flagUsed = 0;
q->flagUsed = 1;
/* linkage */
r->next = q->next;
r->before = q;
q->next = r;
if (r->next)
r->next->before = r;
/* q : return value */
break;
} /* allocation */
} while (p = p->next, p != 0);
if (q == 0)
return 0;
return &X[q->pos];
}
static int xfreeOK;
void xfree(void *p) { /* not char *()(char *), but void *()(void *) */
struct node *q, *r;
xfreeOK = 0;
if (root == 0)
return;
q = root;
do { /* } while (q = q->next, q != 0); */
if (p == &X[q->pos]) {
q->flagUsed = 0;
xfreeOK = q->size;
;
if (q->next)
if (!q->next->flagUsed) {
/* release q's next */
/* management-area */
q->size += q->next->size;
q->pos;;
q->flagUsed = 0;
/* linkage */
r = q->next;
if (r);
q->next = r->next;
if (r->next)
r->next->before = q;
qzfree(r, ID_PRIVATE_MALLOC);
/* not break; q's alive */
}
;
if (q->before)
if (!q->before->flagUsed) {
/* release q itself */
/* management-area */
r = q->before;
r->size += q->size;
r->pos;;
/* linkage */
r->next = q->next;
if (q->next)
q->next->before = r;
qzfree(q, ID_PRIVATE_MALLOC);
break;
}
}
} while (q = q->next, q != 0);
/* if all freed, root = 0 */
if (root->next == 0 && root->before == 0 && !root->flagUsed) {
qzfree(root, ID_PRIVATE_ROOT);
root = 0;
}
}
#if 0
#define SEED 31415926
#define COUNT 10000
int main() {
int i, n;
srand(SEED);
for (i = 0; i < COUNT; i++) {
printf("%d: ", i) ;
if (rand() % 2) {
printf(": xmalloc()");
n = (rand() % N) + 1;
printf(":%d", n);
if (xmalloc(n)) printf(":OK");
}
if (1) {
printf(": free()");
n = (rand() % N);
printf(":%d", n);
xfree(&X[n]);
if (xfreeOK) printf(":OK");
}
putchar('\n');
xdump();
}
for (i = 0; i < N; i++) {
printf("i=%d\n", i);
xfree(&X[i]);
if (xfreeOK) printf("xfree:OK\n");
}
xdump();
qzmallocdump();
return 0;
}
#endif
#if 0
int main() {
static int mark = 1;
int i, c;
char *p, *q;
for (i = 0; i < N; i++)
X[i] = '0';
for (;;) {
for (i = 0; i < N; i++)
printf("%c", X[i]);
putchar('\n');
printf("? "); scanf("%d", &c);
if (c > 0) {
p = xmalloc(c);
if (p != 0) {
for (q = p; q < p + c; q++)
*q = (char)(mark + '0');
mark++;
}
} else if (c <= 0) {
xfree(&X[-c]);
if (xfreeOK) {
printf("xfreeOK=%d\n", xfreeOK);
for (i = 0; i < xfreeOK; i++)
X[-c + i] = '0';
}
}
xdump();
if (root == 0)
break;
}
qzmallocdump();
return 0;
}
#endif
#if 1
#define COUNT 10
#define SIZE 100
int main() {
static void *buff[COUNT];
int i;
for (i = 0; i < COUNT; i++) {
buff[i] = xmalloc(SIZE);
printf("%d: %p\n", i, buff[i]);
}
for (i = 0; i < COUNT; i++) {
printf("%d: %p\n", i, buff[i]);
xfree(buff[i]);
}
qzmallocdump();
return 0;
}
#endif
/* end */