[boost] Bidirectional relation pointers using C++ templates with member pointer parameters

From: Andy Glew (glew_at_[hidden])
Date: 1999-09-23 12:37:14

Summary
=======

I have succeeded in creating automatically maintained consistent
"smart pointers" in C++ using templates that accept pointers
to members as template parameters.

E.g. you can declare/define your data structures like this

    struct test1 {
      bidirectional_ptr<test2> t12a;
    };
    struct test2 {
      bidirectional_ptr<test1> t21a;
    };

    // schema
    typedef bidirectional_relation<test1, test2, &test1::t12a, &test2::t21a > relation_from_1_to_2;

and then do

  relation_from_1_to_2::set_bidirectional_ptrs( t1, t2 );

and use structure/class data member syntax to access the pointers.

  t1.t12a->print();

I plan to use this approach to create more automatically consistent
data structures - 1:1, 1:many, many:many relations - as well as
to create STL equivalent multicontainers.

At this time I invite those of you who have in the past expressed
interest in such data structures to contact me, so that we can explore
the space of useful and convenient interfaces.

Detail
======

I have talked to all of you, at one time or another, about my desire
for data structures whose consistency is automatically maintained.
Several Boost mailing list members have indicated their desire 
for such structures.

E.g. bidirectional pointers: if a.p1 points to b, then b.p2 points to
a. 

Or, similarly, my desire for "multicontainers", objects that are on
multiple data structure "access paths" simultaneously, and for which
it is an O(1) operation to cross from one to the other.
Multicontainers are useful in creating such automatically consistent
data structures. Consensus was that multiple inheritance was "the way"
to create such generic multicontainers in C++, a solution I found
abhorrent compared to the C preprocessor macro solution which looks
like LINK(p,next,p->next,prev).

I have encountered such data structures in Object Oriented Database
languages. They are nice, and greatly reduce errors. I recognized my
desire in Jiri Soukup's Dr Dobb's Journal article "C++ Data Structures
as Objects", October 1999; Jiri has two implementations, one using a
preprocessor, the other using templates and multiple inheritance, much
as I had been doing already. I find neither the preprocessor nor the
multiple inheritance solution acceptable.

C++ data declaration rules prevent "the right" solution
-------------------------------------------------------

I would have liked to be able to do something like

    // schema
    typedef bidirectional_relation<test1, test2, &test1::t12a, &test2::t21a > relation_from_1_to_2;

    struct test1 {
      relation_from_1_to_2::from_type t12a;
    };
    struct test2 {
      relation_from_1_to_2::to_type t12a;
    };

and then do

  t1.t12a = &t2;

and have that automatically establish the backwards link.

However, C++ does not allow a fieldname to be used as a template
parameter until it is defined (even though the storage layout doesn't
change). So different classes to establish the pointer and the actual
relation are necessary.  This loses a bit of type checking ability,
but not too much.

Linkage
-------

Now, with a level of indirection one can still say
  t1.t12a = &t2;

but the only implemenation I have made work is grotty, using negative
offsets.  Fearing that, I thought it was better to require an explicit
linkage

     relation_from_1_to_2::set_bidirectional_ptrs( t1, t2 );

Similar operations would be used
for 1 to many and many to many relations.

Although better names are certainly possible
     relation_from_1_to_2::link( t1, t2 );

I eventually felt obliged to give up on using operator notation,
which I idealized as
     t1.t12a <=> t2.t21a
because
    a) to do this properly would have required the full template
with member offsets as the member type
    b) again, I do not like the grotty solutions using negative
member templates that avoid the type issues
    c) but, the final word was that C++ does not have enough
symmetric binary operators: we can't define new ones like <=>,
and using =, ==, etc. seemed highly likely to be
misleading.

Debug features
--------------

The automatically maintained consistent bidirectional pointers could
be "registered", either in a class static for the relation, or in a
member of a relation object. This latter would allow multiple relation
objects to be created between given types using the same members. I am
uncertain if that is good or bad.

A pointer to the relation an object is in could be stored with its
linkage --- for bidirectional 1:1 relations, this would be overhead,
but such a pointer to thge relation could allow pointer consistency to
be checked while ignorant of the relation. Such a relation pointer
is much more natural for 1 to many and many to many relations.

The usual debug checks, such as requiring that a pointer be unlinked
before deallocation, can be made.

Code Example
------------

I here provide code examples. These are not fully fledged out - the
smart bidirectional_ptr<T> is not fully proxying T* - but it gives the
idea.  Works on gcc 2.95 -- which is actually the first version of
GCC/EGCS/G++ that I have been able to compile such templates with
pointers to member parameters.

