statically allocated data structures source?

  • Thread starter Thomas Paul Diffenbach
  • Start date
T

Thomas Paul Diffenbach

Can anyone point me to an open source library of /statically
allocated/ data structures?

I'm writing some code that would benefit from trees, preferably self
balancing, but on an embedded system that doesn't offer dynamic
memory allocation (to be clear: no malloc, no realloc), and with
rather tight memory constraints.

Writing my own malloc to do dynamic allocation from some static pool
isn't really an option, for various reasons, not all of which are
technical.

Of course, I can write my own structures (or port them), but I'd
prefer to not cover myself in glory re-inventing the wheel (and
besides, I think SCO claims the patent on "wheel" already).

On a more general note, if I were looking for C++ code, I'd know to
start at boost.org (if the C++ STL didn't already have what I
needed); is there anything similar to boost.org for C?
 
K

Kevin Easton

Thomas Paul Diffenbach said:
Can anyone point me to an open source library of /statically
allocated/ data structures?

I'm writing some code that would benefit from trees, preferably self
balancing, but on an embedded system that doesn't offer dynamic
memory allocation (to be clear: no malloc, no realloc), and with
rather tight memory constraints.

Writing my own malloc to do dynamic allocation from some static pool
isn't really an option, for various reasons, not all of which are
technical.

Can't you just replace the malloc() and free() calls in one of the
already-existing ADT libraries with calls to functions that acquire and
release a structure from a static pool?

- Kevin.
 
H

Herbert Rosenau

Can anyone point me to an open source library of /statically
allocated/ data structures?

I'm writing some code that would benefit from trees, preferably self
balancing, but on an embedded system that doesn't offer dynamic
memory allocation (to be clear: no malloc, no realloc), and with
rather tight memory constraints.

Writing my own malloc to do dynamic allocation from some static pool
isn't really an option, for various reasons, not all of which are
technical.

The following code is at ALPHA state and may be yet buggy and is not
threadsave yet.

As you have no malloc you should
#define malloc(n) NULL
to get a NULL pointer as a result from any call of malloc, because
you'll always unable to increase the predifined chunk of memory.

