/*
 * $Id: test_malloc.c,v 1.4 2000/11/03 17:19:49 wessels Exp $
 */

/*
 * test_malloc
 * 
 * The idea is to call malloc and free very often while maintaining a "constant"
 * sized total memory area.  The probability of calling malloc or free is
 * proportional to the size of the memory area. Internally I track the sum of
 * all allocated blocks.  Due to malloc overheads, the process size is
 * significantly larger.
 * 
 * Each malloc'd block must be at least 4 bytes.  The size of the block is stored
 * in the first 4 bytes.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <assert.h>
#include <time.h>
#include <string.h>

#define URANDOM "/dev/urandom"
#define USAGE "usage: %s -t mbytes\n"

typedef struct _hash hash;
typedef struct _hashitem hashitem;

struct _hashitem {
    void *key;
    hashitem *next;
    void *data;
};

struct _hash {
    hashitem **buckets;
    int nbuckets;
    int nelem;
};

extern hash *hashCreate(int);
extern void *hashLookup(hash *, void *);
extern void hashInsert(hash *, void *, void *);
extern void hashDelete(hash *, void *);
extern void *hashRandom(hash *);

int checkdup = 0;

void *
hashRandom(hash * h)
{
    int b;
    hashitem *i;
    do {
	b = random() % h->nbuckets;
	i = h->buckets[b];
    } while (NULL == i);
    while (i->next)
	i = i->next;
    return i->data;
}

hash *
hashCreate(int n)
{
    hash *h = calloc(1, sizeof(*h));
    h->nbuckets = n;
    h->buckets = calloc(h->nbuckets, sizeof(*h->buckets));
    return h;
}

void *
hashLookup(hash * h, void *key)
{
    int b = (int) key % h->nbuckets;
    hashitem *i;
    for (i = h->buckets[b]; i; i = i->next)
	if (key == i->key)
	    return i->data;
    return NULL;
}

void
hashInsert(hash * h, void *data, void *key)
{
    int b = (int) key % h->nbuckets;
    hashitem *i;
    if (checkdup)
	for (i = h->buckets[b]; i; i = i->next)
	    assert(key != i->key);
    i = calloc(1, sizeof(*i));
    i->key = key;
    i->data = data;
    i->next = h->buckets[b];
    h->buckets[b] = i;
    h->nelem++;
}

void
hashDelete(hash * h, void *key)
{
    int b = (int) key % h->nbuckets;
    hashitem **I;
    hashitem *i;
    for (I = &h->buckets[b]; *I; I = &(*I)->next) {
	if ((*I)->key != key)
	    continue;
	i = *I;
	*I = i->next;
	free(i);
	break;
    }
    h->nelem--;
}

int
main(int argc, char *argv[])
{
    hash *h = hashCreate(65537);
    int cursize = 0;
    int maxsize;
    double p;
    double x;
    int s;
    void *y;
    const char *progname = strdup(argv[0]);
    int nalloc = 0;
    int nfree = 0;
    int nop = 0;
    int rndfd = -1;
    int ch;
    while ((ch = getopt(argc, argv, "td")) != -1) {
	switch (ch) {
	case 't':
	    rndfd = open(URANDOM, O_RDONLY);
	    if (rndfd < 0) {
		perror(URANDOM);
		return 1;
	    }
	    break;
	case 'd':
	    checkdup = 1;
	    break;
	case '?':
	default:
	    fprintf(stderr, USAGE, progname);
	    return 1;
	    break;

	}
    }
    argc -= optind;
    argv += optind;
    if (1 != argc) {
	fprintf(stderr, USAGE, progname);
	return 1;
    }
    srandom(time(NULL));
    maxsize = atoi(argv[0]) << 21;
    assert(0 < maxsize);
    for (;;) {
	p = (double) random() / (double) 0x7fffffff;
	x = (double) cursize / (double) maxsize;
	if (p < x) {
	    y = hashRandom(h);
	    assert(y);
	    memcpy(&s, y, sizeof(s));
	    assert(s > 0 && s < 0x10000);
	    cursize -= s;
	    hashDelete(h, y);
	    free(y);
	    nfree++;
	} else {
	    do {
		s = random() & 0x7FC;
	    } while (s < sizeof(s));
	    y = malloc(s);
	    if (rndfd > -1)
		read(rndfd, y, s);
	    memcpy(y, &s, sizeof(s));
	    hashInsert(h, y, y);
	    cursize += s;
	    nalloc++;
	}
	nop++;
	if ((nop & 0xFF) == 0)
	    if (rndfd > -1 || 0 == (nop & 0x3FFF))
		printf("%d MB, %d ptrs, %d alloc, %d free\n",
		    cursize >> 20, h->nelem, nalloc, nfree);
    }
}