include/cln/object.h

   1 // General object definitions: pointers, reference counting, garbage collection.
   2
   3 #ifndef _CL_OBJECT_H
   4 #define _CL_OBJECT_H
   5
   6 #include "cln/types.h"
   7 #include "cln/modules.h"
   8 #include <cstdlib>
   9
  10 namespace cln {
  11
  12 // We don't have to deal with circular structures, so normal reference counting
  13 // is sufficient. Is also has the advantage of being mostly non-interrupting.
  14
  15
  16 // An object is either a pointer to heap allocated data
  17 //              or immediate data.
  18
  19 // It is possible to distinguish these because pointers are aligned.
  20 // cl_uint_alignment is the guaranteed alignment of a `void*' or `long'
  21 // in memory. Must be > 1.
  22 #if defined(__m68k__)
  23   #define cl_word_alignment  2
  24 #endif
  25 #if defined(__i386__) || defined(__mips__) || defined(__mipsel__) || defined(__sparc__) || defined(__hppa__) || defined(__arm__) || defined(__rs6000__) || defined(__m88k__) || defined(__convex__) || defined(__s390__)
  26   #define cl_word_alignment  4
  27 #endif
  28 #if defined(__alpha__) || defined(__ia64__) || defined(__mips64__) || defined(__powerpc64__) || defined(__sparc64__) || defined(__x86_64__)
  29   #define cl_word_alignment  8
  30 #endif
  31 #if !defined(cl_word_alignment)
  32   #error "Define cl_word_alignment for your CPU!"
  33 #endif
  34
  35
  36 // Four basic classes are introduced:
  37 //
  38 //   gcobject      rcobject
  39 //
  40 //   gcpointer     rcpointer
  41 //
  42 // `gcobject' = garbage collectible object (pointer or immediate),
  43 // `gcpointer' = garbage collectible pointer,
  44 // `rcobject' = reference counted object (pointer or immediate),
  45 // `rcpointer' = reference counted pointer.
  46 //
  47 // "garbage collectible" means that a reference count is maintained, and
  48 // when the reference count drops to 0, the object is freed. This is useful
  49 // for all kind of short- or long-lived objects.
  50 // "reference counted" means that a reference count is maintained, which
  51 // cannot drop to 0. This is useful for objects which are registered in a
  52 // global cache table, in order to know which objects can be thrown away
  53 // when the cache is cleaned. (If the cache were never cleaned, its objects
  54 // would never be freed, and we could get away with normal C pointers.)
  55 //
  56 // It is permissible to treat a `rcobject' as a `gcobject', and a `rcpointer'
  57 // as a `gcpointer', but this just increases the destructor and copy-constructor
  58 // overhead.
  59 // It is also permissible to treat a `gcpointer' as a `gcobject', and a
  60 // `rcpointer' as a `rcobject', but this just increases the destructor and
  61 // copy-constructor overhead.
  62
  63
  64 // Immediate data is a word, as wide as a pointer.
  65 typedef sintP  cl_sint;
  66 typedef uintP  cl_uint;  // This ought to be called `cl_word'.
  67 #define cl_pointer_size intPsize
  68 // NB: (cl_pointer_size==64) implies defined(HAVE_FAST_LONGLONG)
  69 #if (cl_pointer_size==64)
  70   #define CL_WIDE_POINTERS
  71 #endif
  72
  73 // Distinguish immediate data from pointers.
  74 inline cl_boolean cl_pointer_p (cl_uint word)
  75 {
  76         return (cl_boolean)((word & (cl_word_alignment-1)) == 0);
  77 }
  78 inline cl_boolean cl_immediate_p (cl_uint word)
  79 {
  80         return (cl_boolean)((word & (cl_word_alignment-1)) != 0);
  81 }
  82
  83 // Immediate data: Fixnum, Short Float, maybe Single Float.
  84 // They have type tags.
  85 //   |...............................|......|
  86 //               cl_value             cl_tag
  87
  88 // Number of bits reserved for tagging information:
  89 #if (cl_word_alignment <= 4)
  90   #define cl_tag_len    2
  91 #else
  92   #define cl_tag_len    3
  93 #endif
  94 #define cl_tag_shift    0
  95 #if (cl_pointer_size == 64)
  96   #define cl_value_shift  32
  97 #else
  98   #define cl_value_shift  (cl_tag_len+cl_tag_shift)
  99 #endif
 100 #define cl_value_len    (cl_pointer_size - cl_value_shift)
 101 #define cl_tag_mask     (((1UL << cl_tag_len) - 1) << cl_tag_shift)
 102 #define cl_value_mask   (((1UL << cl_value_len) - 1) << cl_value_shift)
 103
 104 // Return the tag of a word.
 105 inline cl_uint cl_tag (cl_uint word)
 106 {
 107         return (word & cl_tag_mask) >> cl_tag_shift;
 108 }
 109
 110 // Return the value (unsigned) of a word.
 111 inline cl_uint cl_value (cl_uint word)
 112 {
 113         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 114         return word >> cl_value_shift;
 115 }
 116
 117 // Return a word, combining a value and a tag.
 118 inline cl_uint cl_combine (cl_uint tag, cl_uint value)
 119 {
 120         return (value << cl_value_shift) + (tag << cl_tag_shift);
 121 }
 122 inline cl_uint cl_combine (cl_uint tag, cl_sint value)
 123 {
 124         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 125         return (value << cl_value_shift) + (tag << cl_tag_shift);
 126 }
 127 // Keep the compiler happy.
 128 inline cl_uint cl_combine (cl_uint tag, unsigned int value)
 129 { return cl_combine(tag, (cl_uint)value); }
 130 inline cl_uint cl_combine (cl_uint tag, int value)
 131 { return cl_combine(tag, (cl_sint)value); }
 132 #ifdef HAVE_LONGLONG
 133 inline cl_uint cl_combine (cl_uint tag, unsigned long long value)
 134 { return cl_combine(tag, (cl_uint)value); }
 135 inline cl_uint cl_combine (cl_uint tag, long long value)
 136 { return cl_combine(tag, (cl_uint)value); }
 137 #endif
 138
 139 // Definition of the tags.
 140 #if !defined(CL_WIDE_POINTERS)
 141   #if (cl_word_alignment == 2)
 142     #define cl_FN_tag   1
 143     #define cl_SF_tag   3       // must satisfy the cl_immediate_p predicate!
 144   #endif
 145   #if (cl_word_alignment == 4)
 146     #define cl_FN_tag   1
 147     #define cl_SF_tag   2
 148   #endif
 149 #else // CL_WIDE_POINTERS
 150   // Single Floats are immediate as well.
 151   #define cl_FN_tag     1
 152   #define cl_SF_tag     2
 153   #define cl_FF_tag     3
 154 #endif
 155
 156 // Corresponding classes.
 157 extern const struct cl_class * cl_immediate_classes [1<<cl_tag_len];
 158
 159
 160 // Heap allocated data contains a header, for two purposes:
 161 // - dynamic typing,
 162 // - reference count (a portable alternative to garbage collection,
 163 //   or the basis for a portable and interoperable garbage collection).
 164 struct cl_heap {
 165         int refcount;                   // reference count
 166         const struct cl_class * type;   // type tag
 167 };
 168
 169 // Function to destroy the contents of a heap object.
 170 typedef void (*cl_heap_destructor_function) (cl_heap* pointer);
 171 // Flags, may be ORed together.
 172 #define cl_class_flags_subclass_complex   1  // all instances belong to cl_N
 173 #define cl_class_flags_subclass_real      2  // all instances belong to cl_R
 174 #define cl_class_flags_subclass_float     4  // all instances belong to cl_F
 175 #define cl_class_flags_subclass_rational  8  // all instances belong to cl_RA
 176 #define cl_class_flags_number_ring       16  // all instances are rings whose
 177                                              // elements belong to cl_number
 178 #define cl_class_flags_modint_ring       32  // all instances are rings whose
 179                                              // elements belong to cl_MI
 180 #define cl_class_flags_univpoly_ring     64  // all instances are rings whose
 181                                              // elements belong to cl_UP
 182 // Function to print an object for debugging, to cerr.
 183 typedef void (*cl_heap_dprint_function) (cl_heap* pointer);
 184
 185 struct cl_class {
 186         cl_heap_destructor_function destruct;
 187         int flags;
 188         cl_heap_dprint_function dprint;
 189 };
 190
 191 // Free an object on heap.
 192 extern void cl_free_heap_object (cl_heap* pointer);
 193
 194 // Debugging support for dynamic typing: Register a debugging print function.
 195 #define cl_register_type_printer(type,printer)  \
 196   { extern cl_class type; type.dprint = (printer); }
 197
 198
 199 // cl_private_thing: An immediate value or a pointer into the heap.
 200 // This must be as wide as a `cl_uint'.
 201 // (Actually, this ought to be a  union { void*; cl_uint; }, but using
 202 // a pointer type generates better code.)
 203 // Never throw away a cl_private_thing, or reference counts will be wrong!
 204 typedef struct cl_anything * cl_private_thing;
 205
 206 // Increment the reference count.
 207 inline void cl_inc_pointer_refcount (cl_heap* pointer)
 208 {
 209         pointer->refcount++;
 210 }
 211
 212 // Decrement the reference count of a garbage collected pointer.
 213 inline void cl_gc_dec_pointer_refcount (cl_heap* pointer)
 214 {
 215         if (--pointer->refcount == 0)
 216                 cl_free_heap_object(pointer);
 217 }
 218 // Decrement the reference count of a reference counted pointer.
 219 inline void cl_rc_dec_pointer_refcount (cl_heap* pointer)
 220 {
 221         --pointer->refcount;
 222 }
 223
 224 // Increment the reference count.
 225 // This must be a macro, not an inline function, because pointer_p() and
 226 // inc_pointer_refcount() are non-virtual member functions, so that the
 227 // compiler can optimize it.
 228 #define cl_inc_refcount(x)  \
 229         if ((x).pointer_p())                                    \
 230                 (x).inc_pointer_refcount();                     \
 231
 232 // Decrement the reference count.
 233 // This must be a macro, not an inline function, because pointer_p() and
 234 // dec_pointer_refcount() are non-virtual member functions, so that the
 235 // compiler can optimize it.
 236 #define cl_dec_refcount(x)  \
 237         if ((x).pointer_p())                                    \
 238                 (x).dec_pointer_refcount();                     \
 239
 240 // The declaration of a copy constructor.
 241 // Restriction: The base class's default constructor must do nothing or
 242 // initialize `pointer' to a constant expression.
 243 #define CL_DEFINE_COPY_CONSTRUCTOR1(_class_)                    \
 244         _CL_DEFINE_COPY_CONSTRUCTOR1(_class_,_class_)
 245 #define _CL_DEFINE_COPY_CONSTRUCTOR1(_class_,_classname_)       \
 246 inline _class_::_classname_ (const _class_& x)                  \
 247 {                                                               \
 248         cl_uint x_word = x.word;                                \
 249         cl_inc_refcount(x);                                     \
 250         this->word = x_word;                                    \
 251 }
 252
 253 // The declaration of a copy constructor.
 254 // Restriction: The base class must have the usual `cl_private_thing'
 255 // constructor. Drawback: The base class must be known here.
 256 #define CL_DEFINE_COPY_CONSTRUCTOR2(_class_,_baseclass_)                \
 257         _CL_DEFINE_COPY_CONSTRUCTOR2(_class_,_class_,_baseclass_)
 258 #define _CL_DEFINE_COPY_CONSTRUCTOR2(_class_,_classname_,_baseclass_) \
 259 inline _class_::_classname_ (const _class_& x)                  \
 260         : _baseclass_ (as_cl_private_thing(x)) {}
 261
 262 // The declaration of an assignment operator.
 263 #define CL_DEFINE_ASSIGNMENT_OPERATOR(dest_class,src_class)     \
 264 inline dest_class& dest_class::operator= (const src_class& x)   \
 265 {                                                               \
 266         /* Be careful, we might be assigning x to itself. */    \
 267         cl_uint x_word = x.word;                                \
 268         cl_inc_refcount(x);                                     \
 269         cl_dec_refcount(*this);                                 \
 270         this->word = x_word;                                    \
 271         return *this;                                           \
 272 }
 273
 274 // We have a small problem with destructors: The specialized destructor
 275 // of a leaf class such as `cl_SF' should be more efficient than the
 276 // general destructor for `cl_N'. Since (by C++ specs) destructing a cl_SF
 277 // would run the destructors for cl_SF, cl_F, cl_R, cl_N (in that order),
 278 // and in the last step the compiler does not know any more that the object
 279 // actually is a cl_SF, there is no way to optimize the destructor!
 280 // ("progn-reversed" method combination is evil.)
 281 // And if we define "mirror"/"shadow" classes with no destructors (such
 282 // that `cl_F' inherits from `cl_F_no_destructor' buts adds a destructor)
 283 // then we need to add explicit conversion operators cl_SF -> cl_F -> cl_R ...,
 284 // with the effect that calling an overloaded function like `as_cl_F'
 285 // (which has two signatures `as_cl_F(cl_number)' and `as_cl_F(cl_F)')
 286 // with a cl_SF argument gives an "call of overloaded function is ambiguous"
 287 // error.
 288 // There is no help: If we want overloaded functions to be callable in a way
 289 // that makes sense, `cl_SF' has to be a subclass of `cl_F', and then the
 290 // destructor of `cl_SF' will do at least as much computation as the `cl_F'
 291 // destructor. Praise C++ ! :-((
 292 // (Even making `pointer_p()' a virtual function would not help.)
 293
 294
 295 // This is obnoxious.
 296 template <class key1_type, class value_type> struct cl_htentry1;
 297
 298 // The four concrete classes of all objects.
 299
 300 class cl_gcobject {
 301 public: /* ugh */
 302         union {
 303                 void*   pointer;
 304                 cl_heap* heappointer;
 305                 cl_uint word;
 306         };
 307 public:
 308 // Default constructor. (Used for objects with no initializer.)
 309         cl_gcobject ();
 310 // Destructor. (Used when a variable goes out of scope.)
 311         ~cl_gcobject ();
 312 // Copy constructor.
 313         cl_gcobject (const cl_gcobject&);
 314 // Assignment operator.
 315         cl_gcobject& operator= (const cl_gcobject&);
 316 // Distinguish immediate data from pointer.
 317         cl_boolean pointer_p() const
 318                 { return cl_pointer_p(word); }
 319 // Reference counting.
 320         void inc_pointer_refcount () const
 321                 { cl_inc_pointer_refcount(heappointer); }
 322         void dec_pointer_refcount () const
 323                 { cl_gc_dec_pointer_refcount(heappointer); }
 324 // Return the type tag of an immediate number.
 325         cl_uint nonpointer_tag () const
 326                 { return cl_tag(word); }
 327 // Return the type tag of a heap-allocated number.
 328         const cl_class * pointer_type () const
 329                 { return heappointer->type; }
 330 // Private pointer manipulations.
 331         cl_private_thing _as_cl_private_thing () const;
 332 // Private constructor.
 333         cl_gcobject (cl_private_thing p)
 334                 #if !(defined(__alpha__) && !defined(__GNUC__))
 335                 : pointer (p) {}
 336                 #else
 337                 { pointer = p; }
 338                 #endif
 339 // Debugging output.
 340         void debug_print () const;
 341 // Ability to place an object at a given address.
 342         void* operator new (size_t size, void* ptr) { (void)size; return ptr; }
 343         void* operator new (size_t size) { return ::operator new (size); }
 344 };
 345 inline cl_gcobject::cl_gcobject () {}
 346 inline cl_gcobject::~cl_gcobject () { cl_dec_refcount(*this); }
 347 CL_DEFINE_COPY_CONSTRUCTOR1(cl_gcobject)
 348 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_gcobject,cl_gcobject)
 349
 350 class cl_gcpointer {
 351 public: /* ugh */
 352         union {
 353                 void*   pointer;
 354                 cl_heap* heappointer;
 355                 cl_uint word;
 356         };
 357 public:
 358 // Default constructor. (Used for objects with no initializer.)
 359         cl_gcpointer ();
 360 // Destructor. (Used when a variable goes out of scope.)
 361         ~cl_gcpointer ();
 362 // Copy constructor.
 363         cl_gcpointer (const cl_gcpointer&);
 364 // Assignment operator.
 365         cl_gcpointer& operator= (const cl_gcpointer&);
 366 // Distinguish immediate data from pointer.
 367         cl_boolean pointer_p() const
 368                 { return cl_true; }
 369 // Reference counting.
 370         void inc_pointer_refcount () const
 371                 { cl_inc_pointer_refcount(heappointer); }
 372         void dec_pointer_refcount () const
 373                 { cl_gc_dec_pointer_refcount(heappointer); }
 374 // Return the type tag of an immediate number.
 375         cl_uint nonpointer_tag () const
 376                 { return cl_tag(word); }
 377 // Return the type tag of a heap-allocated number.
 378         const cl_class * pointer_type () const
 379                 { return heappointer->type; }
 380 // Private pointer manipulations.
 381         cl_private_thing _as_cl_private_thing () const;
 382 // Private constructor.
 383         cl_gcpointer (cl_private_thing p)
 384                 #if !(defined(__alpha__) && !defined(__GNUC__))
 385                 : pointer (p) {}
 386                 #else
 387                 { pointer = p; }
 388                 #endif
 389 // Debugging output.
 390         void debug_print () const;
 391 // Ability to place an object at a given address.
 392         void* operator new (size_t size, void* ptr) { (void)size; return ptr; }
 393         void* operator new (size_t size) { return ::operator new (size); }
 394 };
 395 inline cl_gcpointer::cl_gcpointer () {}
 396 inline cl_gcpointer::~cl_gcpointer () { cl_dec_refcount(*this); }
 397 CL_DEFINE_COPY_CONSTRUCTOR1(cl_gcpointer)
 398 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_gcpointer,cl_gcpointer)
 399
 400 class cl_rcobject {
 401 public: /* ugh */
 402         union {
 403                 void*   pointer;
 404                 cl_heap* heappointer;
 405                 cl_uint word;
 406         };
 407 public:
 408 // Default constructor. (Used for objects with no initializer.)
 409         cl_rcobject ();
 410 // Destructor. (Used when a variable goes out of scope.)
 411         ~cl_rcobject ();
 412 // Copy constructor.
 413         cl_rcobject (const cl_rcobject&);
 414 // Assignment operator.
 415         cl_rcobject& operator= (const cl_rcobject&);
 416 // Distinguish immediate data from pointer.
 417         cl_boolean pointer_p() const
 418                 { return cl_pointer_p(word); }
 419 // Reference counting.
 420         void inc_pointer_refcount () const
 421                 { cl_inc_pointer_refcount(heappointer); }
 422         void dec_pointer_refcount () const
 423                 { cl_rc_dec_pointer_refcount(heappointer); }
 424 // Return the type tag of an immediate number.
 425         cl_uint nonpointer_tag () const
 426                 { return cl_tag(word); }
 427 // Return the type tag of a heap-allocated number.
 428         const cl_class * pointer_type () const
 429                 { return heappointer->type; }
 430 // Private pointer manipulations.
 431         cl_private_thing _as_cl_private_thing () const;
 432 // Private constructor.
 433         cl_rcobject (cl_private_thing p)
 434                 #if !(defined(__alpha__) && !defined(__GNUC__))
 435                 : pointer (p) {}
 436                 #else
 437                 { pointer = p; }
 438                 #endif
 439 // Debugging output.
 440         void debug_print () const;
 441 // Ability to place an object at a given address.
 442         void* operator new (size_t size, void* ptr) { (void)size; return ptr; }
 443         void* operator new (size_t size) { return ::operator new (size); }
 444 };
 445 inline cl_rcobject::cl_rcobject () {}
 446 inline cl_rcobject::~cl_rcobject () { cl_dec_refcount(*this); }
 447 CL_DEFINE_COPY_CONSTRUCTOR1(cl_rcobject)
 448 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_rcobject,cl_rcobject)
 449
 450 class cl_rcpointer {
 451 public: /* ugh */
 452         union {
 453                 void*   pointer;
 454                 cl_heap* heappointer;
 455                 cl_uint word;
 456         };
 457 public:
 458 // Default constructor. (Used for objects with no initializer.)
 459         cl_rcpointer ();
 460 // Destructor. (Used when a variable goes out of scope.)
 461         ~cl_rcpointer ();
 462 // Copy constructor.
 463         cl_rcpointer (const cl_rcpointer&);
 464 // Assignment operator.
 465         cl_rcpointer& operator= (const cl_rcpointer&);
 466 // Distinguish immediate data from pointer.
 467         cl_boolean pointer_p() const
 468                 { return cl_true; }
 469 // Reference counting.
 470         void inc_pointer_refcount () const
 471                 { cl_inc_pointer_refcount(heappointer); }
 472         void dec_pointer_refcount () const
 473                 { cl_rc_dec_pointer_refcount(heappointer); }
 474 // Return the type tag of an immediate number.
 475         cl_uint nonpointer_tag () const
 476                 { return cl_tag(word); }
 477 // Return the type tag of a heap-allocated number.
 478         const cl_class * pointer_type () const
 479                 { return heappointer->type; }
 480 // Private pointer manipulations.
 481         cl_private_thing _as_cl_private_thing () const;
 482 // Private constructor.
 483         cl_rcpointer (cl_private_thing p)
 484                 #if !(defined(__alpha__) && !defined(__GNUC__))
 485                 : pointer (p) {}
 486                 #else
 487                 { pointer = p; }
 488                 #endif
 489 // Debugging output.
 490         void debug_print () const;
 491 // Ability to place an object at a given address.
 492         void* operator new (size_t size, void* ptr) { (void)size; return ptr; }
 493         void* operator new (size_t size) { return ::operator new (size); }
 494 };
 495 inline cl_rcpointer::cl_rcpointer () {}
 496 inline cl_rcpointer::~cl_rcpointer () { cl_dec_refcount(*this); }
 497 CL_DEFINE_COPY_CONSTRUCTOR1(cl_rcpointer)
 498 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_rcpointer,cl_rcpointer)
 499
 500 // Private pointer manipulations.
 501
 502 inline cl_private_thing cl_gcobject::_as_cl_private_thing () const
 503 {
 504         cl_private_thing p = (cl_private_thing) pointer;
 505         cl_inc_refcount(*this);
 506         return p;
 507 }
 508 inline cl_private_thing as_cl_private_thing (const cl_gcobject& x)
 509 {
 510         return x._as_cl_private_thing();
 511 }
 512
 513 inline cl_private_thing cl_gcpointer::_as_cl_private_thing () const
 514 {
 515         cl_private_thing p = (cl_private_thing) pointer;
 516         cl_inc_refcount(*this);
 517         return p;
 518 }
 519 inline cl_private_thing as_cl_private_thing (const cl_gcpointer& x)
 520 {
 521         return x._as_cl_private_thing();
 522 }
 523
 524 inline cl_private_thing cl_rcobject::_as_cl_private_thing () const
 525 {
 526         cl_private_thing p = (cl_private_thing) pointer;
 527         cl_inc_refcount(*this);
 528         return p;
 529 }
 530 inline cl_private_thing as_cl_private_thing (const cl_rcobject& x)
 531 {
 532         return x._as_cl_private_thing();
 533 }
 534
 535 inline cl_private_thing cl_rcpointer::_as_cl_private_thing () const
 536 {
 537         cl_private_thing p = (cl_private_thing) pointer;
 538         cl_inc_refcount(*this);
 539         return p;
 540 }
 541 inline cl_private_thing as_cl_private_thing (const cl_rcpointer& x)
 542 {
 543         return x._as_cl_private_thing();
 544 }
 545
 546 // Note: When we define a function that returns a class object by value,
 547 // we normally return it as const value. The declarations
 548 //            T func (...);                    (A)
 549 // and
 550 //            const T func (...);              (B)
 551 // behave identically and generate identical code, except that the code
 552 //            func(...) = foo;
 553 // compiles fine with (A) but is an error (and yields a warning) with (B).
 554 // We want this warning.
 555
 556 // Define a conversion operator from one object to another object of the
 557 // same size.
 558   #define CL_DEFINE_CONVERTER(target_class)  \
 559     operator const target_class & () const                              \
 560     {                                                                   \
 561       if (sizeof(*this) != sizeof(target_class)) cl_abort();            \
 562       return * (const target_class *) (void*) this;                     \
 563     }
 564
 565 }  // namespace cln
 566
 567 #endif /* _CL_OBJECT_H */