Re: Manage an unknown number of objects without malloc

Discussion in 'C Programming' started by HENRY Eshbaugh, Aug 30, 2011.

  1. On Aug 27, 3:31 am, pozz <> wrote:
    > I'm writing a software on an embedded platform, with a C compiler that
    > hasn't malloc/free facilities, so the allocation can't be dynamic.
    >
    > I'd like to mimic the standard I/O functions in one of my API to let the
    > user developer manage several objects.  I, as the library developer,
    > don't know how many objects will be used by the user developer.
    >
    > Consider the fopen:
    >
    >    FILE * fopen (const char *filename, const char *opentype)
    >
    > The mechanism is simple: the I/O library doesn't know in advance how
    > many files the user developer will want to manage at the same time, so
    > fopen() dynamically allocates the FILE object and returns it if the
    > operation is successful.
    >
    > How may I mimic this behaviour in my API?  Now I have two possibilities,
    > but I couldn't choose one.
    >
    > First approach.  The code that calls the function should allocate the
    > FILE object and pass it to the API functions.  The fopen function will be:
    >
    >    int myfopen (FILE *stream, const char *filename, const char *opentype)
    >
    > The con of this approach is that the function interface is different so
    > it will be costly, in the future, to switch to a platform with
    > malloc/free facilities (where I'll use an interface similar to standard
    > I/O functions).
    >
    > Second approach.  Adding an intermediate level that allocates and manage
    > a maximum number of objects (configurable as a probject basis).
    >
    >    /* middle_level.c */
    >    FILE files[CONFIG_MAXFILES];
    >
    >    FILE * myfopen (const char *filename, const char *opentype) {
    >      FILE *freefile = NULL;
    >      unsigned int i;
    >      for (i = 0; i < CONFIG_MAXFILES; i++) {
    >        if (file_isused(&files)) {
    >          freefile = &files;
    >          break;
    >        }
    >      }
    >      if (freefile == NULL) {
    >        return NULL;
    >      }
    >      myfopen_low(freefile, filename, opentype);
    >      return freefile;
    >    }
    >
    > Every time I need a new FILE object (like in myfopen), instead of
    > dynamically allocation, I have to search for a free (not used) object in
    > the files[] array.  In other words, I create a micro and simple dynamic
    > allocation facilities that manage only FILE object.
    >
    > What do you suggest?  Are there any other better approaches?


    Write your own malloc(). Read the kmalloc() implementation in the
    Linux kernel, plus the stuff on caching.
     
    HENRY Eshbaugh, Aug 30, 2011
    #1
    1. Advertising

  2. On Aug 30, 6:18 am, HENRY Eshbaugh <> wrote:
    >
    > Write your own malloc(). Read the kmalloc() implementation in the
    > Linux kernel, plus the stuff on caching.
    >

    If there's no malloc(), there's usually a good reason for that, which
    is that resources are so constrained that the tiny memory pool will
    fragment and the function start returning nulls in no time.

    However you can implement a stack allocator. Simply pop and push
    regions on the stack. This means that all memory you allocate has to
    be freed in strict reverse order, and only the stack top can be
    reallocated. Most small programs can be written to obey these rules.
    (The exception is when you need a tree or graph like structure).
    --
    Memory games. Malloc(), fixed-size allocators, and stack allocators.
    Just one chapter in Basic Algorithms, a massive compendium of C
    resources
    http://www.malcolmmclean.site11.com/www
     
    Malcolm McLean, Sep 25, 2011
    #2
    1. Advertising

  3. HENRY Eshbaugh

    Uno Guest

    On 9/25/2011 1:09 AM, Malcolm McLean wrote:
    > On Aug 30, 6:18 am, HENRY Eshbaugh<> wrote:
    >>
    >> Write your own malloc(). Read the kmalloc() implementation in the
    >> Linux kernel, plus the stuff on caching.
    >>

    > If there's no malloc(), there's usually a good reason for that, which
    > is that resources are so constrained that the tiny memory pool will
    > fragment and the function start returning nulls in no time.


    If there's no malloc(), get your money back. 2 gigs is disposable now.
    >
    > However you can implement a stack allocator. Simply pop and push
    > regions on the stack. This means that all memory you allocate has to
    > be freed in strict reverse order, and only the stack top can be
    > reallocated. Most small programs can be written to obey these rules.
    > (The exception is when you need a tree or graph like structure).


    All structures are graph-like. Some are trivial.
    --
    Uno
     
    Uno, Sep 25, 2011
    #3
  4. On Sep 25, 1:52 pm, Uno <> wrote:
    >
    > All structures are graph-like.  Some are trivial.
    >

    Most are trivial. Most short programs can be written with nested
    arrays, and a flat array is virtually always the best choice for such
    programs. Only occasionally do you need nodes with pointers to other
    nodes.

    --
    Alice in Wonderland card game. Will the Queen chop off your head?
    http://www.malcolmmclean.site11.com/www
     
    Malcolm McLean, Sep 25, 2011
    #4
  5. HENRY Eshbaugh

    Uno Guest

    On 9/25/2011 4:57 AM, Malcolm McLean wrote:
    > On Sep 25, 1:52 pm, Uno<> wrote:
    >>
    >> All structures are graph-like. Some are trivial.
    >>

    > Most are trivial. Most short programs can be written with nested
    > arrays, and a flat array is virtually always the best choice for such
    > programs. Only occasionally do you need nodes with pointers to other
    > nodes.


    Can you relate a graph structure to C? For example, can you describe
    graphs that correspond to anything in K&R2?

    I'd like to show the thermodynamics of steel in its graph
    interpretation, as it exists in contemporary steel structures.

    Cowboys won!
    --
    Uno
     
    Uno, Sep 27, 2011
    #5
  6. On Sep 27, 7:06 am, Uno <> wrote:
    > On 9/25/2011 4:57 AM, Malcolm McLean wrote:
    >
    > > On Sep 25, 1:52 pm, Uno<>  wrote:

    >
    > >> All structures are graph-like.  Some are trivial.

    >
    > > Most are trivial. Most short programs can be written with nested
    > > arrays, and a flat array is virtually always the best choice for such
    > > programs. Only occasionally do you need nodes with pointers to other
    > > nodes.

    >
    > Can you relate a graph structure to C?  For example, can you describe
    > graphs that correspond to anything in K&R2?
    >

    struct edge
    {
    struct node *node1;
    struct node *node2;
    int direction; /* 0 = undirected, 1 = node1 -> node2, 2 = node2 ->
    node 1, 3 = bidirectional */
    double weight;
    void *data;
    };

    struct node
    {
    struct edge **incoming;
    int Nin;
    struct edge **outgoing;
    int Nout;
    void *data;
    };

    struct graph
    {
    struct edge *edges;
    int Nedges;
    struct node *node;
    int Nnodes;
    struct node *root; /* can be null */
    };

    You can build arrays, stacks, linked lists from these structures.
    However normally that's overkill.
     
    Malcolm McLean, Sep 27, 2011
    #6
  7. Malcolm McLean <> writes:
    <snip>
    > struct edge
    > {
    > struct node *node1;
    > struct node *node2;
    > int direction; /* 0 = undirected, 1 = node1 -> node2, 2 = node2 ->
    > node 1, 3 = bidirectional */
    > double weight;
    > void *data;
    > };


    In my experience, most algorithms on directed graphs end up simpler if
    the directionality of the edge is implicit in the nodes, i.e. that an
    edge always goes from node1 to node2. Have you it helpful to have the
    directionality stored?

    > struct node
    > {
    > struct edge **incoming;
    > int Nin;
    > struct edge **outgoing;
    > int Nout;
    > void *data;
    > };


    That involves a lot of redundancy (maybe that's a good thing -- it
    depends) which imposes a cost on some operations. With all data
    structures it's worth pointing out what they are good at and what they
    are less good at. For example, flipping an edge's direction is quite
    complex with this structure but finding all the outgoing edges from some
    node is very simple. The optimal data structure will depend on the
    algorithm.

    You might, for example, simply have presented a 2D bit matrix as the
    representation of a graph. For some algorithms that's both compact and
    efficient. My point being that no one should come away thinking that
    the above is "the" way to map a graph to a C data structure.

    <snip last structure>
    --
    Ben.
     
    Ben Bacarisse, Sep 27, 2011
    #7
  8. HENRY Eshbaugh

    Uno Guest

    On 9/27/2011 1:09 AM, Malcolm McLean wrote:

    > struct edge
    > {
    > struct node *node1;
    > struct node *node2;
    > int direction; /* 0 = undirected, 1 = node1 -> node2, 2 = node2 ->
    > node 1, 3 = bidirectional */
    > double weight;
    > void *data;
    > };



    If mein Gedankenexperiment is to be realized in C, I think we need a
    different node. Imagine a universe populated by only space and steel.

    I'll admit that in the realm of universes, this one counts as pretty
    parochial, because the whole darn thing is plum, level, square, where
    every node has order 6.
    >
    > struct node
    > {
    > struct edge **incoming;
    > int Nin;
    > struct edge **outgoing;
    > int Nout;
    > void *data;
    > };
    >
    > struct graph
    > {
    > struct edge *edges;
    > int Nedges;
    > struct node *node;
    > int Nnodes;
    > struct node *root; /* can be null */
    > };


    As far as heat transfer goes, it won't get worse than -k^2dx locally.
    The magic question is how small this universe must be in order to
    collapse locally to an energy source.

    Anti-regime protests everywhere in Amiland,
    --
    Uno
     
    Uno, Sep 27, 2011
    #8
  9. On Sep 27, 12:54 pm, Ben Bacarisse <> wrote:
    > Malcolm McLean <> writes:
    >
    > <snip>
    >
    > > struct edge
    > > {
    > >   struct node *node1;
    > >   struct node *node2;
    > >   int direction; /* 0 = undirected, 1 = node1 -> node2, 2 = node2 ->
    > > node 1, 3 = bidirectional */
    > >   double weight;
    > >   void *data;
    > > };

    >
    > In my experience, most algorithms on directed graphs end up simpler if
    > the directionality of the edge is implicit in the nodes, i.e. that an
    > edge always goes from node1 to node2.  Have you it helpful to have the
    > directionality stored?
    >

    No, it's more to make the structure self-documenting. By examining a
    filled edge structure, you can know what you're looking at.
    (Undirected and bidirectional edges are the same in any algorithm I
    can think of, but not logically the same. A distance matrix of cities
    on a Cartesian plain is undirected, a road time matrix is
    bidirectional).


    > > struct node
    > > {
    > >   struct edge **incoming;
    > >   int Nin;
    > >   struct edge **outgoing;
    > >   int Nout;
    > >   void *data;
    > > };

    >
    > That involves a lot of redundancy (maybe that's a good thing -- it
    > depends) which imposes a cost on some operations.  With all data
    > structures it's worth pointing out what they are good at and what they
    > are less good at.
    >

    That structure is good for relatively sparse graphs with medium
    numbers of edges and nodes, where you're unlikely to edit the
    structure much but you need to traverse it often. You can easily
    enumerate either the edges or the nodes, and you can get from a node
    to an edge or an edge to a node very easily. Lazy deletions can be
    O(1), as can most additions (you need a good realloc()), but to do it
    properly is O(N). It also makes it cheap to hang data off edges.
    However normally you just need a flag for an edge to show if it has
    been visited.
     
    Malcolm McLean, Sep 27, 2011
    #9
    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. Robert Scarborough

    Manage State of COM objects

    Robert Scarborough, Jul 17, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    314
    Robert Scarborough
    Jul 17, 2003
  2. Martin Maercker

    JNI - how to manage C++ objects from Java?

    Martin Maercker, Jan 16, 2005, in forum: Java
    Replies:
    2
    Views:
    3,514
    Chris Uppal
    Jan 18, 2005
  3. Rajshekhar
    Replies:
    5
    Views:
    2,159
    Jonathan Bartlett
    Mar 29, 2005
  4. Ian Collins
    Replies:
    1
    Views:
    320
    Ian Collins
    Aug 28, 2011
  5. Vincent Arnoux
    Replies:
    1
    Views:
    251
    Arnaud Bergeron
    Aug 11, 2006
Loading...

Share This Page