NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/lang/cplus/12547

Text File | 1992-08-19 | 6.7 KB | 249 lines

Path: sparky!uunet!zephyr.ens.tek.com!uw-beaver!cornell!batcomputer!caen!sdd.hp.com!swrinde!elroy.jpl.nasa.gov!decwrl!deccrl!bloom-beacon!eru.mt.luth.se!lunic!sunic!seunet!appli!niklas
From: [e-mail] (Niklas Hallqvist)
Newsgroups: comp.lang.c++
Subject: Re: Doubly-linked list trick (was Re: Garbage Collection for C++)
Message-ID: <[e-mail]>
Date: 19 Aug 92 08:33:14 GMT
References: <[e-mail]>> <[e-mail]> <[e-mail]> <[e-mail]>
Organization: Applitron Datasystem AB, GOTHENBURG, SWEDEN
Lines: 238

[e-mail] (Barry Margolin) writes:

>In article <[e-mail]> [e-mail] (Niklas Hallqvist) writes:
>>When you want to do a doubly linked list to the cost of a singly
>>linked one (i.e. in mem. space).  Instead of having two pointers
>>for the link in each node, take the "previous" and "next" pointers
>>and XOR them, and store the result!

>Problems:

>1) XOR isn't defined for pointers in C/C++.

True!

>2) You could cast the pointers to suitably large integers and XOR those,
>but the result of casting the integers back into pointers is
>implementation-dependent or undefined (I don't remember which, but either
>way it's not portable).

Well, read the ARM 5.4:

    A pointer converted to an integer of sufficient size (if any such
    exists on the implementation) and back to the same pointer type
    WILL have its original value; mappings between pointers and integers
    are OTHERWISE implementation dependent.

Emphasises mine!  This means the trick WILL be portable to all platforms
where there exists an integral type large enough (ie. almost all platforms).
I agree that this may be a bad habit, BUT... what I wanted to tell was:
It's REAL HARD (read: impossible) to implement GC on most architectures if
this rule is left in.

>3) It's only useful if you always traverse the list from one end or the
>other, since you need to know what to XOR each combined pointer with in
>order to get one of the original pointers.  But one of the main reasons for
>using a doubly-linked list is so that you can start with any entry in the
>list and get to the rest.

Often you don't start with the entry, but rather a pointer to the entry.
In C++ you can make smart-pointers, no big deal...

>3a) In particular, how would you do a circular doubly-linked list with this
>scheme?  When it starts out, the node's previous and next pointers would
>both be the same (they point to itself) and the result of the XOR would be
>0.  But that's also the result when the circular list has two elements,
>since the previous and next nodes would always be the "other" node.

You confused me here... I just had to go home to my Amiga and implement the
thing (quick and dirty, I admit) to see why it works.  Of course, it's a
smart-pointer keeping the contextual information needed.  Look for yourself,
the code has been compiled with GCC (version >= 2.1):

Niklas

#include <iostream.h>
#include <stdlib.h>
#include <assert.h>

template <class Int, class Elem>
class Node {
  Int x;
  Elem e;
public:
  Node(Elem el) : e(el), x(0) { assert(sizeof(Int) >= sizeof(Node*)); }
  Node* link(Node* n) const { return (Node*)(x ^ (Int)n); }
  void link(Node* l, Node* r) { x = (Int)l ^ (Int)r; }
  void relink(Node* o, Node* n) { x ^= (Int)o ^ (Int)n; }
  Elem elem() const { return e; }
};

