statically allocated data structures source?

Discussion in 'C Programming' started by Thomas Paul Diffenbach, Jul 11, 2003.

  1. 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?
     
    Thomas Paul Diffenbach, Jul 11, 2003
    #1
    1. Advertising

  2. Thomas Paul Diffenbach

    Kevin Easton Guest

    Thomas Paul Diffenbach <usenet@..my-last-name...org> wrote:
    > 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.
     
    Kevin Easton, Jul 11, 2003
    #2
    1. Advertising

  3. On Fri, 11 Jul 2003 06:58:44 UTC, Thomas Paul Diffenbach
    <usenet@..my-last-name...org> wrote:

    > 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[i].phead == NULL) continue;
    if (pn >= blocklist[i].phead && pn < blocklist[i].pfooter) {
    if (blocklist[i].type) {
    pn -= sizeof(FREEMIDICHUNK);
    freemidichunk(blocklist[i].phead, blocklist[i].pfooter,
    pn);
    return;
    } else {
    if (pn & 1) pn--;
    else pn -= sizeof(FREEMINICHUNK);
    freeminichunk(blocklist[i].phead, blocklist[i].pfooter,
    pn);
    return;
    }
    }
    }
    free(pn);
    }



    --
    Tschau/Bye

    Herbert Rosenau
    [url]http://www.pc-rosenau.de[/url] eComStation Reseller in Germany
    eCS 1.1 GA englisch wird jetzt ausgeliefert[/i][/i][/i][/i][/i][/i][/i][/i]
     
    Herbert Rosenau, Jul 11, 2003
    #3
  4. Thomas Paul Diffenbach

    Malcolm Guest

    "Thomas Paul Diffenbach" <usenet@..my-last-name...org> wrote in message
    >
    > 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.
     
    Malcolm, Jul 11, 2003
    #4
  5. Thomas Paul Diffenbach

    David Rubin Guest

    Herbert Rosenau wrote:

    > 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

    --
    FORTRAN was the language of choice
    for the same reason that three-legged races are popular.
    -- Ken Thompson, "Reflections on Trusting Trust"
     
    David Rubin, Jul 12, 2003
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    5
    Views:
    623
    Matt Wharton
    Dec 9, 2004
  2. Replies:
    4
    Views:
    439
    Joe Wright
    May 25, 2005
  3. Alfonso Morra
    Replies:
    11
    Views:
    720
    Emmanuel Delahaye
    Sep 24, 2005
  4. Replies:
    6
    Views:
    374
    Army1987
    Sep 24, 2007
  5. kuangye
    Replies:
    3
    Views:
    548
    Philip Semanchuk
    Mar 13, 2011
Loading...

Share This Page