Re: Double linked list with one pointer

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Gaetano Mendola <mendola(at)bigfoot(dot)com>
Cc: "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Double linked list with one pointer
Date: 2003-12-06 18:44:03
Message-ID: 14355.1070736243@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Gaetano Mendola <mendola(at)bigfoot(dot)com> writes:
> If I'm not wrong Neil Conway is working on
> reimplement a double linked list.

No, he's working on keeping track of the list tail element (and length,
but the tail element is the important part). There was nothing about
double linking.

> In particular, a motivation behind two-way pointers is that you
> can have a more space-efficient doubly linked list if you store only one
> (not two) pointer's worth of storage in each node. But how can the list
> still be traversable in both directions? The idea is that each node
> stores, not a pointer to one other node, but a pointer to the previous
> node XOR'd with a pointer to the next node.

This is way too weird for my taste. We do not need two-way list
traversal in 99.9% of the backend code (note the near complete lack of
use of Dllist). Also, the described scheme is slower to traverse than a
standard list since you have to remember two words of state (prev and
cur pointer not just cur) to traverse the list; that bookkeeping, plus
the cost of the XOR itself, adds up. Another cost that would be
significant from my point of view is loss of readability of list
structures in the debugger. I don't want to pay that cost to buy a
feature we don't need.

regards, tom lane

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2003-12-06 19:09:25 IDENT and IPv6 (was Re: [GENERAL] pg_hba.conf change in 7.4)
Previous Message Tom Lane 2003-12-06 18:30:54 Re: Postgres 7.3.5 and count('x')