template <class Int, class Elem>
class Ptr {
  Node<Int, Elem>* p;
  Node<Int, Elem>* r;
public:
  Ptr() : p(0), r(0) {}
  Ptr(const Ptr& ptr) : p(ptr.p), r(ptr.r) {}
  Ptr(Node<Int, Elem>* n) : p(n), r(0) {}
  Ptr operator=(const Ptr& ptr) { p = ptr.p; r = ptr.r; return *this; }
  Ptr operator=(Node<Int, Elem>* n) { p = n; r = 0; return *this; }
  int operator==(const Ptr& ptr) { return p == ptr.p; }
  int operator!=(const Ptr& ptr) { return p != ptr.p; }
  Node<Int, Elem>* operator->() const { return p; }
  Node<Int, Elem>& operator*() const { return *p; }
  Ptr operator++()
    { Node<Int, Elem>* n = p; p = r; r = p->link(n); return *this; }
  Ptr operator--()
    { Node<Int, Elem>* n = r; r = p; p = r->link(n); return *this; }
  int operator!() const { return !p; }
  operator Node<Int, Elem>*() const { return p; }
  void next(Node<Int, Elem>* n) { r = n; }
};

template <class Int, class Elem>
class List {
  Ptr<Int, Elem> p;
public:
  void prepend(Elem);
  void append(Elem);
  Ptr<Int, Elem> head() const { return p; }
  Ptr<Int, Elem> tail() const
    { if (p) { Ptr<Int, Elem> ptr(p); return --ptr; } else return 0; }
};

template <class Int, class Elem>
void List<Int, Elem>::prepend(Elem e)
{
  Node<Int, Elem>* n = new Node<Int, Elem>(e);
  Ptr<Int, Elem> old = p;
  p = n;
  if (old)
    {
      Ptr<Int, Elem> prev = old;
      --prev;
      p->link(prev, old);
      p.next(old);
      prev.next(p);
      prev->relink(old, p);
      old->relink(prev, p);
    }
  else
    p.next(p);
}

template <class Int, class Elem>
void List<Int, Elem>::append(Elem e)
{
  Ptr<Int, Elem> n = new Node<Int, Elem>(e);
  if (p)
    {
      Ptr<Int, Elem> prev = p;
      --prev;
      n->link(prev, p);
      n.next(p);
      prev.next(n);
      prev->relink(p, n);
      p->relink(prev, n);
    }
  else
    {
      p = n;
      p.next(p);
    }
}

template <class Int, class Elem>
void print_forward(ostream& os, const List<Int, Elem>& l)
{
  os << "[ ";
  Ptr<Int, Elem> p = l.head();
  if (p)
    while (1)
      {
    os << p->elem();
    if (++p == l.head())
      break;
    os << ", ";
      }
  os << " ]" << endl;
}

template <class Int, class Elem>
void print_backward(ostream& os, const List<Int, Elem>& l)
{
  os << "[ ";
  Ptr<Int, Elem> p = l.tail();
  if (p)
    while (1)
      {
    os << p->elem();
    if (--p == l.tail())
      break;
    os << ", ";
      }
  os << " ]" << endl;
}

template <class Int, class Elem>
void print_funny(ostream& os, const List<Int, Elem>& l)
{
  int forward = 1;
  os << "[ ";
  Ptr<Int, Elem> p = l.tail();
  if (p)
    while (1)
      {
    os << p->elem();
    if (forward)
      ++p;
    else
      {
        --p;
        --p;
        --p;
      }
    forward = !forward;
    if (p == l.tail())
      break;
    os << ", ";
      }
  os << " ]" << endl;
}

template<class Int, class Elem>
inline void print(ostream& os, const List<Int, Elem>& l)
{
  print_forward(os, l);
  print_backward(os, l);
  print_funny(os, l);
}

int main()
{
  List<int, int> l;
  print(cout, l);
  l.prepend(4);
  print(cout, l);
  l.prepend(3);
  print(cout, l);
  l.prepend(2);
  print(cout, l);
  l.prepend(1);
  print(cout, l);
  l.append(5);
  print(cout, l);
  l.append(6);
  print(cout, l);
  l.append(7);
  print(cout, l);
  l.append(8);
  print(cout, l);
  return 0;
}
--
Niklas Hallqvist    Phone: [phone]
Applitron Datasystem    Fax:   [phone]
Molndalsvagen 95    Email: [e-mail]
S-412 63  GOTEBORG, Sweden     mcsun!seunet!appli!niklas