Messages in this thread |  | | | Date | Thu, 3 Jun 2010 15:55:52 +0200 | | From | Florian Mickler <> | | Subject | Re: [linux-pm] [PATCH 0/8] Suspend block api (version 8) |
| |
On Thu, 3 Jun 2010 00:10:03 -0700 Arve Hjønnevåg <arve@android.com> wrote:
> On Wed, Jun 2, 2010 at 10:40 PM, mark gross <640e9920@gmail.com> wrote:
> > well I think for a pm_qos class that has boolean dynamic range we can > > get away with not walking the list on every request update. we can use > > a counter, and the list will be for mostly for stats. > > > > Did you give any thought to my suggestion to only use one entry per > unique value on the first level list and then use secondary lists of > identical values. That way if you only have two constraints values the > list you have to walk when updating a request will never have more > than two entries regardless of how many total request you have. > > 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 >
Yes. I think that would be good. If we keep the primary list sorted, then this becomes a nice priority queue implementation which does GetMax in constant time and Insert and Delete in logarithmic complexity to the number of different values.
Cheers, Flo -- 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/
|  |