Stretchy arrays (Re: Efficient coding considered harmful?)

[Dave Jones]

>From article <1709 at garth.UUCP>, by smryan at garth.UUCP (Steven Ryan):
...[I missed the article to which Mr. Ryan is responding.]

>> Well, gee, how do you allocate an indefinite sized array?
> 
> Glad you asked. I stuff it down a stack, each element individually
> handcrafted with malloc, until I've reached the end and know exactly
> how big it is. Then, IF I need random access, I copy it to an array.
> Linear time.


A method I have used quite successfully for some time now is
to use realloc to increase the size of a buffer by some *percentage*
of its current size.  How big a percentage depends on how
much memory you can afford to be "wasted".  Usually doubling the
size of the array works just fine.

The array will occasionally be twice as big as it need be. But
the overhead is not as much as it might seem at first.  Notice that in
the stacking scheme described above, there is an overhead for
links and heap-structure headers.  On the machine I mostly use (Sun-3),
that would increase memory usage for character arrays by a factor of
ten!  And with that particular libc.a, malloc overhead can be devastating 
in the speed column. (I would not use malloc "raw" for linked lists, but
that's another issue.)

The algorithm is linear in time and space.

Here's a sample of an example. (I'm a poet, and didn't know it.)

>From my personal library...


/* Vbuf.h */
#ifndef _VBUF_H_

typedef
struct Vbuf
{
  /* Public */
  unsigned char* buf; /* current buffer. Read-only. */
  int dot;   /* byte-displacement of next byte 
             ** to be put or bss'd. Read-write.
             */

  /* private */
  int bufsize; /* size, in bytes, of current buffer */
} Vbuf;

Vbuf* Vbuf_init(/* Vbuf* */);
void  Vbuf_clean(/* Vbuf* */);

/* These return the old dot. */
int   Vbuf_put_uchar(/* Vbuf*, unsigned  */);
int   Vbuf_put_ushort(/* Vbuf*, unsigned */);
int   Vbuf_put_ulong(/* Vbuf*, unsigned */);
int   Vbuf_put_block( /* Vbuf*, unsigned char*, int */)
int   Vbuf_bss_uchar(/* Vbuf* */);
int   Vbuf_bss_ushort(/* Vbuf* */);
int   Vbuf_bss_ulong(/* Vbuf* */);
int   Vbuf_bss(/* Vbuf*, int */);

/* These return the new dot */
int   Vbuf_align_short(/* Vbuf*/);
int   Vbuf_align_long(/* Vbuf */);

/* Returns value from system-call write() */
int   Vbuf_write(/* Vbuf*, int */);   /* int is file-descriptor */

#define _VBUF_H_
#endif  _VBUF_H_



You can probably guess what the code has to look like. Here's
a fragment...


#include "Vbuf.h"
#define INITIAL_SIZE 16

static void expand();

Vbuf_put_uchar(obj, val)
  register Vbuf* obj;
  unsigned val;
{
  while(obj->dot >= obj->bufsize) expand(obj);
  *(obj->buf + (obj->dot)++) = (unsigned char) val;
  return obj->dot - 1;
}


static void
expand(obj)
  register Vbuf* obj;
{
  if(obj->bufsize == 0 )
    { /* first allocation */
      obj->buf = (unsigned char*)smalloc(INITIAL_SIZE);
      obj->bufsize = INITIAL_SIZE;
    }
  else
    {
      obj->bufsize *= 2;
      obj->buf = (unsigned char*)realloc(obj->buf, obj->bufsize);
    }
}