The code is based on the idea that if you have to allocate lots of
very, very small chunks of memory malloc's internal management
structures can cost more memory than the data itself requires. The
idea was born as I have to develop an application that uses lots of
little structures (bounded to trees or lists and lots of really short
strings whereas all of: number of structs/strings are really unknown,
but high, size of each is low, values are totally unknown because the
data is externally based and changes dayly multiple times.

I've defined 2 differen internal structures:
*mini* = chunks of less than 60 bytes
an used chunk costs only 2x4 bits (1 byte) management
structure
an unused chunk 4 bytes management structure
(2x4 bits flags and 3 octets size)
chunk sizes given to the caller:
min: 3 bytes for HRstrdup() (effective 4 bytes used)
4 bytes for HRmalloc() (effective 8 bytes used)
4 bytes internal usage because the
delivered address must be aligned
max: 60 bytes
between: rounded up to multiple of 4
HRstrdup: (multiple of 4) - 1
*midi* = chunks of more than 60 but less than 2 KB in size
whereas the management structure is never more than 8 bytes
low.
chunk sizes given to the caller:
min: 4 bytes (effective 8 bytes used)
max: 2044 bytes
*maxi* = the size of the management structure doesn't matter because
the chunk needed is more than 2 KB big - and rare. In
this case the functions only wrappers to malloc().
If you've a need for dynamically memory of that size
you've to write your own functions like the ones above.

As I can uses malloc as fallback I start the initialisation with
malloc to get one big contunous memory block of each chunk type and in
case this one is full it can be run itself in a linked list to be
extended to more blocks. So you have to change this to make there a
static initialiastion of the base structure to let them point to
initial memory blocks of an appropiate size. Be sure to get a NULL
pointer back when the inital memory blocks have not enough free space
to fullify a requirement.

HRstrdup() works like strdup() but will come back mostenly with an
unaligned pointer, because strings are always allowed to start on
unaligned addresses. Whereas HRmalloc will deliver in any case an
aligned address, because stucts have to start on aligned addresses to
get theyr members aligned. It is HRmalloc() which finds out by itself
which of the 3 chunk types are needed.

HRfree give a chunk back to the free list. Whereas a freelist member
can grow up to the block size, a used member is limited to the
maximale size the chunk type defines.

The routines are written to be thrifty to CPU usage, because the
frequency they are used may be very high.

The routines are highly sensitive to size overrun! But that is because
one can not have both, very low memory usage and insensitiveness
bounded with thrift in CPU usage. So care of the programmer using this
is strictly required.


user interfaces:
Init_mem() initialiation of the internal memory data structures
to be called at top of main() to get all the
following functions useable
HRmalloc() like malloc, but uses less memory whenever possible
HRstrmalloc() like HRmalloc, but returns unaligned pointer
for thrifty memory usage.
HRstrdup() like strdup() but returns unaligned pointer
for thrifty memory usage
duplicate strings (e.g. "..." to be changeable)
HRmemdup() like strdup() but returns aligned pointer
makes it easy to duplicate structures


HRfree() frees a chunk for reuse


-------------HRmemory.c-----------------
/* make inline compiler independant */
#define INLINE _inline

/* chunks for a minimal memory usage
*/
/* that means memory blocks of up to 60 Bytes
*/
/* hold memory usage so short as ever possible!
*/

/* describes a used mini chunk
*/
/* a mini chunk has the absolutely needed number of bits used to save
memory */
/* as ever possible.
*/
/*
*/
/* The application doesn't need to know which type of chunk is used!
*/
/*
*/
/* A mini chunk holds space up to 60 bytes, including the '\0' char on
*/
/* strings, excluding the one byte header
*/
/*
*/
/* As the standard requires to return pointers aligned to hold any
type of */
/* data pointers all functions allocationg memory will follow this
rule */
/* - except HRstring.... The HRstring family returns explicity char *,
*/
/* that means unaligned pointers to string. That is because the
memory */
/* administration uses only one byte, so a string can use up to 3
bytes */
/* without requirering an extra byte to get a pointer aligned
*/
/* The memory administration itself uses only aligned pointers.
*/
/* Any string function knows of the problematic of unaligned pointers,
but */
/* is ready to handle them to save memory as possible.
*/
/*
*/
/* There are 3 different block types to save memory as possible:
*/
/* - mini works with chunk sizes of 4 bytes only
*/
/* malloc() itself has a relative high overhead for its
own */
/* management. So it costs often more bytes for
malloc() */
/* internal management than the app needs for a piece
of data. */
/* Most of malloced data blocks are very little, so lot
of */
/* memory gets spent for only malloc internal things.
*/
/* The mini blocks are created to save any byte that
can ever */
/* saved to get more room for user data.
*/
/* Whereas 4 is the number of bytes used round up to
the */
/* next possible alignment. As the free list is
integrated */
/* it differs from the used list insofar that it needs
all */
/* 4 bytes for itself, but the used list requires only
the */
/* very first one.
*/
/* The chunk size is defined at least through the needs
*/
/* of the free list. Because the free list can contain
only */
/* one chunk for the whole block
*/
/* the size value is always a multiple of 4 to the
respect */
/* of the needs to deliver aligned pointers.
*/
/* - midi a compromise between the need to save memory usage
as */
/* ever possible, the need to hold big numbers in the
free list*/
/* and the usage of so less memory as possible for a
single */
/* piece of data that is a bit bigger than a handful
bytes. */
/* As this type of list is only used when the
requirement for */
/* an chunk exceeds the maximum size a mini chunk can
hold */
/* and the size of an used entry is limited to
2040/2044 */
/* aligned/unaligned, the list can contain only entries
with */
/* at least one byte longer than the mini list.
*/
/* So the administration uses one byte for used entries
and */
/* 4 bytes for the size of unused ones, makes up to 8
bytes. */
/* - high big chunks have no need to save low number of bytes,
*/
/* so we can simply let do malloc anything it can do.
*/
/* The absolute number of chunks with the usage of a
high */
/* of bytes is low, so the administrative overhead a
chunk may */
/* is relative low, no relevant storage save can
occure. */


/* Block containing mini chunks
*/

/* used mini chunks
*/
/*
*/
/* me == 0 ? chunk is free, see free mini chunks
*/
/* : number of reserved 4 bytes for this chunk
*/
/* parent == 0 ? parent chunk is free. we can join this chunk to it
*/
/* when this chunk gets free'd
*/
/*
*/

/* set alignment to bytes */
#pragma pack(1)
typedef struct {
char me : 4; /* own size in multiple of 4 bytes
*/
/* if 0 then this chunk is free
*/
/* see freeminichunk
*/
char parent : 4; /* parents size in multiple of 4 bytes
*/
/* if 0 then parents chunk is free, see
*/
/* freeminichunk
*/
} MINICHUNKHEAD, *PMINICHUNKHEAD;



/* free mini chunks
*/
/*
*/
/* head see MINICHUNKHEAD above
*/
/*
*/
/* high the high byte of the total size this chunk has
*/
/* low high << 16 + low is the total number of 4 bytes this
*/
/* chunk holds.
*/
/*
*/
/* As a chunk is always 4 bytes or a multiple of 4 bytes long, there
is */
/* would be a problem of finding the head of an chunk if we need it.
*/
/* We'd resolved that by having the head repeated as footer:
*/
/*
*/
/* head
*/
/* <optional free bytes>
*/
/* footer (exactly the same data as head
*/
/*
*/
/* The shortest possible chunk has head and footer overlapping
exactly. */
/* In that case changing the head changes the same information on the
footer */
/* and changing the footer changes the same information on the head.
*/
/* So it can occure that we change the same bytes twice, because we
don't */
/* check for overlapping.
*/
/*
*/
/* As we always request and free memory in multiple sizes of
MINICHUNKHEAD */
/* we've always one of 3 cases occureing:
*/
/*
*/
/*
*/
/* Requested size: number of heads used
*/
/* <= 4 1 head and footer overlaps
*/
/* <= 8 2 footer follows head
immediately */
/* > 8 >2 some number of heads -2 free
between */
/*
*/
/* In practice there is no difference in handling the three cases!
*/
/* because we know always one of them:
*/
/* - we should split a free chunk to 1 used, 1 free:
*/
/* 1. round the requested size (+ 1 head size) to the next higher
headsize) */
/* 2. create there the reminding free chunk by filling in the
management */
/* data, do the same with the current footer
*/
/* 3. create the used chunk by changing me to the calculated use
size */
/* when the split results in 0 heads free: change the next's chunk
*/
/* parent field to the size the now used chunk has
*/
/* - we get a chunk back:
*/
/* 1. parent chunk is free
*/
/* add the size of the now free chunk to the parents size
*/
/* copy the head as footer into the last 4 bytes of the now free
one */
/* change the parent of the next chunk to show there that it is
free */
/* 2. parent is not free: nothing to do for this
*/
/* 3. next chunk is free
*/
/* join the next chunk as if it were the current one
*/
/* So we handle only FREEMINICHUNK size blocks we have never a problem
*/
/* with getting heads overlapping unaligned.
*/

typedef struct {
MINICHUNKHEAD head; /* .me is 0, parent ma be or may be not
0 */
char high; /* high byte of chunk size in multiple
of */
/* 4 bytes.
*/
USHORT low; /* low word of free bytes
/* size = (high * sizeof(short) + low)
<< 2 */
} FREEMINICHUNK, *PFREEMINICHUNK;

/* return to default alignment */
#pragma pack()


/* chunks for memory usage of 60 and more bytes but less than 2040
bytes */
/* this chunk type uses at least 8 bytes for its free list
*/
typedef struct {
char me; /* own size in multiple of 4 bytes
*/
/* if 0 then this chunk is free,
*/
char parent; /* parents size in multiple of 4 bytes
*/
/* if 0 then parents chunk is free,
*/
/* see freemidichunk
*/
} MIDICHUNK, *PMIDICHUNK;

/* head for free MIDICHUNKS
*/
/* Handling is the same as for mini chunks, except that the struct
itself */
/* differs from.
*/
typedef struct {
MIDICHUNKHEAD head; /* same as midichunk
*/
ULONG size; /* size of bytes of free chunk
*/
} FREEMIDICHUNK, *PFREEMIDICHUNK;


typedef FREEMIDICHUNK *PFREEMIDIFOOT;
typedef FREEMIDICHUNK *PFREEMIDIFOOT;



/* As we handle different type of chunks we need different blocks for
each. */
/*
*/
/* A block is a very big amount of memory, allocated from the OS to
get be */
/* splitted in chunks of dynamic sizes for separate use by the
application. */
/*
*/
/* We don't use malloc() for little chunks to reduce the overhead
malloc */
/* itself needs to do the same work.
*/
/*
*/
/* As an OS may have some low limits in the number of blocks it can
assign to */
/* an application we try to get an very high amount of bytes for each
block */
/* we use to split in small chunks. So the number of OS calls should
be */
/* limited to a real low one where the usage of the number of chunks
should */
/* be incredible high.
*/
/*
*/

/* Master base memory allocation
*/
/*
*/
/* We differ on
*/
typedef struct {
PVOID phead; /* a block starts here */
PVOID pfooter; /* foot of last available chunk
*/
USHORT type; /* 0: minichunk, 1 midichunk
*/
USHORT ixnext; /* index to next block of that type
*/
USHORT ixpre; /* index to previous block of that type
*/
} BLOCK, *PBLOCK;




/* it is possible to buy up to 12 blocks from OS */
#define BLOCKSIZE 32 * 1024 * 1024 - 64 /* a bit less than
multiples of */
/* full pages to let room for malloc()
internal */
/* storage without extra page
*/
#define MAXBLOCKS 12 /* the system should give us at least 12
block */
/* to split them to mini/midi chunks
*/

static USHORT blocks = 0;
static BLOCK *blocklist[MAXBLOCKS]; /* we start with no blocks */

#define SETMINISIZE(p, s) /
p->high = s >> 16; /
p->low = s & 0xffff;

#define GETMINISIZE(p) /
(p->high << 16) + p->low;


/* function: usemini
*/
/*
*/
/* usemini(pminifreechunk, no_of_chunks)
*/
/*
*/
/* change the state of the chunk from free to used. Split the chunk if
it is */
/* bigger than required.
*/
/* if split is required:
*/
/* - create a new chunk immediately the current one, containing
*/
/* - parents field set with the size of the required one
*/
/* - the new own free size,
*/
/* - the new footer field with the correct data in
*/
/* if chunk size matches the required size exactly
*/
/* - change next chunks parent field to in use by setting the size of
the */
/* active chunk
*/
/*
*/
/* parameters:
*/
/* PMINIFREECHUNK pchunk pointer to chunk to get in usage
*/
/* size_t no_of_chunks the number of chunks going in use
*/
/* this is the number of bytes requested +
*/
/* 1 chunk size for management, rounded
*/
/* - down when unaligned data
*/
/* - up when aligned data
*/
/* pointer requested by the app.
*/
/*
*/
/* return:
*/
/* NULL when something failed
*/
/* pchunk the incomming, unchanged pointer
*/

INLINE PFREEMINICHUNK usemini(PFREEMINICHUNK p, size_t req) {
PFREEMINICHUNK pchild;
size_t size;

if (!(size = p->head.me)) {
/* self is free */
size = GETMINISIZE(p); /* free size of current chunk
*/
p->head.me = req; /* chunk now in use
*/
pchild = p + req; /* address next chunk
*/
pchild->head.parent = req; /* size of now used chunk
*/
/* flags the next chunk to its
parent */
/* is in use
*/
if (size == req) {
/* newly reserved chunk matches required size exactly */
return p; /* done */
}
/* chunk must be splitted! */
pchild->head.me = 0; /* new chunk is free */
size -= req; /* size of new chunk */
SETMINISIZE(pchild, size); /* set free size */
pchild += size - 1; /* change footer */
pchild->head.me = 0; /* free */
pchild->head.parent = req; /* parent is used */
SETMINISIZE(pchild, size);
/* old parent lives unchanged because its parent is a free one
*/
return p;
}
/* we've a problem! memory management seems defective */
return NULL;
}

/* function: usemini
*/
/*
*/
/* freemini(pchunk)
*/
/*
*/
/* parameters:
*/
/*
*/
/* PFREEMINICHUNK pchunk pointer to chunk to get free'd
*/
/*
*/
/* return:
*/
/*
*/
/* NULL some kind of error
*/
/* PFREEMINICHUNK same pointer as received
*/

_inline PFREEMINICHUNK freemini(PFREEMINICHUNK p) {
PFREEMINICHUNK pchild;
size_t size;

if (!(size = p->head.me)) {
/* self is free */
/* we've a problem! memory management seems defective */
return NULL;
}
if (!p->head.parent) {
pchild = p - 1; /* parent is free, so increase its
size */
p -= GETMINISITE(pchild);
size += GETMINISIZE(p);
}
p->head.me = 0; /* mark chunk as free */
pchild = p + size; /* inspect ooter */
if (!pchild->head.me) {
pchild--;
size += GETMINISIZE(pchild);
pchild = p + size;
}
pchild--; /* create footer */
SETMINISIZE(p, size); /* size of free chunk */
pchild->head.me = 0; /* free */
pchild->head.parent = p->head.parent;
SETMINISIZE(pchild, size); /* size in footer */
pchild++;
pchild->head.parent = 0; /* parent is now free */
return p;
}



/* return negative value if an error occures or the index to the newly
*/
/* created block */
static int mkminiblock(void) {
PMINIFREECHUNK pmini = malloc(BLOCKSIZE);
PMINIFREECHUNK pminifree = pmini;
ULONG s = BLOCKSIZE / sizeof(FREEMINICHUNK); /* number of chunks
*/
ULONG cs = s * sizeof(FREEMINICHUNK); /* number of bytes useable
*/
int i = 0;
int ix = 0;

if (!pmini) return -1; /* no memory */

for (i = 0; i < MAXBLOCKS; i++) {
if (blocklist.phead) {
if (blocklist.type) continue;
ix = i;
continue;
}
blocklist.phead = pmini;
blocklist.pfooter = pminifree + s - 1;
blocklist.type = 0;
blocklist.ixpre = ix;
blocklist[ix].ixnext = i;
pmini->head.me = 0;
pmini->head.parent = 0;
pminifree->head.me = 0;
pminifree->head.parent = 0;
pminifree->high = cs >> 16;
pminifree->low = cs & 0xffff;
pminifree += s - 1;
pminifree->head.me = 0;
pminifree->head.parent = 0;
pminifree->high = cs >> 16;
pminifree->low = cs & 0xffff;
blocks++;
return i;
}
return -1;

}

static int mkmidiblock(void) {
PMIDICHUNK pmidi = malloc(BLOCKSIZE);
PMIDIFREECHUNK pmidifree = pmidi;
ULONG s = BLOCKSIZE / sizeof(FREEMIDICHUNK); /* number of chunks
*/
ULONG cs = s * sizeof(FREEMIDICHUNK); /* number of bytes useable
*/
int i = 0;

if (!pmidi) return -1; /* no memory */

for (i = 0; i < MAXBLOCKS; i++) {
if (blocklist.phead) {
if (blocklist.type != 1) continue;
ix = i;
continue;
}
blocklist.phead = pmidi;
blocklist.pfooter = pmidifree + s - 1);
blocklist.type = 1;
blocklist.ixpre = ix;
blocklist[ix].ixnext = i;
pmidi->me = 0;
pmidi->parent = 0;
pmidifree->head.me = 0;
pmidifree->head.parent = 0;
pmidifree->size = cs;
pmidifree += s - 1;
pmidifree->head.me = 0;
pmidifree->head.parent = 0;
pmidifree->size = cs;
blocks++;
return i;
}
return -1;
}

