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