Re: [RFC] Lock free fd lookup

[William Lee Irwin III]

On Fri, 16 Jul 2004 18:19:36 -0700, William Lee Irwin III wrote:
>> This actually appears to confirm my earlier assertion about the linkage
>> of the data structure. Is this conclusion what you had in mind?

On Sat, Jul 17, 2004 at 12:12:39PM +1000, Keith Owens wrote:
> Not quite.  The 2-3-4 tree has embedded linkage, but it can be done
> lockfree if you really have to.  The problem is that a single 2-3-4
> list entry maps to two red-black list entries.  I could atomically
> update a single 2-3-4 list entry, including its pointers, even when the
> list was being read or updated by other users.  I could not work out
> how to do the equivalent update when the list linkage data was split
> over two red-black nodes.

2-3 trees have external linkage just like B/B+ trees as I had
envisioned what external linkage is. Terminological issue I guess.


On Sat, Jul 17, 2004 at 12:12:39PM +1000, Keith Owens wrote:
> The list structure is an implementation detail, the use of 2-3-4 or
> red-black is completely transparent to the main code.  The main code
> wants to lookup a structure from the list, to update a structure, to
> insert or to delete a structure without waiting.  How the list of
> structures is maintained is a problem for the internals of the API.

That kind of genericity is tough to come by in C. I guess callbacks and
void * can do it when pressed.


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