Re: [PATCH 0/8] Suspend block api (version 8)

On Thu, 3 Jun 2010 21:07:07 -0700
Arve Hjønnevåg [off-list ref] wrote:

On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki [off-list ref] wrote:

quoted

On Thursday 03 June 2010, James Bottomley wrote:

quoted

On Thu, 2010-06-03 at 00:10 -0700, Arve Hjønnevåg wrote:

quoted

A request update then becomes something like this:
  if on primary list {
    unlink from primary list
    if secondary list is not empty
      get next secondary entry and add in same spot on primary list
  }
  unlink from secondary list
  find new spot on primary list
  if already there
    add to secondary list
  else
    add to primary list

This is just reinventing hash bucketed lists.  To get the benefits, all
we do is implement an N state constraint as backed by an N bucketed hash
list, which the kernel already has all the internal mechanics for.

Agreed.

No, a hash is used for quick lookup of a specific value, not to find
an extreme value. It is however extremely similar to plists. The only
difference is that plists link all the secondary lists together. If we
want to have constraints that autoexpire, then keeping the secondary
lists separate allows the same optimization as I did for
wakelock/suspend_blocker timeouts where no timer is active if an
(equal or stricter) non-expiring constraint is active.

Can you give an example for the optimization or elaborate about the
negative effect of linking the secondary lists together? I don't
understand right now.

Would be hlist from list.h better? (I think that is what James is
referring to?) That is a (single-linked-)list of double-linked-lists. 

Cheers,
Flo