Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #10905 > unrolled thread

Re: Manage an unknown number of objects without malloc

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Manage an unknown number of objects without malloc Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-25 01:09 -0700
    Re: Manage an unknown number of objects without malloc Uno <merrilljensen@q.com> - 2011-09-25 04:52 -0700
      Re: Manage an unknown number of objects without malloc Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-25 04:57 -0700
        Re: Manage an unknown number of objects without malloc Uno <merrilljensen@q.com> - 2011-09-26 22:06 -0700
          Re: Manage an unknown number of objects without malloc Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-27 01:09 -0700
            Re: Manage an unknown number of objects without malloc Uno <merrilljensen@q.com> - 2011-09-27 04:17 -0700
            Re: Manage an unknown number of objects without malloc Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-27 11:54 +0100
              Re: Manage an unknown number of objects without malloc Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-27 04:43 -0700

#10905 — Re: Manage an unknown number of objects without malloc

On Aug 30, 6:18 am, HENRY Eshbaugh <henryeshba...@gmail.com> 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

[toc] | [next] | [standalone]

#10909

On 9/25/2011 1:09 AM, Malcolm McLean wrote:
> On Aug 30, 6:18 am, HENRY Eshbaugh<henryeshba...@gmail.com>  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

[toc] | [prev] | [next] | [standalone]

#10913

On Sep 25, 1:52 pm, Uno <merrilljen...@q.com> 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

[toc] | [prev] | [next] | [standalone]

#10993

On 9/25/2011 4:57 AM, Malcolm McLean wrote:
> On Sep 25, 1:52 pm, Uno<merrilljen...@q.com>  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

[toc] | [prev] | [next] | [standalone]

#11000

On Sep 27, 7:06 am, Uno <merrilljen...@q.com> wrote:
> On 9/25/2011 4:57 AM, Malcolm McLean wrote:
>
> > On Sep 25, 1:52 pm, Uno<merrilljen...@q.com>  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.

[toc] | [prev] | [next] | [standalone]

#11003

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

[toc] | [prev] | [next] | [standalone]

#11005

Malcolm McLean <malcolm.mclean5@btinternet.com> 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.

[toc] | [prev] | [next] | [standalone]

#11010

On Sep 27, 12:54 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> Malcolm McLean <malcolm.mcle...@btinternet.com> 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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web