Re: Red-black tree for GIN

On Mon, Jan 11, 2010 at 1:18 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> 2010/1/11 Teodor Sigaev <teodor(at)sigaev(dot)ru>:
>> knngist uses that implementation of rb-tree. One more candidate is a ts_stat
>> which now uses unbalanced binary tree.
>
> Ah, OK.  That's great if we can reuse that code in 2 or 3 places.

Some preliminary thoughts on this patch:

1. I think rb_free_recursive is missing a pfree().

2. We already have a definition of NIL in the PG source base. I think
this one needs to be named something else. RBNIL, maybe.

3. This code could really use some more comments, and maybe some of
the variable names could be better chosen, too. It's far from obvious
what is going on here. I studied rbtrees in college and I still
remember more or less how they work, but, boy, this is hard to follow.
The names of the iterator states are truly horrible, at least IMO.

4. It would be nice if you could do a better job conforming to project
indentation style.

...Robert