int init_mem(void) {
if (mkminiblock() < 0) return 1;
if (mkmidiblock() < 0) return 1;
return 0;
}

/* return: 0: nothing done, >0: number of chuncs compressed */
static int reorg_mini_chunks(PBLOCK pb) {
PFREEMINICHUNK pnext = pb->phead;
PFREEMINICHUNK palt = 0;
PFREEMINICHUNK pmini;
size_t s_s;
size_t s_n;
int f = 0;
int rc = 0;

for (; pnext <= pb->pfooter; ) {
if (pnext->me) {
/* in use */
pnext += pnext->me;
continue;
}
/* free chunk. next one free too? */
pmini = pnext;
s_s = GETMINISIZE(pmini);
s_n = s_s;
pnext += s_s;
for (f = 0; !pnext->me; pnext += s_s) {
s_s = GETMINISIZE(pnext);
s_n += s_s;
rc++; /* chunks to concatenate */
f++;
}
if (!f) continue; /* only a single free block */
SETMINISIZE(pmini, s_n); /* concatenate */

palt = pnext - 1; /* footer */
palt->me = 0;
palt->parent = pmini->parent;
SETMINISIZE(palt, s_n);
}
return rc;
}

/* return: 0: nothing done, >0: number of chuncs compressed */
static int reorg_midi_chunks(PBLOCK pb) {
PFREEMIDICHUNK pnext = pb->phead;
PFREEMIDICHUNK palt = 0;
PFREEMIDICHUNK pmini;
size_t s_s;
size_t s_n;
int rc = 0;

for (; pnext <= pb->pfooter; ) {
if (pnext->me) {
/* in use */
pnext += pnext->me;
continue;
}
/* free chunk. next one free too? */
pmini = pnext;
s_s = pmini->size;
s_n = s_s;
pnext += s_s;
for (; !pnext->me; pnext += s_s) {
s_s = pnext->size;
s_n += s_s;
}
pmini->size = s_n;

pnext->parent = 0; /* parent is free */
palt = pnext - 1; /* footer */
palt->me = 0;
palt->parent = pmini->parent;
palt->size = s_n;
rc++;
}
return rc;
}

