core/library/structures/amorph.h

   1 #ifndef AMORPH_CLASS
   2 #define AMORPH_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : amorph                                                            *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   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 \*****************************************************************************/
  17
  18 #include "object_packers.h"
  19
  20 #include <basis/astring.h>
  21 #include <basis/functions.h>
  22 #include <basis/contracts.h>
  23 #include <basis/guards.h>
  24
  25 //! A dynamic container class that holds any kind of object via pointers.
  26 /*!
  27   The object is considered owned by the amorph unless re-acquired from it,
  28   and will be deleted when the amorph is destroyed.
  29
  30   An amorph has a specified number of fields at any one time, but the number
  31   can be changed with "zap", "insert" and "adjust".  Fields in the amorph
  32   are either full or empty, where an empty field in the amorph has NIL as
  33   its content.  "put" adds a new field to the amorph.  "get" retrieves the
  34   contents of a field as a constant.  "acquire" is used to check a field
  35   out of the amorph, meaning that the amorph no longer possesses that field.
  36   The legal range of indices in an amorph is from 0 through
  37   "elements() - 1".  In general, a range violation for an index is
  38   treated as an invalid request and is ignored (although BAD_INDEX is
  39   returned by functions with compatible return values).
  40
  41   Model:
  42
  43   The policy followed in amorph is that once an object is checked in with
  44   "put" or "append", then the amorph owns that object.  The object must not
  45   be destroyed externally, because the amorph will automatically destroy
  46   the object when either: 1) the amorph itself is destroyed, or 2) another
  47   object is entered into the same field.  If the stored object must be
  48   destroyed externally, then it should be checked out of the amorph with
  49   "acquire"; after that, the pointer may be deleted.  "get" and "borrow"
  50   return a pointer to the stored item while leaving it checked in to the
  51   amorph.  it is safe to modify what was "borrow"ed or to look at what one
  52   "get"s, but do not destroy the pointers returned from either method.
  53 */
  54
  55 namespace structures {
  56
  57 template <class contents>
  58 class amorph : private basis::array<contents *>
  59 {
  60 public:
  61   amorph(int elements = 0);
  62     //!< constructs an amorph capable of holding "elements" pointers.
  63
  64   ~amorph();
  65
  66   int elements() const { return this->length(); }
  67     //!< the maximum number of elements currently allowed in this amorph.
  68
  69   int valid_fields() const { return _fields_used; }
  70     //!< Returns the number of fields that have non-NIL contents.
  71     /*!< This might be different from the number of total elements. */
  72
  73   void adjust(int new_max);
  74     //!< Changes the maximum number of elements for this amorph.
  75     /*!< If the new number is smaller than the original, then the fields at
  76     index "new_maximum" and upwards are thrown away.  existing fields are
  77     kept. */
  78
  79   void reset(int new_maximum = 0);
  80     //!< like adjust but doesn't keep existing contents.
  81
  82   basis::outcome put(int field, const contents *data);
  83     //!< Enters an object into the field at index "field" in the amorph.
  84     /*!< If "data" is NIL, then the field is cleared.  The amorph considers the
  85     pointer "data" to be its own property after put is invoked; "data"
  86     should not be destructed since the amorph will automatically do so.
  87     This restriction does not hold if the object is checked back out of
  88     the amorph with acquire(). */
  89
  90   basis::outcome append(const contents *data);
  91     //!< puts "data" on the end of this amorph.
  92     /*!< adds an element to the end of the amorph by increasing the amorph size
  93     (with "adjust") and putting the element into the new spot (with "put"). */
  94
  95   basis::outcome operator += (const contents *data) { return append(data); }
  96     //!< a synonym for append.
  97
  98   //! Returns a constant pointer to the information at the index "field".
  99   /*! If no information is stored or the field is out range, then NIL is
 100   returned. */
 101   const contents *get(int field) const;
 102   //! Returns a pointer to the information at the index "field".
 103   /*! Also returns NIL for invalid indexes.  DO NOT destroy the returned
 104   pointer; it is still owned by the amorph. */
 105   contents *borrow(int field);
 106
 107   //! synonym for get.
 108   const contents *operator [] (int field) const { return get(field); }
 109   //! synonym for borrow.
 110   contents *operator [] (int field) { return borrow(field); }
 111
 112   contents *acquire(int field);
 113     //!< Retrieves a "field" from the amorph, taking responsibility for it back.
 114     /*!< This function is similar to get, except that the contents are pulled
 115     out of the amorph.  The contents will no longer be destroyed when the
 116     amorph is destroyed.  To store the modified contents again, use put,
 117     and then the amorph will take over management of the contents again.
 118     Note that the index is not zapped with this function; the acquired
 119     "field" will simply hold a null pointer. */
 120
 121   basis::outcome clear(int field);
 122     //!< Clears the contents of the field specified.
 123     /*!< Clearing an empty field has no effect.  Clearing an invalid field has
 124     no effect.  NOTE: clearing the contents means that the contents are
 125     destroyed, not just disconnected. */
 126
 127   void clear_all();
 128     //!< Clears every field in the amorph.
 129
 130   basis::outcome zap(int start, int end);
 131     //!< Removes a range of indices from the amorph.
 132     /*!< This does not just clear the field associated with the specified index
 133     as "clear" does, it actually changes the number of total elements by
 134     removing the indices from the amorph.  The new amorph contains the old
 135     elements up to just before the "start" and from the "end" + 1 through the
 136     end of the amorph.  AMORPH_BAD_INDEX is returned if either index is out of
 137     range.  If the zap succeeds, then AMORPH_OKAY is returned, even if the
 138     "end" is less than the "start". */
 139
 140   basis::outcome insert(int position, int lines_to_add);
 141     //!< Adds "lines_to_add" indices to the amorph at the index "position".
 142     /*!< If "lines_to_add" is non-positive, the request is ignored.  Inserting
 143     at a position beyond the bounds of the array is ignored, but a position AT
 144     elements() is allowed (it is an append...). */
 145
 146   int find_empty(basis::outcome &o) const;
 147     //!< Returns the index of a free field if there are any.
 148     /*!< The returned index is invalid if the "o" is IS_FULL. */
 149
 150   const contents *next_valid(int &field) const;
 151     //!< Returns the contents of the next valid element at or after "field".
 152     /*!< "field" is set to the location where an entry was found, if one was
 153     actually found.  If none exists at "field" or after it, then NIL is
 154     returned. */
 155
 156   int find(const contents *to_locate, basis::outcome &o);
 157     //!< Searches the amorph for the contents specified.
 158     /*!< Since only pointers to the contents are maintained, the search is
 159     based on finding a pointer in the amorph that is identical to "to_locate".
 160     if "o" is OKAY, then the index of the entry is returned.  If
 161     "o" is NOT_FOUND, then the contents are not present. */
 162
 163   void swap_contents(amorph<contents> &other);
 164     //!< Exchanges the contents of "this" and "other".
 165     /*!< No validation is performed but this should always succeed given
 166     amorphs that are constructed properly. */
 167
 168 private:
 169   int _fields_used;  //!< The number of fields currently full of info.
 170
 171   void check_fields(const char *where) const;
 172     //!< Crashes out if the field count is wrong.
 173     /*!< This is only used for the debugging version. */
 174
 175   void set_nil(int start, int end);
 176     // Puts NIL in the indices between start and end.
 177     /*!< Does not delete whatever used to reside there; it just sets the
 178     pointers to NIL. */
 179
 180   // not to be used: amorphs should not be copied because it is intended that
 181   // they support storing heavyweight objects that either have no copy
 182   // constructors or have high-cost copy constructors.
 183   amorph(const amorph &to_copy) {}  //!< not to be used.
 184   amorph &operator = (const amorph &to_copy) { return *this; }
 185     //!< not to be used.
 186 };
 187
 188 //////////////
 189
 190 // these extensions are phrased as macros to avoid including the headers
 191 // necessary for compiling them.  to use them, just put the macro name in
 192 // the file where the template is needed.
 193
 194 //////////////
 195
 196 //! This can be used when the templated object has a copy constructor.
 197 /*! this makes the "to_assign" into a copy of the "to_copy" amorph. */
 198 template <class contents>
 199 void amorph_assign(amorph<contents> &to_assign,
 200     const amorph<contents> &to_copy);
 201
 202 //////////////
 203
 204 //! support for packing an amorph into an array of bytes.
 205 /*!
 206   this can be used when the underlying object is based on packable or
 207   supports the same pack/unpack methods.  note that if there are empty spots in
 208   the amorph, they are not packed.  when the packed form is unpacked again, it will
 209   have only the first N elements set, where N is the number of non-empty items.
 210 */
 211 template <class contents>
 212 void amorph_pack(basis::byte_array &packed_form, const amorph<contents> &to_pack);
 213
 214 //! unpacks the amorph from an array of bytes.
 215 template <class contents>
 216 bool amorph_unpack(basis::byte_array &packed_form, amorph<contents> &to_unpack);
 217
 218 //! reports how large the packed form will be.
 219 template <class contents>
 220 int amorph_packed_size(const amorph<contents> &to_pack);
 221
 222 // implementation for longer methods...
 223
 224 //#define DEBUG_AMORPH
 225   // uncomment to enable more testing, as well as complaints on errors.
 226
 227 #undef static_class_name
 228 #define static_class_name() "amorph"
 229   // used in bounds_halt macro.
 230
 231 #undef AMO_ALERT
 232 #ifdef DEBUG_AMORPH
 233   #include <basis/astring.h>
 234   #define AMO_ALERT(a, b, c) basis::throw_error(basis::astring(a), basis::astring(func), basis::astring(b) + " -- " + c)
 235   #define CHECK_FIELDS check_fields(func)
 236 #else
 237   #define AMO_ALERT(a1, a2, a3) {}
 238   #define CHECK_FIELDS { if (!func) {} }
 239 #endif
 240
 241 //////////////
 242
 243 template <class contents>
 244 amorph<contents>::amorph(int elements)
 245 : basis::array<contents *>(elements, NIL, basis::array<contents *>::SIMPLE_COPY
 246       | basis::array<contents *>::EXPONE | basis::array<contents *>::FLUSH_INVISIBLE),
 247   _fields_used(0)
 248 {
 249   FUNCDEF("constructor");
 250   set_nil(0, elements - 1);
 251   CHECK_FIELDS;
 252 }
 253
 254 template <class contents>
 255 amorph<contents>::~amorph()
 256 {
 257   FUNCDEF("destructor");
 258   CHECK_FIELDS;
 259   clear_all();
 260 }
 261
 262 template <class contents>
 263 void amorph<contents>::set_nil(int start, int end)
 264 {
 265   for (int i = start; i <= end; i++)
 266     basis::array<contents *>::put(i, (contents *)NIL);
 267 }
 268
 269 template <class contents>
 270 void amorph<contents>::check_fields(const char *where) const
 271 {
 272   FUNCDEF("check_fields");
 273   int counter = 0;
 274   for (int i = 0; i < elements(); i++)
 275     if (basis::array<contents *>::get(i)) counter++;
 276   if (_fields_used != counter) {
 277     AMO_ALERT("amorph", basis::a_sprintf("check_fields for %s", where),
 278         "error in _fields_used count");
 279   }
 280 }
 281
 282 template <class contents>
 283 void amorph<contents>::reset(int new_maximum)
 284 {
 285   FUNCDEF("reset");
 286   CHECK_FIELDS;
 287   adjust(new_maximum);
 288   clear_all();
 289 }
 290
 291 template <class contents>
 292 void amorph<contents>::clear_all()
 293 {
 294   FUNCDEF("clear_all");
 295   CHECK_FIELDS;
 296   for (int i = 0; i < elements(); i++) clear(i);
 297 }
 298
 299 template <class contents>
 300 basis::outcome amorph<contents>::append(const contents *data)
 301 {
 302   FUNCDEF("append");
 303   CHECK_FIELDS;
 304   adjust(elements() + 1);
 305   return put(elements() - 1, (contents *)data);
 306 }
 307
 308 template <class contents>
 309 const contents *amorph<contents>::get(int field) const
 310 {
 311   FUNCDEF("get");
 312   CHECK_FIELDS;
 313   bounds_return(field, 0, elements() - 1, NIL);
 314   return basis::array<contents *>::observe()[field];
 315 }
 316
 317 template <class contents>
 318 void amorph<contents>::adjust(int new_maximum)
 319 {
 320   FUNCDEF("adjust");
 321   CHECK_FIELDS;
 322   if (new_maximum < 0) return;  // bad input here.
 323   int old_max = elements();
 324   if (new_maximum == old_max) return;  // nothing to do.
 325   if (new_maximum < old_max) {
 326     // removes the elements beyond the new size of the amorph.
 327     zap(new_maximum, old_max - 1);
 328     // we're done tuning it.
 329     return;
 330   }
 331
 332   // we get to here if we need more space than we used to.
 333   int new_fields = new_maximum - old_max;
 334
 335   basis::array<contents *>::insert(old_max, new_fields);
 336   for (int i = old_max; i < new_maximum; i++) {
 337     basis::array<contents *>::put(i, NIL);
 338   }
 339 }
 340
 341 template <class contents>
 342 basis::outcome amorph<contents>::insert(int position, int lines_to_add)
 343 {
 344   FUNCDEF("insert");
 345   CHECK_FIELDS;
 346   bounds_return(position, 0, elements(), basis::common::OUT_OF_RANGE);
 347   basis::outcome o = basis::array<contents *>::insert(position, lines_to_add);
 348   if (o != basis::common::OKAY) return basis::common::OUT_OF_RANGE;
 349   set_nil(position, position + lines_to_add - 1);
 350   return basis::common::OKAY;
 351 }
 352
 353 template <class contents>
 354 basis::outcome amorph<contents>::zap(int start_index, int end_index)
 355 {
 356   FUNCDEF("zap");
 357   CHECK_FIELDS;
 358   bounds_return(start_index, 0, elements() - 1, basis::common::OUT_OF_RANGE);
 359   bounds_return(end_index, 0, elements() - 1, basis::common::OUT_OF_RANGE);
 360   if (end_index < start_index) return basis::common::OKAY;
 361   for (int i = start_index; i <= end_index;  i++) clear(i);
 362   basis::outcome o = basis::array<contents *>::zap(start_index, end_index);
 363   return (o == basis::common::OKAY? basis::common::OKAY : basis::common::OUT_OF_RANGE);
 364 }
 365
 366 template <class contents>
 367 basis::outcome amorph<contents>::put(int field, const contents *data)
 368 {
 369   FUNCDEF("put");
 370   CHECK_FIELDS;
 371   bounds_return(field, 0, elements() - 1, basis::common::OUT_OF_RANGE);
 372   contents *to_whack = acquire(field);
 373   WHACK(to_whack);
 374   if (data) {
 375     basis::array<contents *>::access()[field] = (contents *)data;
 376     _fields_used++;
 377   }
 378   return basis::common::OKAY;
 379 }
 380
 381 template <class contents>
 382 int amorph<contents>::find_empty(basis::outcome &o) const
 383 {
 384   FUNCDEF("find_empty");
 385   CHECK_FIELDS;
 386   if (_fields_used == elements()) { o = basis::common::IS_FULL; return 0; }
 387   for (int i = 0; i < elements(); i++)
 388     if (!basis::array<contents *>::get(i)) { o = basis::common::OKAY; return i; }
 389   AMO_ALERT("amorph", "empty", "_fields_used is incorrect");
 390   return basis::common::IS_FULL;
 391 }
 392
 393 template <class contents>
 394 const contents *amorph<contents>::next_valid(int &field) const
 395 {
 396   FUNCDEF("next_valid");
 397   CHECK_FIELDS;
 398   bounds_return(field, 0, elements() - 1, NIL);
 399   for (int i = field; i < elements(); i++)
 400     if (basis::array<contents *>::get(i)) {
 401       field = i;
 402       return basis::array<contents *>::get(i);
 403     }
 404   return NIL;
 405 }
 406
 407 template <class contents>
 408 basis::outcome amorph<contents>::clear(int field)
 409 {
 410   FUNCDEF("clear");
 411   CHECK_FIELDS;
 412   return this->put(field, NIL);
 413 }
 414
 415 template <class contents>
 416 contents *amorph<contents>::acquire(int field)
 417 {
 418   FUNCDEF("acquire");
 419   CHECK_FIELDS;
 420   contents *to_return = borrow(field);
 421   if (to_return) {
 422     _fields_used--;
 423     basis::array<contents *>::access()[field] = NIL;
 424   }
 425   return to_return;
 426 }
 427
 428 template <class contents>
 429 int amorph<contents>::find(const contents *to_locate, basis::outcome &o)
 430 {
 431   FUNCDEF("find");
 432   CHECK_FIELDS;
 433   if (!_fields_used) { o = basis::common::NOT_FOUND; return 0; }
 434   for (int i = 0; i < elements(); i++) {
 435     if (basis::array<contents *>::get(i) == to_locate) {
 436       o = basis::common::OKAY;
 437       return i;
 438     }
 439   }
 440   o = basis::common::NOT_FOUND;
 441   return 0;
 442 }
 443
 444 template <class contents>
 445 contents *amorph<contents>::borrow(int field)
 446 {
 447   FUNCDEF("borrow");
 448   CHECK_FIELDS;
 449   bounds_return(field, 0, elements() - 1, NIL);
 450   return basis::array<contents *>::access()[field];
 451 }
 452
 453 template <class contents>
 454 void amorph<contents>::swap_contents(amorph<contents> &other)
 455 {
 456   FUNCDEF("swap_contents");
 457   CHECK_FIELDS;
 458   int hold_fields = _fields_used;
 459   _fields_used = other._fields_used;
 460   other._fields_used = hold_fields;
 461   this->basis::array<contents *>::swap_contents(other);
 462 }
 463
 464 template <class contents>
 465 int amorph_packed_size(const amorph<contents> &to_pack)
 466 {
 467   int parts_size = 0;
 468   for (int i = 0; i < to_pack.elements(); i++) {
 469     const contents *current = to_pack.get(i);
 470     if (current) parts_size += current->packed_size();
 471   }
 472   return PACKED_SIZE_INT32 + parts_size;
 473 }
 474
 475 template <class contents>
 476 void amorph_pack(basis::byte_array &packed_form, const amorph<contents> &to_pack)
 477 {
 478   structures::attach(packed_form, to_pack.elements());
 479   for (int i = 0; i < to_pack.elements(); i++) {
 480     const contents *current = to_pack.get(i);
 481     if (current) current->pack(packed_form);
 482   }
 483 }
 484
 485 template <class contents>
 486 bool amorph_unpack(basis::byte_array &packed_form, amorph<contents> &to_unpack)
 487 {
 488   to_unpack.reset();
 489   int elem = 0;
 490   if (!structures::detach(packed_form, elem)) return false;
 491   for (int i = 0; i < elem; i++) {
 492     contents *to_add = new contents;
 493     if (!to_add->unpack(packed_form)) { delete to_add; return false; }
 494     to_unpack.append(to_add);
 495   }
 496   return true;
 497 }
 498
 499 template <class contents>
 500 void amorph_assign(amorph<contents> &to_assign,
 501     const amorph<contents> &to_copy)
 502 {
 503   if (&to_assign == &to_copy) return;
 504   to_assign.clear_all();
 505   if (to_assign.elements() != to_copy.elements()) {
 506     to_assign.zap(0, to_assign.elements() - 1);
 507     to_assign.insert(0, to_copy.elements());
 508   }
 509   for (int i = 0; i < to_assign.elements(); i++) {
 510     if (to_copy.get(i)) to_assign.put(i, new contents(*to_copy.get(i)));
 511     else to_assign.put(i, (contents *)NIL);
 512   }
 513 }
 514
 515 #undef static_class_name
 516
 517 } //namespace.
 518
 519 #endif
 520