[comp.lang.c] re-sizing a 2-dim array

brendan@cs.widener.edu (Brendan Kehoe) (05/17/91)

 I have a two-dimensional array, that I need to dynamically allocate
at run-time. It's declared as:
	LINE **contents;

 I need to be able to read in any arbitrarily large list (n lines) into
this array. I don't know how long the list is. (The example in the
FAQ, of allocating n rows, can't be used in this case, since I've no
idea how many rows could be in it to start with.)

 I was thinking of setting a limit of, say, 4096 or 8192 on it to
begin with (declare it as
	LINE **contents = (LINE **) malloc (sizeof(LINE *) * 4096);
for example). Then, when it read line 4097 (going outside the bounds
of the current set), it'd bump the whole thing up to 8192 (or some
increment), as so: 
	LINE **new_contents = (LINE **) malloc (sizeof(LINE *) * 8192);
and then do something like:

	bcopy((char *)contents, (char *)new_contents, sizeof(LINE *) * 4096);
	free(contents);
	contents = new_contents;

to move the old set of pointers over to the new one.

 Is this a reasonable way to do it? Is there a better way?

 Thanks..

Brendan

-- 
     Brendan Kehoe - Widener Sun Network Manager - brendan@cs.widener.edu
  Widener University in Chester, PA                A Bloody Sun-Dec War Zone
 "Visualize a dream; look for it in the present tense -- a greater calm than
   before.  If you persist in your efforts, you can achieve...dream control."

bls@u02.svl.cdc.com (Brian Scearce) (05/17/91)

In comp.lang.c brendan@cs.widener.edu (Brendan Kehoe) writes:
>	LINE **contents = (LINE **) malloc (sizeof(LINE *) * 4096);
>	LINE **new_contents = (LINE **) malloc (sizeof(LINE *) * 8192);
>	bcopy((char *)contents, (char *)new_contents, sizeof(LINE *) * 4096);
>	free(contents);
>	contents = new_contents;

Your idea is sound, so sound in fact that there's already something
in the standard library that basically does it.

  LINE **new_contents;

  if ( (new_contents = realloc(contents, sizeof(LINE *) * 0x2000)) == 0) {
    panic("Out of memory");
  } else {
    contents = new_contents;
  }

The advantages of this method:

1) realloc might find that there's space right after your allocated
   space, so it doesn't do anything except mark that space as
   unavailable.  Corollary: there might not be enough space for
   both malloc'd areas to exist at the same time -- possibly with
   realloc, they won't have to both exist at the same time.  Imagine
   your initial 4K block is followed by 5K of free space, but there
   is no more heap area.  Maybe realloc will be smart enough to
   satisfy the request for 8K, but malloc/bcopy/free will certainly
   fail.

2) One function call (realloc), instead of three (malloc, bcopy, free).

3) In most library implementations, realloc is self-starting: feeding
   it a NULL pointer for the first argument makes it equivalent to
   a call to malloc.  So here's a pretty common idiom:

#define INCREMENT 100
struct element *list = 0;
add(struct element x)
{
  static int listsize = 0;
  static int elements_in_list = 0;

  if (elements_in_list == listsize) {
    listsize += INCREMENT;
    if ( (list = realloc(list, listsize)) == 0) {
      panic("Out of memory");
      /* panic() doesn't return -- assume that out of mem is an
         abort condition, so it's OK to overwrite list with a possible
         NULL since we're giving up anyway. */
    }
  }
  list[elements_in_list++] = x;
}

Hope this helps.

--
     Brian Scearce (bls@robin.svl.cdc.com  -or-  robin!bls@shamash.cdc.com)
    "Don't be surprised when a crack in the ice appears under your feet..."
 Any opinions expressed herein do not necessarily reflect CDC corporate policy.