lkml.org 
[lkml]   [2004]   [Oct]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: single linked list header in kernel?
On Wed, 13 Oct 2004 23:18:10 -0500, Kevin Puetz <puetzk@puetzk.org> wrote:
>
>
> Tonnerre wrote:
>
> > Salut,
> >
> > On Wed, Oct 13, 2004 at 08:25:43PM +0200, Matthias Urlichs wrote:
> >> I dunno, though -- open-coding a singly-linked list isn't that much of a
> >> problem; compared to a doubly-linked one, there's simply fewer things
> >> that can go horribly wrong. :-/
> >
> > The problem is that
> >
> > 1. you have to use circular lists
> >
> > 2. going forward is O(1), going backward is O(N). This doesn't sound
> > like a problem, but deleting from lists and alike requires you to
> > go back in the list.
> >
> > I guess that if you have lists that you edit a lot, double linked
> > lists should be less overhead. However, if you only walk the lists a
> > lot, both models should perform equally well.
> >
> > Insertion is faster, but that's the only good news..
> >
> > I'm all against them, though. ;)
> >
> > Tonnerre
>
> And of course there's the ever-infamous 'two-half-linked list' (for want of
> a better name). If you really need O(1) access in both directions but the
> constant factor isn't terribly important, it *is* (surprisingly) possible
> to achieve this without any size overhead in the list elements, though the
> code and iterator sizes will be a little higher and the "number of things
> that can go horribly wrong will swell impressively".
>
> Read on only if you a) already know what I have in mind, but want to tell my
> I described it wrong or b) genuinely enjoy disgustingly clever trickery, or
> c) the previous, plus have some specific need to make an uncorrupted
> programmer's head explode. Do NOT read on if you are intending to implement
> what I describe, unless you have a damned good reason not to use a sane
> doubly-linked list :-)
>
> What you do is take advantage of the fact that when iterating, it's usually
> pretty straightforward to make your 'iterator' keep track of of the
> previous node as the current one. Then, instead of storing a 'next' pointer
> or a 'previous' pointer in the node, you store the two XORed together (or
> choose your favorite mixing function, there are many viable choices). Then,
> when you are at a node, you can recover the pointer for whichever direction
> you are travelling in by XORing the mix from the node with your stored
> 'previous' pointer, thus giving you whichever neighbor you didn't already
> know. Then you can move to the next node (prev=current, current=neighbor)
> and do it again. Or just swap prev and current if you want to go the other
> direction.
>
> So, you end up with:
> O(1) forward and reverse iteration
> only 1 pointer of overhead per node
>
> but, you pay for it with:
> 2 pointers of size for a moveable iterator pointing to a node
> an extra fetch (though probably still in a register if you're in a tight
> loop) and an XOR for every step along the chain.
>
>
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>

Some links for the intrigued ones:

http://www.google.com/search?q=xor+linked+list

http://www.fact-index.com/x/xo/xor_linked_list.html

http://www.greatsnakes.com/savannah/xlist.asp

--
Greetz, Antonio Vargas
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:07    [W:0.028 / U:10.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site