static PFREEMINICHUNK split_mini_chunk(PFREEMINICHUNK pm, size_t s) {
PFREEMINICHUNK pnext = pm;
PFREEMINICHUNK palt = NULL;
PFREEMINICHUNK pmini;
size_t s_s = (pm->high << 16) + pm->low;
size_t cur_s = s_s - s; /* left free */

pnext->me = s; /* pm is now in use */
pnext += s; /* split position */

/* old next is now next after new free */
palt = pm + s_s; /* old next */
palt->parent = 0;
palt--; /* go to footer */
palt->me = 0;
palt->parent = 0;
palt->high = cur_s >> 16;
palt->low = cur_s &0xffff;

/* new free chunk */
pnext->me = 0; /* new free chunk */
pnext->parent = s; /* used parents size */
pnext->high = cur_s >> 16;
pnext->low = cur_s &0xffff;
return pm;
}

static PFREEMIDICHUNK split_midi_chunk(PFREEMIDICHUNK pm, size_t s) {
PFREEMIDICHUNK pnext = pm;
PFREEMIDICHUNK palt = NULL;
PFREEMIDICHUNK pmini;
size_t s_s = pm->size;
size_t cur_s = s_s - s; /* left free */

pnext->me = s; /* pm is now in use */
pnext += s; /* split position */

/* old next is now next after new free */
palt = pm + s_s; /* old next */
palt->parent = 0;
palt--; /* go to footer */
palt->me = 0;
palt->parent = 0;
palt->size = cur_s;

/* new free chunk */
pnext->me = 0; /* new free chunk */
pnext->parent = s; /* used parents size */
pnext->size = cur_s;
return pm;
}

