Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: Manage an unknown number of objects without malloc

Reply
Thread Tools

Re: Manage an unknown number of objects without malloc

 
 
HENRY Eshbaugh
Guest
Posts: n/a
 
      08-30-2011
On Aug 27, 3:31*am, pozz <(E-Mail Removed)> 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[i])) {
> * * * * *freefile = &files[i];
> * * * * *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.
 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      09-25-2011
On Aug 30, 6:18*am, HENRY Eshbaugh <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
 
Uno
Guest
Posts: n/a
 
      09-25-2011
On 9/25/2011 1:09 AM, Malcolm McLean wrote:
> On Aug 30, 6:18 am, HENRY Eshbaugh<(E-Mail Removed)> 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
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      09-25-2011
On Sep 25, 1:52*pm, Uno <(E-Mail Removed)> 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
 
Reply With Quote
 
Uno
Guest
Posts: n/a
 
      09-27-2011
On 9/25/2011 4:57 AM, Malcolm McLean wrote:
> On Sep 25, 1:52 pm, Uno<(E-Mail Removed)> 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
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      09-27-2011
On Sep 27, 7:06*am, Uno <(E-Mail Removed)> wrote:
> On 9/25/2011 4:57 AM, Malcolm McLean wrote:
>
> > On Sep 25, 1:52 pm, Uno<(E-Mail Removed)> *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.

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      09-27-2011
Malcolm McLean <(E-Mail Removed)> 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.
 
Reply With Quote
 
Uno
Guest
Posts: n/a
 
      09-27-2011
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

 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      09-27-2011
On Sep 27, 12:54*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
> Malcolm McLean <(E-Mail Removed)> 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.




 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Manage an unknown number of objects without malloc Ian Collins C Programming 1 08-28-2011 08:07 PM
Assign an unknown value to an unknown variable Vincent Arnoux Ruby 1 08-11-2006 06:12 PM
How to allocate mem without using malloc() & free without using free() Rajshekhar C Programming 5 03-29-2005 06:03 PM
free'ing malloc'd structure with malloc'd members John C Programming 13 08-02-2004 11:45 AM
Re: free'ing malloc'd structure with malloc'd members ravi C Programming 0 07-30-2004 12:42 PM



Advertisments