Re: ltable.c table deletion

[Doug Currie <doug.currie@...>]

On Feb 1, 2012, at 5:03 PM, Josh Haberman wrote:

> - this technique of avoiding coalescing is known, but not well-known.
>   Knuth attributes it to Ferguson and doesn't mention Brent, and to
>   my eye Brent's paper [0] is talking about an improvement to open
>   addressing, not chained scatter.

Yes, this is why I was harping on the next field. BTW, sorry about missing the significance of your initial reference to "chained scatter." I'm much more familiar with open addressing, and talk of Brent's variation also implies open addressing to me. Here's one way to look at four variations of hash table design:

   open addressing  --------->  Brent's variation
          |                             |
          |                             |
          |                             |
          |     (add next links)        |
          |                             |
          v                             v
    chained scatter   ----->  Ferguson's variation

where the arrows pointing down add next links to hash buckets, and arrows to the right add Brent/Ferguson insertion optimization to decrease probe count (and as you point out, deletion complexity). 

We were talking past each other initially because I was traveling across the top of the diagram and then down ("add next links so chains never coalesce at the expense of one link pointer per hash bucket"), whereas you were starting in the lower left and describing the optimization across the bottom of the diagram.

Thank you for your patient and careful explanation of this not well-known technique of avoiding coalescing.

-- e