static PFREEMINICHUNK findminichunk(PBLOCK pb, size_t s) {
PFREEMINICHUNK pnext = pb->phead;
PFREEMINICHUNK palt = 0;
PFREEMINICHUNK pmini;
size_t cur_s = BLOCKSIZE; /* fikive maximum */
size_t s_s;

for (pnext = pb->phead; pnext <= pb->pfooter; ) {
if (pnext->me) {
/* in use */
pnext += pnext->me;
continue;
}
/* free chunk */
pmini = pnext;
s_s = (pmini->high << 16) + pmini->low;
pnext += s_s;
if (s_s == s) {
/* exact match! footer == head */
pmini->me = s; /* no more free */
return pmini;
}
if (s_s < (s + 2)) continue;
if (s_s < cur_s) {
cur_s = s_s; /* minim chunk size we can split */
palt = pmini;
}
}
if (cur_s == BLOCKSIZE) {
/* no chunk found */
if (reorg_mini_chunks(pb))
return findminichunk(pb, s);
return NULL;
} else {
return split_mini_chunk(palt, s);
}
}

static PFREEMIDICHUNK findmidichunk(PBLOCK pb, size_t s) {
PFREEMIDICHUNK pnext = pb->phead;
PFREEMIDICHUNK palt = 0;
PFREEMIDICHUNK pmini;
size_t cur_s = BLOCKSIZE; /* fikive maximum */
size_t s_s;

for (pnext = pb->phead; pnext <= pb->pfooter; ) {
if (pnext->me) {
/* in use */
pnext += pnext->me;
continue;
}
/* free chunk */
pmini = pnext;
s_s = (pmini->high << 16) + pmini->low;
pnext += s_s;
if (s_s == s) {
/* exact match! footer == head */
pmini->me = s; /* no more free */
return pmini;
}
if (s_s < (s + 2)) continue;
if (s_s < cur_s) {
cur_s = s_s; /* minim chunk size we can split */
palt = pmini;
}
}
if (cur_s == BLOCKSIZE) {
/* no chunk found */
if (reorg_midi_chunks(pb))
return findmidichunk(pb, s);
return NULL;
} else {
return split_midi_chunk(palt, s);
}
}

