diff options
author | Con Kolivas <kernel@kolivas.org> | 2016-10-21 22:18:35 +1100 |
---|---|---|
committer | Con Kolivas <kernel@kolivas.org> | 2016-10-22 09:53:12 +1100 |
commit | 04bbfdc3164a52ae35bd0b7572a67689de2a8a62 (patch) | |
tree | 85748bb7d135c06e0ab21f725f12d4566d795b3b /kernel | |
parent | 6b45f1f363d7f6959b648cf49252f378022d11c6 (diff) |
Optimise randomlevel in skip list to be simple ffb and rarer for higher levels
Diffstat (limited to 'kernel')
-rw-r--r-- | kernel/skip_list.c | 34 |
1 files changed, 4 insertions, 30 deletions
diff --git a/kernel/skip_list.c b/kernel/skip_list.c index 5c66067f2899..d5250805672d 100644 --- a/kernel/skip_list.c +++ b/kernel/skip_list.c @@ -93,34 +93,9 @@ void skiplist_node_init(skiplist_node *node) memset(node, 0, sizeof(skiplist_node)); } -/* - * Returns a pseudo-random number based on the randseed value by masking out - * 0-15. As many levels are not required when only few values are on the list, - * we limit the height of the levels according to how many list entries there - * are in a cheap manner. The height of the levels may have been higher while - * there were more entries queued previously but as this code is used only by - * the scheduler, entries are short lived and will be torn down regularly. - * - * 00-03 entries - 1 level - * 04-07 entries - 2 levels - * 08-15 entries - 4 levels - * 15-31 entries - 7 levels - * 32+ entries - max(16) levels - */ -static inline unsigned int randomLevel(int entries, unsigned int randseed) +static inline unsigned int randomLevel(const long unsigned int randseed) { - unsigned int mask; - - if (entries > 15) - mask = 0x7; - else if (entries > 7) - mask = 0x3; - else if (entries > 3) - mask = 0x1; - else - return 0; - - return randseed & mask; + return find_first_bit(&randseed, MaxLevel); } void skiplist_insert(skiplist *l, skiplist_node *node, keyType key, valueType value, unsigned int randseed) @@ -136,9 +111,8 @@ void skiplist_insert(skiplist *l, skiplist_node *node, keyType key, valueType va update[k] = p; } while (--k >= 0); - k = randomLevel(++l->entries, randseed); - if (k > MaxLevel) - k = MaxLevel; + ++l->entries; + k = randomLevel(randseed); if (k > l->level) { k = ++l->level; update[k] = l->header; |