Test equipment for the 64-bit arithmetic in `bits.h'.

[mLib] / darray.c

/* -*-c-*-
 *
 * $Id: darray.c,v 1.5 2000/06/17 10:37:39 mdw Exp $
 *
 * Dynamically growing dense arrays
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of the mLib utilities library.
 *
 * mLib is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * mLib is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with mLib; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: darray.c,v $
 * Revision 1.5  2000/06/17 10:37:39  mdw
 * Add support for arena management.
 *
 * Revision 1.4  1999/11/06 12:40:45  mdw
 * Minor changes to allocation strategy.
 *
 * Revision 1.3  1999/10/29 22:59:22  mdw
 * New array adjustment macros for unsigned arguments.
 *
 * Revision 1.2  1999/10/28 22:05:28  mdw
 * Modify and debug allocation routines.
 *
 * Revision 1.1  1999/10/22 22:37:26  mdw
 * New dynamic array implementation replaces `dynarray.h'.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "alloc.h"
#include "arena.h"
#include "darray.h"

/*----- Magic numbers -----------------------------------------------------*/

#define DA_INITSZ 16			/* Default size for new array */
#define DA_SLOTS 8			/* Number of preshifted slots */

/*----- Main code ---------------------------------------------------------*/

/* --- @da_ensure@ --- *
 *
 * Arguments:	@da_base *b@ = pointer to array base structure
 *		@void *v@ = pointer to array vector
 *		@size_t sz@ = size of individual array elements
 *		@size_t n@ = number of items required at the end
 *
 * Returns:	Pointer to newly allocated or adjusted array vector.
 *
 * Use:		Extends a dynamic array to accommodate a number of new items
 *		at its end.  This function is a helper for the @DA_ENSURE@
 *		macro, which should be used by preference.
 */

void *da_ensure(da_base *b, void *v, size_t sz, size_t n)
{
  size_t rq = n + b->len;
  char *p = v, *q;
  size_t nsz;
  size_t slots;

  /* --- Make sure there's something which needs doing --- *
   *
   * If there's enough space already then return immediately.
   */

  if (rq < b->sz)
    return (p);

  /* --- Compute a number of `unshift' slots --- *
   *
   * When returning from this function, the offset will be set to @slots@.
   * If @unshift@ is zero, there's no point in reserving slots.  Otherwise
   * choose a power of two greater than @unshift@, with a minimum of
   * @DA_SLOTS@.  Then add the number of slots to the requirement.
   */

  if (!b->unshift)
    slots = 0;
  else {
    slots = DA_SLOTS;
    while (slots < b->unshift)
      slots <<= 1;
  }
  rq += slots;

  /* --- Maybe just shunt data around a bit --- *
   *
   * If the vector is large enough, then theoretically we could cope by
   * moving the objects about in their existing storage.  It's not worth
   * bothering if there's not actually double the amount of space I need.
   */

  if (rq * 2 < b->sz + b->off) {
    q = p - (b->off - slots) * sz;
    memmove(q, p, b->len * sz);
    b->sz += b->off - slots;
    b->off = slots;
    b->unshift = b->push = 0;
    return (q);
  }

  /* --- Decide on a new size --- *
   *
   * There's a minimum possible size for the array which is used if it's
   * currently completely empty.  Otherwise I choose the smallest power of
   * two which is big enough, starting at double the current size.
   */

  nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
  do nsz <<= 1; while (nsz < rq);

  /* --- Reallocate the block --- *
   *
   * If I'm not changing the base offset then it's worth using @realloc@;
   * otherwise there'll probably be two calls to @memcpy@ to shunt the data
   * around so it's not worth bothering.
   */

  if (p && slots == b->off) {
    q = x_realloc(b->a, p - b->off * sz, nsz * sz);
    q += slots * sz;
  } else {
    q = x_alloc(b->a, nsz * sz);
    q += slots * sz;
    if (p) {
      memcpy(q, p, b->len * sz);
      x_free(b->a, p - b->off * sz);
    }
  }

  /* --- Fill in the other parts of the base structure --- */

  b->off = slots;
  b->sz = nsz - slots;
  b->unshift = b->push = 0;
  return (q);
}