static PFREEMINICHUNK mkminichunk(size_t s) {
PFREEMINICHUNK *p;
int i;

for (i = 0; i < blocks; i++) {
if (blocklist.phead) {
if (blocklist.type) continue;
if ((p = findminichunk(&blocklist, s) != NULL) {
return p;
}
}
}
if ((i = mkminiblock()) < 0) return NULL;
return findminichunk(&blocklist, s);
}

static PFREEMIDICHUNK mkmidichunk(size_t s) {
PFREEMIDICHUNK *p;
int i;

for (i = 0; i < blocks; i++) {
if (blocklist.phead) {
if (!blocklist.type) continue;
if ((p = findmidichunk(&blocklist, s) != NULL) {
return p;
}
}
}
if ((i = mkmidiblock()) < 0) return NULL;
return findmidichunk(&blocklist, s);
}

void *HRmalloc(size_t s) {
size_t cs = s >> 2;
unsigned int cr = s & 3;
char *p;

if (cr) cs++; /* round up */
cs++; /* need 4 bytes for chunk head */
if (cs <= (0x0f) {
p = mkminichunk(cs);
return p ? p + 4 : NULL;
}
if (s <= 0x0fff) {
p = mkmidichunk(cs);
return p ? p + 4 : NULL;
}
return malloc(s);
}

/* function HRstrmalloc
*/
/*
*/
/* HRstrmalloc(size_t s)
*/
/*
*/
/* Parameter:
*/
/* size_t s number of chars to allocate
*/
/* includes the '\0' byte!
*/
/*
*/
/* return: type char *
*/
/* == NULL no memory available
*/
/* 1= NULL pointer to first useable byte
*/
/* ready to hold s bytes
*/
void *HRstrmalloc(size_t s) {
size_t s_s = (s + sizeof(MINICHUNKHEAD)) >> 2;
char *p;

if (s_s <= 0x0f) {
p = mkminichunk(s_s); /* 1 - 3 bytes free
if (p) p += sizeof(MINICHUNKHEAD); /* reserve size of head at
top */
return p;
}
return HRmalloc(s);
}

void *HRstrdup(void *pv) {
size_t s = strlen(pv) + 1;
char *p = HRstrmalloc(s);

return p ? strcpy(p, pv) ? NULL;
}

void *HRmemdup(void *pv, size_t s) {
char *p = HRmalloc(s);

if (!p) return p;
return memcpy(p, pv, s);
}


static void freeminichunk(PFREEMINICHUNK pm, PFREEMINICHUNK pf, char
*pc) {
PFREEMINICHUNK pmini = (PFREEMINICHUNK) pc;
PFREEMINICHUNK pnext;
size_t s_s = 0;

#ifdef(MEMDBG)
for (pnext = pm; pnext < pf; pnext += s_s) {
#endif
s_s = pnext->me ? s_s = pnext->me
: (pnext->high << 16) + pnext->low;
#ifdef(MEMDBG)
if (pmini != pnext) continue;
#endif
pmini->high = s_s >> 16;
pmini->low = s_s &0xffff;
pmini->me = 0;
return;
#ifdef(MEMDBG)
}
#endif
}

void HRfree(void *pn) {
int i;

if (!pn) return;
for (i = 0; i < MAXBLOCKS; i++) {
if (blocklist.phead == NULL) continue;
if (pn >= blocklist.phead && pn < blocklist.pfooter) {
if (blocklist.type) {
pn -= sizeof(FREEMIDICHUNK);
freemidichunk(blocklist.phead, blocklist.pfooter,
pn);
return;
} else {
if (pn & 1) pn--;
else pn -= sizeof(FREEMINICHUNK);
freeminichunk(blocklist.phead, blocklist.pfooter,
pn);
return;
}
}
}
free(pn);
}



--
Tschau/Bye

Herbert Rosenau
http://www.pc-rosenau.de eComStation Reseller in Germany
eCS 1.1 GA englisch wird jetzt ausgeliefert
 
M

Malcolm

Thomas Paul Diffenbach said:
Can anyone point me to an open source library of /statically
allocated/ data structures?

I'm writing some code that would benefit from trees, preferably self
balancing, but on an embedded system that doesn't offer dynamic
memory allocation (to be clear: no malloc, no realloc), and with
rather tight memory constraints.
If the nodes are fixed size, then it is very easy to write your own
allocation library. It is even easier if the nodes already contain a pointer
to their own type.

You simply declare an array of the structures of the size you want. Then you
construct a linked list using the pointer (if your structure doesn't contain
such a pointer, you need to declare a union).
You then have a "head" pointer.
To allocate, point the head pointer to the next in the list and return the
old value.
To free, set the self pointer in the structure to be freed to the head
pointer, then set the head pointer to the address of the structure to be
freed.
 
D

David Rubin

Herbert said:
The following code is at ALPHA state and may be yet buggy and is not
threadsave yet.

[snip - too long and poorly formatted]

You spelled "incoming" incorrectly.

HTH,

/david
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top