4 /*****************************************************************************\
7 * Author : Chris Koeritz *
9 *******************************************************************************
10 * Copyright (c) 1989-$now By Author. This program is free software; you can *
11 * redistribute it and/or modify it under the terms of the GNU General Public *
12 * License as published by the Free Software Foundation; either version 2 of *
13 * the License or (at your option) any later version. This is online at: *
14 * http://www.fsf.org/copyleft/gpl.html *
15 * Please send any updates to: fred@gruntose.com *
16 \*****************************************************************************/
18 #include "common_outcomes.h"
19 #include "definitions.h"
20 #include "enhance_cpp.h"
21 #include "functions.h"
26 // uncomment for the noisier debugging version.
30 //! Represents a sequential, ordered, contiguous collection of objects.
32 This object manages a contiguous array of memory to hold the objects it
33 contains. The objects to be stored must have a constructor with zero
34 parameters, since the objects are stored in a C-style array (and array
35 constructors cannot be given arguments to be passed to the objects).
36 The objects must also either be flat (containing no pointers) or have an
37 assignment operator (=) that correctly copies the deep contents.
38 This class also provides an exponential growth mode for memory to reduce
39 thrashing; this allows the size pre-allocated to double every time a new
40 allocation is required during a resize. This causes the allocation to grow
41 very swiftly, speeding up usage of frequently growing arrays, but this may
42 not be desired for every array.
44 blank array: a array with some number of elements, but where those
45 elements are objects that have been constructed using their default
46 parameterless constructor.
47 empty array: a array of zero elements.
50 template <class contents>
51 class array : public virtual root_object
54 //! the flags specify how the array treats its contents and its length.
56 NO_SPECIAL_MODES = 0x0, //!< do nothing extra; only valid by itself.
57 SIMPLE_COPY = 0x1, //!< the contents can be memcpy'd and are not deep.
58 EXPONENTIAL_GROWTH = 0x2, //!< length is doubled when reallocation happens.
59 EXPONE = EXPONENTIAL_GROWTH, //!< synonym for EXPONENTIAL_GROWTH.
60 FLUSH_INVISIBLE = 0x4 //!< blanks out allocated but inaccessible elements.
63 DEFINE_CLASS_NAME("array");
65 enum how_to_copy { NEW_AT_END, NEW_AT_BEGINNING, DONT_COPY };
66 //!< An enumeration of ways to shift existing contents in an array.
67 /*!< In the context of dynamically resizing an array of data, a range of
68 new elements can be added (or removed for that matter) at the end of the
69 existing space (NEW_AT_END), at the beginning of the existing space
70 (NEW_AT_BEGINNING), or we might not care about the existing data when
71 we perform the resize (DONT_COPY). These methods impose a particular
72 shift on the existing contents if we actually already have enough space
73 for the new contents. If there is space before the part of the array
74 that's in use and we want NEW_AT_END, then the existing contents are
75 jammed up into the front end of the array. */
77 array(int number = 0, const contents *init = NIL,
78 int flags = EXPONENTIAL_GROWTH | FLUSH_INVISIBLE);
79 //!< Constructs an array with room for "number" objects.
80 /*!< The initial contents are copied from "init" unless NIL is passed in
81 instead. If "init" is not NIL, then it must point to an array of objects
82 that contains at least "number". The "flags" are a value based on the
83 special flags being added bit-wise. If "flags" contains SIMPLE_COPY, then
84 memmove() is used rather than using the C++ object's assignment operator.
85 Note that SIMPLE_COPY will NOT work if the templated object has a regular
86 constructor or assignment operator, since those methods will not be
87 called on copying. If the "flags" contain EXPONENTIAL_GROWTH, then the
88 true allocation size will be doubled every time a new allocation is
89 required. when the FLUSH_INVISIBLE flag is included, then the array
90 elements that go out of scope are returned to the state provided by
91 the content's default constructor. this ensures that if they ever come
92 back into scope, they do not yet have any contents. further, if the
93 elements had any deep contents, those resources should be released. */
95 array(const array<contents> ©_from);
96 //!< copies the contents & sizing information from "copy_from".
98 virtual ~array(); //!< destroys the memory allocated for the objects.
100 void reset(int number = 0, const contents *initial_contents = NIL);
101 //!< Resizes this array and sets the contents from an array of contents.
102 /*< If "initial_contents" is not NIL, then it must contain an array of
103 "contents" with at least "number" objects in it. If it is NIL, then
104 the size of the array is changed but the contents are not. note that
105 any pre-existing elements that were previously out of range might still
106 have their prior contents; the newly available elements are not necessarily
107 "blank". thus, before using them, ensure you store appropriate elements
108 in those positions. */
110 array &operator = (const array<contents> ©_from);
111 //!< Copies the array in "copy_from" into this.
113 int length() const { return c_active_length; }
114 //!< Returns the current reported length of the allocated C array.
116 int last() const { return c_active_length - 1; }
117 //!< Returns the last valid element in the array.
119 int flags() const { return c_flags; }
120 //!< Provides the raw flags value, without interpreting what it means.
122 bool exponential() const { return c_flags & EXPONENTIAL_GROWTH; }
123 //!< Returns true if this allocator will grow exponentially on resize.
125 bool simple() const { return c_flags & SIMPLE_COPY; }
126 //!< Reports whether the templated object is a simple type or not.
128 const contents &get(int index) const;
129 //!< Accesses individual objects stored in "this" at the "index" position.
130 /*!< If the index is out of range, then a bogus reference (to internally
131 held garbage) is returned. */
132 contents &use(int index);
133 //!< A non-constant version of get(); the returned object can be modified.
135 const contents &operator [] (int index) const { return get(index); }
136 //!< Synonym for get that provides the expected array indexing syntax.
137 contents &operator [] (int index) { return use(index); }
138 //!< Synonym for use that provides the expected array indexing syntax.
140 outcome put(int index, const contents &to_put);
141 //!< Stores an object at the index "index" in the array.
142 /*!< The outcome is "OUT_OF_RANGE" if the index does not exist. */
144 array concatenation(const array &to_concatenate) const;
145 //!< Returns the concatenation of "this" and the array "to_concatenate".
146 array concatenation(const contents &to_concatenate) const;
147 //!< Returns the concatenation of "this" and the object "to_concatenate".
149 array &concatenate(const array &to_concatenate);
150 //!< Appends the array "to_concatenate" onto "this" and returns "this".
151 array &concatenate(const contents &to_concatenate);
152 //!< Appends the object "to_concatenate" onto "this" and returns "this".
153 array &concatenate(const contents *to_concatenate, int length);
154 //!< Concatenates a C-array "to_concatenate" onto "this" and returns "this".
155 /*!< There must be at least "length" elements in "to_concatenate". */
157 array operator + (const array &to_cat) const
158 { return concatenation(to_cat); }
159 //!< Synonym for concatenation.
160 array operator + (const contents &to_concatenate) const
161 { return concatenation(to_concatenate); }
162 //!< Synonym for concatenation.
163 array &operator += (const array &to_concatenate)
164 { return concatenate(to_concatenate); }
165 //!< Synonym for concatenate that modifies "this".
166 array &operator += (const contents &to_concatenate)
167 { return concatenate(to_concatenate); }
168 //!< Synonym for concatenate that modifies "this".
170 const contents *observe() const { return c_offset; }
171 //!< Returns a pointer to the underlying C array of data.
172 /*!< The array contains "length()" number of objects in it. BE CAREFUL.
173 This version is a constant peek at that pointer. */
174 contents *access() { return c_offset; }
175 //!< A non-constant access of the underlying C-array. BE REALLY CAREFUL.
177 void swap_contents(array<contents> &other);
178 //!< Exchanges the contents of "this" and "other".
179 /*!< No validation is performed but this should always succeed given
180 arrays constructed properly. */
182 void snarf(array &new_contents);
183 //!< Drops "this" array's contents into the dustbin and uses "new_contents".
184 /*!< Afterwards, "new_contents" is an empty array and what used to be
185 stored there is now in "this" instead. */
187 array subarray(int start, int end) const;
188 //!< Returns the array segment between the indices "start" and "end".
189 /*!< This is all characters from "start" to "end" inclusively, as long as
190 those values are valid for this array. Even then, an intelligent default
191 is usually assumed if the indices are out of range. */
193 outcome insert(int index, int new_indices);
194 //!< Adds "new_indices" new positions for objects into the array at "index".
196 outcome overwrite(int index, const array &write_with, int count = -1);
197 //!< Stores the array "write_with" into the current array at the "index".
198 /*!< The current contents are overwritten with "write_with". If the
199 index is invalid, then OUT_OF_RANGE is returned. If the "write_with"
200 array cannot fit due to the boundaries of "this" array, then only the
201 portion that can fit is used. If "count" is negative, the whole
202 "write_with" array is used; otherwise, only "count" elements are used. */
204 outcome stuff(int length, contents *to_stuff) const;
205 //!< Copies at most "length" elements from this into the array "to_stuff".
206 /*!< This call will fail disastrously if "length" is larger than the
207 array "to_stuff"'s allocated length. */
209 outcome resize(int new_size, how_to_copy way = NEW_AT_END);
210 //!< Changes the size of the C array to "new_size".
211 /*!< If "way" is NEW_AT_END and the array grows, then new space is added
212 at the end and the prefix of the array is the same as the old array. If
213 the "way" is NEW_AT_END, but the array shrinks, then the new array is a
214 prefix of the old array. If "way" is NEW_AT_BEGINNING and the array
215 grows, then the suffix of the array is the same as the old one and the
216 space is added at the beginning. if the "way" is NEW_AT_BEGINNING but the
217 array shrinks, then the new array is a suffix of the old array. if "way"
218 is DONT_COPY, then the old contents are not copied. keep in mind that
219 any newly visible elements can be in an arbitrary state and will not
220 necessarily be freshly constructed. */
222 outcome zap(int start, int end);
223 //!< Deletes from "this" the objects inclusively between "start" and "end".
224 /*!< C-array conventions are used (0 through length()-1 are valid if
225 length() > 0). If either index is out of range, then a default is
229 //!< Cuts loose any allocated space that is beyond the real length.
231 outcome retrain(int new_size, const contents *to_copy);
232 //!< Resizes the C array and stuffs it with the contents in "to_copy".
234 enum shift_directions { TO_LEFT, TO_RIGHT };
235 //!< All the real contents can be shifted to either the left or right.
237 void shift_data(shift_directions where);
238 //!< The valid portion of the array is moved to the left or right.
239 /*!< This means that the unused space (dictated by the offset where the
240 data starts) will be adjusted. This may involve copying the data. */
242 // These are gritty internal information methods and should not be used
243 // except by appropriately careful code.
244 int internal_real_length() const { return c_real_length; }
245 //!< Gritty Internal: the real allocated length.
246 int internal_offset() const { return int(c_offset - c_mem_block); }
247 //!< Gritty Internal: the offset from real start to stored data.
248 const contents *internal_block_start() const { return c_mem_block; }
249 //!< Gritty Internal: constant peek at the real allocated pointer.
250 contents *internal_block_start() { return c_mem_block; }
251 //!< Gritty Internal: the real allocated pointer made accessible.
252 contents * const *internal_offset_mem() const { return &c_offset; }
253 //!< Gritty Internal: the start of the actual stored data.
256 int c_active_length; //!< the number of objects reported to be in the array.
257 int c_real_length; // the real number of objects that can be stored.
258 contents *c_mem_block; //!< a pointer to the objects held for this array.
259 contents *c_offset; //!< the beginning of the useful part of the memory block.
260 int c_flags; //!< records the special characteristics of this array.
262 outcome allocator_reset(int initial_elements, int blocking);
263 //!< Allocates space for the "initial_elements" plus the "blocking" factor.
264 /*!< This resets the C-array to have "initial_elements" indices, plus an
265 extra pre-allocation of "blocking" that leaves room for expansion. Any
266 prior contents are whacked. */
271 //! A simple object that wraps a templated array of ints.
272 class int_array : public array<int>
275 int_array(int number = 0, const int *initial_contents = 0)
277 array<int>(number, initial_contents, SIMPLE_COPY | EXPONE) {}
278 //!< Constructs an array of "number" integers.
279 /*!< creates a list of ints based on an initial "number" of entries and
280 some "initial_contents", which should be a regular C array of ints
281 with at least as many entries as "number". */
286 //! An array of double floating point numbers.
287 class double_array : public array<double>
290 double_array(int len = 0, double *data = NIL)
292 array<double>(len, data, SIMPLE_COPY | EXPONE) {}
293 double_array(const array<double> &to_copy) : array<double>(to_copy) {}
298 // implementation code, much longer methods below...
302 // 1) provide a slightly smarter allocation method for C arrays and other
303 // contiguous-storage container classes with better speed and reduced memory
304 // fragmentation through pre-allocation. this can reduce memory thrashing
305 // when doing appends and inserts that can be granted with previously
306 // allocated, but unused, space.
307 // 2) clean-up bounds failure cases in functions that return a reference by
308 // always having at least one bogus element in the array for returns. this
309 // really just requires that we never allow our hidden real length of the
312 template <class contents>
313 array<contents>::array(int num, const contents *init, int flags)
314 : root_object(), c_active_length(0), c_real_length(0), c_mem_block(NIL), c_offset(NIL), c_flags(flags)
318 throw "error: array::constructor: error in parameters! still passing a block size?";
320 c_flags = EXPONE | FLUSH_INVISIBLE;
321 // drop simple copy, since the caller doesn't know what they're doing.
324 allocator_reset(num, 1); // get some space.
325 retrain(num, init); // plug in their contents.
328 template <class contents>
329 array<contents>::array(const array<contents> &cf)
330 : root_object(), c_active_length(0), c_real_length(0), c_mem_block(NIL), c_offset(NIL), c_flags(cf.c_flags)
332 allocator_reset(cf.c_active_length, 1); // get some space.
333 operator = (cf); // assignment operator does the rest.
336 template <class contents>
337 array<contents>::~array()
340 if (c_mem_block) delete [] c_mem_block;
346 template <class contents>
347 void array<contents>::reset(int num, const contents *init)
348 { retrain(num, init); }
350 template <class contents>
351 array<contents> &array<contents>::operator =(const array &cf)
353 if (this == &cf) return *this;
354 c_flags = cf.c_flags; // copy the flags coming in from the other object.
355 // prepare the array for retraining...
356 c_offset = c_mem_block; // slide the offset back to the start.
357 c_active_length = 0; // the length gets reset also.
358 retrain(cf.c_active_length, cf.observe());
362 template <class contents>
363 contents &array<contents>::use(int index)
365 bounds_return(index, 0, this->last(), bogonic<contents>());
366 return this->access()[index];
369 template <class contents>
370 const contents &array<contents>::get(int index) const
372 bounds_return(index, 0, this->last(), bogonic<contents>());
373 return this->observe()[index];
376 template <class contents>
377 array<contents> &array<contents>::concatenate(const array &s1)
379 // check whether there's anything to concatenate.
380 if (!s1.length()) return *this;
382 // make sure they don't concatenate this array to itself.
383 return concatenate(array<contents>(*this));
385 int old_len = this->length();
386 resize(this->length() + s1.length(), NEW_AT_END);
387 overwrite(old_len, s1);
391 template <class contents>
392 array<contents> &array<contents>::concatenate(const contents &to_concatenate)
394 resize(this->length() + 1, NEW_AT_END);
396 this->access()[this->last()] = to_concatenate;
398 memcpy(&(this->access()[this->last()]), &to_concatenate, sizeof(contents));
402 template <class contents>
403 array<contents> &array<contents>::concatenate(const contents *to_concatenate,
406 if (!length) return *this; // nothing to do.
407 const int old_len = this->length();
408 resize(this->length() + length, NEW_AT_END);
410 for (int i = 0; i < length; i++)
411 this->access()[old_len + i] = to_concatenate[i];
413 memcpy(&(this->access()[old_len]), to_concatenate,
414 length * sizeof(contents));
418 template <class contents>
419 array<contents> array<contents>::concatenation(const array &s1) const
421 // tailor the return array to the new size needed.
422 array<contents> to_return(this->length() + s1.length(), NIL, s1.c_flags);
423 to_return.overwrite(0, *this); // put the first part into the new array.
424 to_return.overwrite(this->length(), s1); // add the second segment.
428 template <class contents>
429 array<contents> array<contents>::concatenation(const contents &s1) const
431 array<contents> to_return(this->length() + 1, NIL, c_flags);
432 to_return.overwrite(0, *this);
434 to_return.access()[to_return.last()] = s1;
436 memcpy(&(to_return.access()[to_return.last()]), &s1, sizeof(contents));
440 template <class contents>
441 array<contents> array<contents>::subarray(int start, int end) const
443 bounds_return(start, 0, this->last(), array<contents>(0, NIL, c_flags));
444 bounds_return(end, 0, this->last(), array<contents>(0, NIL, c_flags));
445 if (start > end) return array<contents>(0, NIL, c_flags);
446 return array<contents>(end - start + 1, &(this->observe()[start]), c_flags);
449 template <class contents>
450 void array<contents>::swap_contents(array &other)
452 if (this == &other) return; // already swapped then, i suppose.
453 swap_values(this->c_active_length, other.c_active_length);
454 swap_values(this->c_real_length, other.c_real_length);
455 swap_values(this->c_offset, other.c_offset);
456 swap_values(this->c_mem_block, other.c_mem_block);
457 swap_values(this->c_flags, other.c_flags);
460 template <class contents>
461 outcome array<contents>::shrink()
463 if (!c_mem_block) return common::OUT_OF_MEMORY;
464 if (c_active_length == c_real_length) return common::OKAY; // already just right.
465 array new_holder(*this);
466 // create a copy of this object that is just the size needed.
467 swap_contents(new_holder);
468 // swap this object with the copy, leaving the enlarged version behind
473 template <class contents>
474 outcome array<contents>::stuff(int lengthx, contents *to_stuff) const
476 if (!lengthx || !this->length()) return common::OKAY;
477 int copy_len = minimum(lengthx, this->length());
478 if (!this->simple()) {
479 for (int i = 0; i < copy_len; i++)
480 to_stuff[i] = this->observe()[i];
482 memcpy(to_stuff, this->observe(), copy_len * sizeof(contents));
487 template <class contents>
488 outcome array<contents>::overwrite(int position,
489 const array<contents> &write_with, int count)
491 if (!count) return common::OKAY;
492 if ( (this == &write_with) || !this->length() || !write_with.length())
493 return common::BAD_INPUT;
494 bounds_return(position, 0, this->last(), common::OUT_OF_RANGE);
495 if ( negative(count) || (count > write_with.length()) )
496 count = write_with.length();
497 if (position > this->length() - count)
498 count = this->length() - position;
499 if (!this->simple()) {
500 for (int i = position; i < position + count; i++)
501 this->access()[i] = write_with.observe()[i - position];
503 memcpy(&(this->access()[position]), write_with.observe(),
504 count * sizeof(contents));
509 template <class contents>
510 outcome array<contents>::allocator_reset(int initial, int blocking)
512 // FUNCDEF("allocator_reset")
515 throw "error: array::allocator_reset: has bad block size";
519 if (initial < 0) initial = 0; // no antimatter arrays.
521 // remove old contents.
522 delete [] c_mem_block;
526 c_active_length = initial; // reset the length to the reporting size.
527 c_real_length = initial + blocking; // compute the real length.
529 c_mem_block = new contents[c_real_length];
531 // this is an odd situation; memory allocation didn't blow out an
532 // exception, but the memory block is empty. let's consider that
533 // a fatal error; we can't issue empty objects.
534 throw common::OUT_OF_MEMORY;
536 c_offset = c_mem_block; // reset offset to start of array.
541 template <class contents>
542 void array<contents>::shift_data(shift_directions where)
544 if (where == TO_LEFT) {
545 // we want to end up with the data jammed up against the left edge. thus
546 // we need the offset to be zero bytes from start.
547 if (c_offset == c_mem_block)
548 return; // offset already at start, we're done.
549 // well, we need to move the data.
551 memmove(c_mem_block, c_offset, c_active_length * sizeof(contents));
553 for (contents *ptr = c_offset; ptr < c_offset + c_active_length; ptr++)
554 c_mem_block[ptr - c_offset] = *ptr;
556 c_offset = c_mem_block; // we've ensured that this is correct.
557 if (c_flags & FLUSH_INVISIBLE) {
558 // we need to clean up what might have had contents previously.
559 // for (contents *p = c_mem_block + c_active_length; p < c_mem_block + c_real_length; p++)
563 // we want to move the data to the right, so the offset should be the
564 // difference between the real length and the length.
565 if (c_offset == c_mem_block + c_real_length - c_active_length)
566 return; // the offset is already the right size.
568 memmove(&c_mem_block[c_real_length - c_active_length], c_offset, c_active_length * sizeof(contents));
570 for (int i = c_real_length - 1; i >= c_real_length - c_active_length; i--)
571 c_mem_block[i] = c_offset[i - c_real_length + c_active_length];
573 c_offset = c_mem_block + c_real_length - c_active_length; // we've now ensured this.
574 if (c_flags & FLUSH_INVISIBLE) {
575 // we need to clean up the space on the left where old contents might be.
576 // for (contents *p = c_mem_block; p < c_offset; p++)
582 template <class contents>
583 outcome array<contents>::resize(int new_size, how_to_copy way)
585 /// FUNCDEF("resize");
586 if (new_size < 0) new_size = 0; // we stifle this.
587 if (new_size == c_active_length) {
588 // nothing much to do.
591 // okay, now we at least know that the sizes are different. we save all the
592 // old information about the array prior to this resizing.
593 contents *old_s = c_mem_block; // save the old contents...
594 const int old_len = c_active_length; // and length.
595 contents *old_off = c_offset; // and offset.
596 bool delete_old = false; // if true, old memory is whacked once it's copied.
598 //hmmm: wasn't there a nice realization that we could bail out early in
599 // the case where the size is already suffcient? there seems to be
600 // an extraneous copy case here.
601 // also it would be nice to have better, more descriptive names for the
602 // variables here since they are not lending themselves to understanding
605 // we check whether there's easily enough space in the array already.
606 // if not, then we have some more decisions to make.
607 if (c_real_length - (old_off - old_s) < new_size) {
608 // well, there's not enough space with the current space and offset.
609 if (c_real_length < new_size) {
610 // there's really not enough space overall, no fooling. we now will
611 // create a new block.
612 c_mem_block = NIL; // zero out the pointer so reset doesn't delete it.
615 if (exponential()) blocking = new_size + 1;
616 outcome ret = allocator_reset(new_size, blocking);
617 if (ret != common::OKAY) {
618 // failure, but don't forget to whack the old glob.
620 throw "error: array::resize: saw array reset failure";
625 // fall out to the copying phase, now that we have some fresh memory.
627 // there is enough space if we shift some things around.
628 const int size_difference = new_size - c_active_length;
629 // we compute how much space has to be found in the array somewhere
630 // to support the new larger size.
631 if (way == DONT_COPY) {
632 // simplest case; just reset the offset appropriately so the new_size
634 c_offset = c_mem_block;
635 c_active_length = new_size;
636 } else if (way == NEW_AT_BEGINNING) {
637 // if the new space is at the beginning, there are two cases. either
638 // the new size can be accomodated by the current position of the
639 // data or the data must be shifted to the right.
640 if (c_offset - c_mem_block < size_difference) {
641 // we need to shift the data over to the right since the offset isn't
642 // big enough for the size increase.
643 shift_data(TO_RIGHT); // resets the offset appropriately.
645 // now we know that the amount of space prior to the real data
646 // is sufficient to hold what new space is needed. we just need to
647 // shift the offset back somewhat.
648 c_offset -= size_difference;
649 c_active_length = new_size;
651 // better only be three ways to do this; we're now assuming the new
652 // space should be at the end (NEW_AT_END).
653 // now that we're here, we know there will be enough space if we shift
654 // the block to the left, but we DO NEED to do this. if we didn't need
655 // to shift the data, then we would find that:
656 // c_real_length - old_off >= new_size
657 // which is disallowed by the guardian conditional around this area.
658 shift_data(TO_LEFT); // resets the offset for us.
659 c_active_length = new_size;
661 // we have ensured that we had enough space and we have already shifted
662 // the data around appropriately. we no longer need to enter the next
663 // block where we would copy data around if we had to. it has become
664 // primarily for cases where either we have to copy data because we
665 // have new storage to fill or where we are shrinking the array.
670 // the blob of code below is offset invariant. by the time we reach here,
671 // the array should be big enough and the offset should be okay.
672 c_active_length = new_size; // set length to the new reporting size.
673 if (way != DONT_COPY) {
674 int where = 0; // offset for storing into new array.
675 bool do_copy = false; // if true, then we need to move the data around.
676 contents *loopc_offset_old = old_off; // offset into original object.
677 // we should only have to copy the memory in one other case besides our
678 // inhabiting new memory--when we are asked to resize with the new stuff
679 // at the beginning of the array. if the new space is at the end, we're
680 // already looking proper, but if the new stuff is at the beginning, we
681 // need to shift existing stuff downwards.
682 if (way == NEW_AT_BEGINNING) {
683 where = new_size - old_len; // move up existing junk.
684 if (where) do_copy = true; // do copy, since it's not immobile.
686 // array shrank; we need to do the loop differently for starting
687 // from the beginning. we skip to the point in the array that our
688 // suffix needs to start at.
689 loopc_offset_old -= where;
690 where = 0; // reset where so we don't have negative offsets.
693 const int size_now = minimum(old_len, c_active_length);
694 if (delete_old || do_copy) {
695 contents *offset_in_new = c_offset + where;
696 contents *posn_in_old = loopc_offset_old;
698 // memmove should take care of intersections.
699 memmove(offset_in_new, posn_in_old, size_now * sizeof(contents));
701 // we need to do the copies using the object's assignment operator.
702 if (new_size >= old_len) {
703 for (int i = size_now - 1; i >= 0; i--)
704 offset_in_new[i] = posn_in_old[i];
706 for (int i = 0; i < size_now; i++)
707 offset_in_new[i] = posn_in_old[i];
711 // we only want to flush the obscured elements when we aren't already
712 // inhabiting new space.
713 if ( (c_flags & FLUSH_INVISIBLE) && !delete_old) {
714 // clear out the space that just went out of scope. we only do this
715 // for the flushing mode and when we aren't starting from a fresh
716 // pointer (i.e., delete_old isn't true).
717 if (new_size < old_len) {
718 // for (contents *p = posn_in_old; p < offset_in_new; p++)
724 if (delete_old) delete [] old_s;
728 template <class contents>
729 outcome array<contents>::retrain(int new_len, const contents *to_set)
731 /// FUNCDEF("retrain")
732 if (new_len < 0) new_len = 0; // stifle that bad length.
734 if (to_set && (c_mem_block >= to_set) && (c_mem_block < to_set + new_len) ) {
735 throw "error: array::retrain: ranges overlap in retrain!";
738 outcome ret = resize(new_len, DONT_COPY);
739 if (ret != common::OKAY) return ret;
741 if (new_len != c_active_length) {
742 throw "error: array resize set the wrong length";
747 memcpy(c_offset, to_set, c_active_length * sizeof(contents));
749 for (int i = 0; i < c_active_length; i++)
750 c_offset[i] = to_set[i];
752 if (c_flags & FLUSH_INVISIBLE) {
753 // no contents provided, so stuff the space with blanks.
754 // for (int i = 0; i < c_active_length; i++) c_offset[i] = contents();
757 if (c_flags & FLUSH_INVISIBLE) {
758 // for (contents *ptr = c_mem_block; ptr < c_offset; ptr++)
759 // *ptr = contents();
760 // for (contents *ptr = c_offset + c_active_length; ptr < c_mem_block + c_real_length; ptr++)
761 // *ptr = contents();
766 template <class contents>
767 outcome array<contents>::zap(int position1, int position2)
769 if (position1 > position2) return common::OKAY;
770 bounds_return(position1, 0, c_active_length - 1, common::OUT_OF_RANGE);
771 bounds_return(position2, 0, c_active_length - 1, common::OUT_OF_RANGE);
773 // if they're whacking from the beginning, we just reset the offset.
774 c_offset += position2 + 1;
775 c_active_length -= position2 + 1;
778 const int difference = position2 - position1 + 1;
779 // copy from just above position2 down into position1.
781 if (c_active_length - difference - position1 > 0)
782 memmove(&c_offset[position1], &c_offset[position1 + difference],
783 (c_active_length - difference - position1) * sizeof(contents));
785 for (int i = position1; i < c_active_length - difference; i++)
786 c_offset[i] = c_offset[i + difference];
789 outcome ret = resize(c_active_length - difference, NEW_AT_END);
790 // chop down to new size.
792 if (ret != common::OKAY) {
793 throw "error: array::zap: resize failure";
800 template <class contents>
801 outcome array<contents>::insert(int position, int elem_to_add)
803 if (position < 0) return common::OUT_OF_RANGE;
804 if (position > this->length())
805 position = this->length();
806 if (elem_to_add < 0) return common::OUT_OF_RANGE;
807 how_to_copy how = NEW_AT_END;
808 if (position == 0) how = NEW_AT_BEGINNING;
809 resize(this->length() + elem_to_add, how);
811 // if the insert wasn't at the front, we have to copy stuff into the new
813 if (how == NEW_AT_END) {
814 const contents simple_default_object = contents();
815 if (!this->simple()) {
816 for (int i = this->last(); i >= position + elem_to_add; i--)
817 this->access()[i] = this->observe()[i - elem_to_add];
818 for (int j = position; j < position + elem_to_add; j++)
819 this->access()[j] = simple_default_object;
821 memmove(&(this->access()[position + elem_to_add]),
822 &(this->observe()[position]), (this->length() - position
823 - elem_to_add) * sizeof(contents));
824 for (int j = position; j < position + elem_to_add; j++)
825 memcpy(&this->access()[j], &simple_default_object, sizeof(contents));
831 template <class contents>
832 outcome array<contents>::put(int index, const contents &to_put)
834 bounds_return(index, 0, this->last(), common::OUT_OF_RANGE);
836 this->access()[index] = to_put;
838 memcpy(&(this->access()[index]), &to_put, sizeof(contents));
842 template <class contents>
843 void array<contents>::snarf(array<contents> &new_contents)
845 if (this == &new_contents) return; // no blasting own feet off.
846 reset(); // trash our current storage.
847 swap_contents(new_contents);
851 //! a simple wrapper of an array of char *, used by portable::break_line().
852 class char_star_array : public array<char *>
855 char_star_array() : array<char *>(0, NIL, SIMPLE_COPY | EXPONE
856 | FLUSH_INVISIBLE) {}
858 // clean up all the memory we're holding.
859 for (int i = 0; i < length(); i++) {
868 #undef static_class_name