/* --- @da_shunt@ --- *
 *
 * Arguments:	@da_base *b@ = pointer to array base structure
 *		@void *v@ = pointer to array vector
 *		@size_t sz@ = size of the array elements
 *		@size_t n@ = number of items required at the start
 *
 * Returns:	Pointer to appropriately bodged vector.
 *
 * Use:		Extends an array to accommodate items inserted at its front.
 *		This function is a helper for the @DA_SHUNT@ macro, which
 *		should be used by preference.
 */

void *da_shunt(da_base *b, void *v, size_t sz, size_t n)
{
  size_t rq;
  char *p = v, *q;
  size_t nsz;
  size_t slots;

  /* --- Make sure there's something which needs doing --- *
   *
   * If there's enough space already then return immediately.
   */

  if (n < b->off)
    return (p);

  /* --- Compute a number of `push' slots --- *
   *
   * When returning from this function, there will be @slots@ free spaces at
   * the end of the array.  If @push@ is zero, there's no point in reserving
   * slots.  Otherwise choose a power of two greater than @push@, with a
   * minimum of @DA_SLOTS@.  To simplify matters, add the number of items
   * already in the array to @slots@, and then add the number of slots to the
   * requirement.
   */

  if (!b->push)
    slots = 0;
  else {
    slots = DA_SLOTS;
    while (slots < b->push)
      slots <<= 1;
  }
  slots += b->len;
  rq = n + slots;

  /* --- Maybe just shunt data around a bit --- *
   *
   * If the vector is large enough, then theoretically we could cope by
   * moving the objects about in their existing storage.  Again, if there's
   * not actually twice the space needed, reallocate the array.
   */

  if (rq * 2 < b->sz + b->off) {
    q = p + (b->sz - slots) * sz;
    memmove(q, p, b->len * sz);
    b->off += b->sz - slots;
    b->sz = slots;
    b->unshift = b->push = 0;
    return (q);
  }

  /* --- Reallocate the array --- *
   *
   * The neat @realloc@ code doesn't need to be here: the offset changes
   * almost all the time -- that's the whole point of this routine!
   */

  /* --- Decide on a new size --- *
   *
   * There's a minimum possible size for the array which is used if it's
   * currently completely empty.  Otherwise I choose the smallest power of
   * two which is big enough, starting at double the current size.
   */

  nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
  do nsz <<= 1; while (nsz < rq);

  /* --- Reallocate the block --- *
   *
   * The neat @realloc@ code doesn't need to be here: the offset changes
   * almost all the time -- that's the whole point of this routine!
   */

  q = x_alloc(b->a, nsz * sz);
  q += (nsz - slots) * sz;
  if (p) {
    memcpy(q, p, b->len * sz);
    x_free(b->a, p - b->off * sz);
  }

  /* --- Fill in the other parts of the base structure --- */
  
  b->off = nsz - slots;
  b->sz = slots;
  b->unshift = b->push = 0;
  return (q);
}

/* --- @da_tidy@ --- *
 *
 * Arguments:	@da_base *b@ = pointer to array base structure
 *		@void *v@ = pointer to vector
 *		@size_t sz@ = size of the array elements
 *
 * Returns:	Newly allocated vector.
 *
 * Use:		Minimizes the space occupied by an array.  This function is a
 *		helper for the @DA_TIDY@ macro, which should be used by
 *		preference.
 */

void *da_tidy(da_base *b, void *v, size_t sz)
{
  char *p = v, *q;

  b->unshift = b->push = 0;

  if (!p)
    return (0);
  if (b->sz == b->len && b->off == 0)
    return (p);

  if (!b->len) {
    xfree(p - b->off * sz);
    return (0);
  }

  q = x_alloc(b->a, b->len * sz);
  memcpy(q, p, b->len * sz);
  x_free(b->a, p - b->off * sz);
  b->sz = b->len;
  b->off = 0;
  return (q);
}

/* --- Note about testing --- *
 *
 * The test rig for this code is split into three parts.  There's `da-gtest',
 * which is a Perl script which generates a list of commands.  The `da-ref'
 * Perl script interprets these commands as operations on a Perl array.  It's
 * relatively conservatively written and believed to be reliable.  The
 * `da-test.c' file implements a command reader for the same syntax and
 * performs the operations on an integer darray, producing output in the same
 * format.  To test darray, generate a command script with `da-gtest', pass
 * it through both `da-ref' and `da-test' (the result of compiling
 * da-test.c'), and compare the results.  If they're not byte-for-byte
 * identical, there's something wrong.
 */

/*----- That's all, folks -------------------------------------------------*/