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