array.cpp

Go to the documentation of this file.

#ifndef ARRAY_IMPLEMENTATION
#define ARRAY_IMPLEMENTATION

/*****************************************************************************\
*                                                                             *
*  Name   : array                                                             *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1989-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

// GOALS:
//
// 1) provide a slightly smarter allocation method for C arrays and other
//    contiguous-storage container classes with better speed and reduced memory
//    fragmentation through pre-allocation.  this can reduce memory thrashing
//    when doing appends and inserts that can be granted with previously
//    allocated, but unused, space.
// 2) clean-up bounds failure cases in functions that return a reference by
//    always having at least one bogus element in the array for returns.  this
//    really just requires that we never allow our hidden real length of the
//    array to be zero.

//hmmm: with bogonic in use here, there is no error handling that
//      requires a blocking factor of 1, is there?  we can go to a zero
//      blocking factor.  or alternatively, we could toss the bogonic and
//      go back to a blocking of 1 by default.

#include "array.h"
#include "function.h"
#include "guards.h"

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

#undef static_class_name
#define static_class_name() "array"
  // used in debugging macros.

//#define DEBUG_ARRAY
  // uncomment for the debugging version.  this is much less efficient because
  // it performs random spot checks on the allocator's sanity.

template <class contents>
array<contents>::array(int num, const contents *init, u_short flags)
: _active_length(0), _real_length(0), _mem_block(NIL), _offset(NIL), _flags(flags)
{
  if (_flags > 7) {
#ifdef DEBUG_ARRAY
    const char *error_msg = "array constructor: error in parameters!  "
        "still passing a block size?  flags is set to %d.";
    printf(error_msg, flags);
    fprintf(stderr, error_msg, flags);
  #ifdef ERRORS_ARE_FATAL
      fflush(0);
      CAUSE_BREAKPOINT;
      throw "deadly_error";
  #endif // errors are fatal.
#endif // array debugging is turned on.

    _flags = EXPONE | FLUSH_INVISIBLE;
      // drop simple copy, since the caller doesn't know what they're doing.
  }

  allocator_reset(num, 1);  // get some space.
  retrain(num, init);  // plug in their contents.
}

template <class contents>
array<contents>::array(const array<contents> &cf)
: _active_length(0), _real_length(0), _mem_block(NIL), _offset(NIL), _flags(cf._flags)
{
  allocator_reset(cf._active_length, 1);  // get some space.
  operator = (cf);  // assignment operator does the rest.
}

template <class contents>
array<contents>::~array()
{
  _offset = NIL;
  if (_mem_block) delete [] _mem_block;
  _mem_block = NIL;
  _active_length = 0;
  _real_length = 0;
}

template <class contents>
void array<contents>::reset(int num, const contents *init)
{ retrain(num, init); }

template <class contents>
array<contents> &array<contents>::operator =(const array &cf)
{
  if (this == &cf) return *this;
  _flags = cf._flags;  // copy the flags coming in from the other object.
  // prepare the array for retraining...
  _offset = _mem_block;  // slide the offset back to the start.
  _active_length = 0;  // the length gets reset also.
  retrain(cf._active_length, cf.observe());
  return *this;
}

template <class contents>
contents &array<contents>::use(int index)
{
  FUNCDEF("use");
  bounds_halt(index, 0, this->last(), bogonic<contents>());
  return this->access()[index];
}

template <class contents>
const contents &array<contents>::get(int index) const
{
  FUNCDEF("get");
  bounds_halt(index, 0, this->last(), bogonic<contents>());
  return this->observe()[index];
}

template <class contents>
array<contents> &array<contents>::concatenate(const array &s1)
{
  // check whether there's anything to concatenate.
  if (!s1.length()) return *this;
  if (this == &s1) {
    // make sure they don't concatenate this array to itself.
    return concatenate(array<contents>(*this)); 
  }
  int old_len = this->length();
  resize(this->length() + s1.length(), common::NEW_AT_END);
  overwrite(old_len, s1);
  return *this;
}

template <class contents>
array<contents> &array<contents>::concatenate(const contents &to_concatenate)
{
  resize(this->length() + 1, common::NEW_AT_END);
  if (!this->simple())
    this->access()[this->last()] = to_concatenate;
  else
    memcpy(&(this->access()[this->last()]), &to_concatenate, sizeof(contents));
  return *this;
}

template <class contents>
array<contents> &array<contents>::concatenate(const contents *to_concatenate,
    int length)
{
  if (!length) return *this;  // nothing to do.
  const int old_len = this->length();
  resize(this->length() + length, common::NEW_AT_END);
  if (!this->simple())
    for (int i = 0; i < length; i++)
      this->access()[old_len + i] = to_concatenate[i];
  else
    memcpy(&(this->access()[old_len]), to_concatenate,
        length * sizeof(contents));
  return *this;
}

template <class contents>
array<contents> array<contents>::concatenation(const array &s1) const
{
  // tailor the return array to the new size needed.
  array<contents> to_return(this->length() + s1.length(), NIL, s1._flags);
  to_return.overwrite(0, *this);  // put the first part into the new array.
  to_return.overwrite(this->length(), s1);  // add the second segment.
  return to_return;
}

template <class contents>
array<contents> array<contents>::concatenation(const contents &s1) const
{
  array<contents> to_return(this->length() + 1, NIL, _flags);
  to_return.overwrite(0, *this);
  if (!this->simple())
    to_return.access()[to_return.last()] = s1;
  else
    memcpy(&(to_return.access()[to_return.last()]), &s1, sizeof(contents));
  return to_return;
}

template <class contents>
array<contents> array<contents>::subarray(int start, int end) const
{
  bounds_return(start, 0, this->last(), array<contents>(0, NIL, _flags));
  bounds_return(end, 0, this->last(), array<contents>(0, NIL, _flags));
  if (start > end) return array<contents>(0, NIL, _flags);
  return array<contents>(end - start + 1, &(this->observe()[start]), _flags);
}

template <class contents>
void array<contents>::swap_contents(array &other)
{
  if (this == &other) return;  // already swapped then, i suppose.
  swap_values(this->_active_length, other._active_length);
  swap_values(this->_real_length, other._real_length);
  swap_values(this->_offset, other._offset);
  swap_values(this->_mem_block, other._mem_block);
  swap_values(this->_flags, other._flags);
}

template <class contents>
outcome array<contents>::shrink()
{
  if (!_mem_block) return common::OUT_OF_MEMORY;
  if (_active_length == _real_length) return common::OKAY;  // already just right.
  array new_holder(*this);
    // create a copy of this object that is just the size needed.
  swap_contents(new_holder);
    // swap this object with the copy, leaving the enlarged version behind
    // for destruction.
  return common::OKAY;
}

template <class contents>
outcome array<contents>::stuff(int lengthx, contents *to_stuff) const
{
  if (!lengthx || !this->length()) return common::OKAY;
  int copy_len = minimum(lengthx, this->length());
  if (!this->simple()) {
    for (int i = 0; i < copy_len; i++)
      to_stuff[i] = this->observe()[i];
  } else {
    memcpy(to_stuff, this->observe(), copy_len * sizeof(contents));
  }
  return common::OKAY;
}

template <class contents>
outcome array<contents>::overwrite(int position,
    const array<contents> &write_with, int count)
{
  FUNCDEF("overwrite");
  if (!count) return common::OKAY;
  if ( (this == &write_with) || !this->length() || !write_with.length())
    return common::BAD_INPUT;
  bounds_halt(position, 0, this->last(), common::OUT_OF_RANGE);
  if ( negative(count) || (count > write_with.length()) )
    count = write_with.length();
  if (position > this->length() - count)
    count = this->length() - position;
  if (!this->simple()) {
    for (int i = position; i < position + count; i++)
      this->access()[i] = write_with.observe()[i - position];
  } else {
    memcpy(&(this->access()[position]), write_with.observe(), 
        count * sizeof(contents));
  }
  return common::OKAY;
}

template <class contents>
outcome array<contents>::allocator_reset(int initial, int blocking)
{
  FUNCDEF("reset");
  if (blocking < 1) {
#ifdef DEBUG_ARRAY
    continuable_error(static_class_name(), func, "bad block size");
#endif
    blocking = 1;
  }
  if (initial < 0) initial = 0;  // no antimatter arrays.
  if (_mem_block) {
    // remove old contents.
    delete [] _mem_block;
    _mem_block = NIL;
    _offset = NIL;
  }
  _active_length = initial;  // reset the length to the reporting size.
  _real_length = initial + blocking;  // compute the real length.
  if (_real_length) {
    try {
      _mem_block = new contents[_real_length];
      if (!_mem_block) {
        out_of_memory_now(static_class_name(), func);
        return common::OUT_OF_MEMORY;
      }
    } catch (...) {
      _mem_block = NIL;
      out_of_memory_now(static_class_name(), func);
      // shouldn't ever reach this spot.
      return common::OUT_OF_MEMORY;
    }
    _offset = _mem_block;  // reset offset to start of array.
  }
  return common::OKAY;
}

template <class contents>
void array<contents>::shift_data(shift_directions where)
{
  if (where == TO_LEFT) {
    // we want to end up with the data jammed up against the left edge.  thus
    // we need the offset to be zero bytes from start.
    if (_offset == _mem_block)
      return;  // offset already at start, we're done.
    // well, we need to move the data.
    if (simple()) {
      memmove(_mem_block, _offset, _active_length * sizeof(contents));
    } else {
      for (contents *ptr = _offset; ptr < _offset + _active_length; ptr++)
        _mem_block[ptr - _offset] = *ptr;
    }
    _offset = _mem_block;  // we've ensured that this is correct.
    if (_flags & FLUSH_INVISIBLE) {
      // we need to clean up what might have had contents previously.
//      for (contents *p = _mem_block + _active_length; p < _mem_block + _real_length; p++)
//        *p = contents();
    }
  } else {
    // we want to move the data to the right, so the offset should be the
    // difference between the real length and the length.
    if (_offset == _mem_block + _real_length - _active_length)
      return;  // the offset is already the right size.
    if (simple()) {
      memmove(&_mem_block[_real_length - _active_length], _offset, _active_length * sizeof(contents));
    } else {
      for (int i = _real_length - 1; i >= _real_length - _active_length; i--)
        _mem_block[i] = _offset[i - _real_length + _active_length];
    }
    _offset = _mem_block + _real_length - _active_length;  // we've now ensured this.
    if (_flags & FLUSH_INVISIBLE) {
      // we need to clean up the space on the left where old contents might be.
//      for (contents *p = _mem_block; p < _offset; p++)
//        *p = contents();
    }
  }
}

template <class contents>
outcome array<contents>::resize(int new_size, common::how_to_copy way)
{
  FUNCDEF("resize");
  if (new_size < 0) new_size = 0;  // we stifle this.
  if (new_size == _active_length) {
    // nothing much to do.
    return common::OKAY;
  }
  // okay, now we at least know that the sizes are different.  we save all the
  // old information about the array prior to this resizing.
  contents *old_s = _mem_block;  // save the old contents...
  const int old_len = _active_length;  // and length.
  contents *old_off = _offset;  // and offset.
  bool delete_old = false;  // if true, old memory is whacked once it's copied.

//hmmm: wasn't there a nice realization that we could bail out early in
//      the case where the size is already suffcient?  there seems to be
//      an extraneous copy case here.
//      also it would be nice to have better, more descriptive names for the
//      variables here since they are not lending themselves to understanding
//      the algorithm.

  // we check whether there's easily enough space in the array already.
  // if not, then we have some more decisions to make.
  if (_real_length - (old_off - old_s) < new_size) {
    // well, there's not enough space with the current space and offset.
    if (_real_length < new_size) {
      // there's really not enough space overall, no fooling.  we now will
      // create a new block.
      _mem_block = NIL;  // zero out the pointer so reset doesn't delete it.
      delete_old = true;
      int blocking = 1;
      if (exponential()) blocking = new_size + 1;
      outcome ret = allocator_reset(new_size, blocking);
      if (ret != common::OKAY) {
        // failure, but don't forget to whack the old glob.
#ifdef DEBUG_ARRAY
        deadly_error(static_class_name(), "resize", "reset failure");
#endif
        delete [] old_s;
        return ret;
      }
      // fall out to the copying phase, now that we have some fresh memory.
    } else {
      // there is enough space if we shift some things around.
      const int size_difference = new_size - _active_length;
        // we compute how much space has to be found in the array somewhere
        // to support the new larger size.
      if (way == common::DONT_COPY) {
        // simplest case; just reset the offset appropriately so the new_size
        // will fit.
        _offset = _mem_block;
        _active_length = new_size;
      } else if (way == common::NEW_AT_BEGINNING) {
        // if the new space is at the beginning, there are two cases.  either
        // the new size can be accomodated by the current position of the
        // data or the data must be shifted to the right.
        if (_offset - _mem_block < size_difference) {
          // we need to shift the data over to the right since the offset isn't
          // big enough for the size increase.
          shift_data(TO_RIGHT);  // resets the offset appropriately.
        }
        // now we know that the amount of space prior to the real data
        // is sufficient to hold what new space is needed.  we just need to
        // shift the offset back somewhat.
        _offset -= size_difference;
        _active_length = new_size;
      } else {
        // better only be three ways to do this; we're now assuming the new
        // space should be at the end (NEW_AT_END).
        // now that we're here, we know there will be enough space if we shift
        // the block to the left, but we DO NEED to do this.  if we didn't need
        // to shift the data, then we would find that:
        //     _real_length - old_off >= new_size
        // which is disallowed by the guardian conditional around this area.
        shift_data(TO_LEFT);  // resets the offset for us.
        _active_length = new_size;
      }
      // we have ensured that we had enough space and we have already shifted
      // the data around appropriately.  we no longer need to enter the next
      // block where we would copy data around if we had to.  it has become
      // primarily for cases where either we have to copy data because we
      // have new storage to fill or where we are shrinking the array.
      return common::OKAY;
    }
  }

  // the blob of code below is offset invariant.  by the time we reach here,
  // the array should be big enough and the offset should be okay.
  _active_length = new_size;  // set length to the new reporting size.
  if (way != common::DONT_COPY) {
    int where = 0;  // offset for storing into new array.
    bool do_copy = false;  // if true, then we need to move the data around.
    contents *loop_offset_old = old_off;  // offset into original object.
    // we should only have to copy the memory in one other case besides our
    // inhabiting new memory--when we are asked to resize with the new stuff
    // at the beginning of the array.  if the new space is at the end, we're
    // already looking proper, but if the new stuff is at the beginning, we
    // need to shift existing stuff downwards.
    if (way == common::NEW_AT_BEGINNING) {
      where = new_size - old_len;  // move up existing junk.
      if (where) do_copy = true;  // do copy, since it's not immobile.
      if (where < 0) {
        // array shrank; we need to do the loop differently for starting
        // from the beginning.  we skip to the point in the array that our
        // suffix needs to start at.
        loop_offset_old -= where;
        where = 0;  // reset where so we don't have negative offsets.
      }
    }
    const int size_now = minimum(old_len, _active_length);
    if (delete_old || do_copy) {
      contents *offset_in_new = _offset + where;
      contents *posn_in_old = loop_offset_old;
      if (simple()) {
        // memmove should take care of intersections.
        memmove(offset_in_new, posn_in_old, size_now * sizeof(contents));
      } else {
        // we need to do the copies using the object's assignment operator.
        if (new_size >= old_len) {
          for (int i = size_now - 1; i >= 0; i--)
            offset_in_new[i] = posn_in_old[i];
        } else {
          for (int i = 0; i < size_now; i++)
            offset_in_new[i] = posn_in_old[i];
        }
      }

      // we only want to flush the obscured elements when we aren't already
      // inhabiting new space.
      if ( (_flags & FLUSH_INVISIBLE) && !delete_old) {
        // clear out the space that just went out of scope.  we only do this
        // for the flushing mode and when we aren't starting from a fresh
        // pointer (i.e., delete_old isn't true).
        if (new_size < old_len) {
//          for (contents *p = posn_in_old; p < offset_in_new; p++)
//            *p = contents();
        }
      }
    }
  }
  if (delete_old) delete [] old_s;
  return common::OKAY;
}

template <class contents>
outcome array<contents>::retrain(int new_len, const contents *to_set)
{
  FUNCDEF("retrain");
  if (new_len < 0) new_len = 0;  // stifle that bad length.
#ifdef DEBUG_ARRAY
  if ( (_mem_block >= to_set) && (_mem_block < to_set + new_len) )
    deadly_error(static_class_name(), func, "ranges overlap in retrain!");
#endif
  outcome ret = resize(new_len, common::DONT_COPY);
  if (ret != common::OKAY) return ret;
#ifdef DEBUG_ARRAY
  if (new_len != _active_length)
    continuable_error(static_class_name(), func, "resize set the wrong length");
#endif
  if (to_set) {
    if (simple()) 
      memcpy(_offset, to_set, _active_length * sizeof(contents));
    else
      for (int i = 0; i < _active_length; i++)
        _offset[i] = to_set[i];
  } else {
    if (_flags & FLUSH_INVISIBLE) {
      // no contents provided, so stuff the space with blanks.
//      for (int i = 0; i < _active_length; i++) _offset[i] = contents();
    }
  }
  if (_flags & FLUSH_INVISIBLE) {
//    for (contents *ptr = _mem_block; ptr < _offset; ptr++)
//      *ptr = contents();
//    for (contents *ptr = _offset + _active_length; ptr < _mem_block + _real_length; ptr++)
//      *ptr = contents();
  }
  return common::OKAY;
}

template <class contents>
outcome array<contents>::zap(int position1, int position2)
{
  if (position1 > position2) return common::OKAY;
  bounds_return(position1, 0, _active_length - 1, common::OUT_OF_RANGE);
  bounds_return(position2, 0, _active_length - 1, common::OUT_OF_RANGE);
  if (!position1) {
    // if they're whacking from the beginning, we just reset the offset.
    _offset += position2 + 1;
    _active_length -= position2 + 1;
    return common::OKAY;
  }
  const int difference = position2 - position1 + 1;
  // copy from just above position2 down into position1.
  if (simple()) {
    if (_active_length - difference - position1 > 0)
      memmove(&_offset[position1], &_offset[position1 + difference],
          (_active_length - difference - position1) * sizeof(contents));
  } else {
    for (int i = position1; i < _active_length - difference; i++)
      _offset[i] = _offset[i + difference];
  }

  outcome ret = resize(_active_length - difference, common::NEW_AT_END);
    // chop down to new size.
#ifdef DEBUG_ARRAY
  if (ret != common::OKAY) {
    deadly_error(static_class_name(), "zap", "resize failure");
    return ret;
  }
#endif
  return ret;
}

template <class contents>
outcome array<contents>::insert(int position, int elem_to_add)
{
  if (position < 0) return common::OUT_OF_RANGE;
  if (position > this->length())
    position = this->length();
  if (elem_to_add < 0) return common::OUT_OF_RANGE;
  common::how_to_copy how = common::NEW_AT_END;
  if (position == 0) how = common::NEW_AT_BEGINNING;
  resize(this->length() + elem_to_add, how);

  // if the insert wasn't at the front, we have to copy stuff into the new
  // locations.
  if (how == common::NEW_AT_END) {
    const contents simple_default_object = contents();
    if (!this->simple()) {
      for (int i = this->last(); i >= position + elem_to_add; i--)
        this->access()[i] = this->observe()[i - elem_to_add];
      for (int j = position; j < position + elem_to_add; j++)
        this->access()[j] = simple_default_object;
    } else {
      memmove(&(this->access()[position + elem_to_add]),
          &(this->observe()[position]), (this->length() - position
          - elem_to_add) * sizeof(contents));
      for (int j = position; j < position + elem_to_add; j++)
        memcpy(&this->access()[j], &simple_default_object, sizeof(contents));
    }
  }
  return common::OKAY;
}

template <class contents>
outcome array<contents>::put(int index, const contents &to_put)
{
  FUNCDEF("put");
  bounds_halt(index, 0, this->last(), common::OUT_OF_RANGE);
  if (!this->simple())
    this->access()[index] = to_put;
  else
    memcpy(&(this->access()[index]), &to_put, sizeof(contents));
  return common::OKAY;
}

template <class contents>
void array<contents>::snarf(array<contents> &new_contents)
{
  if (this == &new_contents) return;  // no blasting own feet off.
  reset();  // trash our current storage.
  swap_contents(new_contents);
}

#undef static_class_name

#endif

---