// $Header: /u/g/l/glew/hack/biptr/RCS/bidirectional_relation.hh,v 1.1 1999/09/23 17:34:13 glew Exp $

template<class Ptee>
class  bidirectional_ptr {
public:
  Ptee* ptr;
public:
  bidirectional_ptr() : ptr(0) {}
private:
  bidirectional_ptr(bidirectional_ptr& c) { /* copy constructor disallowed */ }
  template<class T> bidirectional_ptr& operator=(T t) { /* assignment disallowed */ }
public:
  friend class bidirectional_relation_base;
public:
  Ptee& operator*() { return *ptr; }
  Ptee* operator->() { return ptr; }
};

class bidirectional_relation_base {
  int dummy;
};

template<
  class A, 
  class B, 
  bidirectional_ptr<B> A::*Amptr, 
  bidirectional_ptr<A> B::*Bmptr
> 
class bidirectional_relation : public bidirectional_relation_base {
private:
  static void
  clear_old_values( A& a, B& b );
public:
  static void
  clear_bidirectional_ptrs( A& a, B& b );
  static void
  set_bidirectional_ptrs( A& a, B& b );
};  

template<
  class A, 
  class B, 
  bidirectional_ptr<B> A::*Amptr, 
  bidirectional_ptr<A> B::*Bmptr
> 
inline
void
bidirectional_relation<A,B,Amptr,Bmptr>::clear_old_values( A& a, B& b ) {
  if( (a.*Amptr).ptr != 0 ) {
    ((a.*Amptr).ptr->*Bmptr).ptr = 0;
    (a.*Amptr).ptr = 0;
  }
  if( (b.*Bmptr).ptr != 0 ) {
    ((b.*Bmptr).ptr->*Amptr).ptr = 0;
    (b.*Bmptr).ptr = 0;
  }
}

template<
  class A, 
  class B, 
  bidirectional_ptr<B> A::*Amptr, 
  bidirectional_ptr<A> B::*Bmptr
> 
inline
void
bidirectional_relation<A,B,Amptr,Bmptr>::clear_bidirectional_ptrs( A& a, B& b ) {
  clear_old_values( a, b );
  (a.*Amptr).ptr = 0;
  (b.*Bmptr).ptr = 0;
}

template<
  class A, 
  class B, 
  bidirectional_ptr<B> A::*Amptr, 
  bidirectional_ptr<A> B::*Bmptr
> 
inline
void
bidirectional_relation<A,B,Amptr,Bmptr>::set_bidirectional_ptrs( A& a, B& b ) {
  clear_old_values( a, b );
  
  (a.*Amptr).ptr = &b;
  (b.*Bmptr).ptr = &a;
}

// $Header: /u/g/l/glew/hack/biptr/RCS/biptr.cc,v 1.4 1999/09/23 16:31:36 glew Exp $

#include <stdio.h>
#include "bidirectional_relation.hh"

// class definitions
struct test1;
struct test2;

struct test1 {
  bidirectional_ptr<test2> t12a;
  bidirectional_ptr<test2> t12b;
  void print() const {
    printf("test1:0x%08x t12a:0x%08x t12b:0x%08x\n",this,t12a.ptr, t12b.ptr);
  }
};
struct test2 {
  bidirectional_ptr<test1> t21b;
  bidirectional_ptr<test1> t21a;
  void print() const {
    printf("test2:0x%08x t21b:0x%08x t21a:0x%08x\n",this,t21b.ptr, t21a.ptr);
  }
};

// schema
typedef bidirectional_relation<test1, test2, &test1::t12a, &test2::t21a > ra;
typedef bidirectional_relation<test1, test2, &test1::t12b, &test2::t21b > rb;

main()
{
  test1 t1;
  test2 t2;

  printf( "initially unlinked objects t1 and t2\n");
  t1.print(); t2.print();

  ra::set_bidirectional_ptrs( t1, t2 );
  printf( "now they should be linked via t1.t12a and t2.t21a\n");
  t1.print(); t2.print();

  
  printf( "showing member notation t1.t12a.print() == t2.print()\n");
  t1.t12a->print();

  rb::set_bidirectional_ptrs( t1, t2 );
  printf( "now they should be linked via t1.t12b and t2.t21b\n");
  t1.print(); t2.print();

  ra::clear_bidirectional_ptrs( t1, t2 );
  printf( "now they should be unlinked via t1.t12a and t2.t21a\n");
  t1.print(); t2.print();

  rb::clear_bidirectional_ptrs( t1, t2 );
  printf( "now they should be unlinked via t1.t12b and t2.t21b\n");
  t1.print(); t2.print();

}

---
Andy Glew, glew_at_[hidden]
[Place URGENT in email subject line for mail filter prioritization.]