Kernel Skip List

I have developed a skip list implementation for Windows kernel. The
algorithm is based on William Pugh’s original paper with some optimizations
I made for performance. References in code.

The code has been implemented to follow the RtlGenericTabel model as close
as possible. To test it, I simply dropped it into some existing code. The
performance is O(log n). In some areas, AVL trees perform a little better,
but the difference is nominal. The advantage is faster inserts and deletes,
less memory than AVL/Splay, and a far, far less complicated algorithm.

There are about five more functions that could be implemented to round out
parity with the full RtlGenericTable interfaces, but this is complete
enough to use.

The code has been put into the public domain for free use by anyone.

Get the source via:

git clone https://github.com/jameykirby/public.git

Comments, suggestions, and updates welcomed.


Jamey Kirby
Disrupting the establishment since 1964

*This is a personal email account and as such, emails are not subject to
archiving. Nothing else really matters.*

That’s pretty cool Jamey.

-p

From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Jamey Kirby
Sent: Tuesday, June 30, 2015 9:39 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Kernel Skip List

I have developed a skip list implementation for Windows kernel. The algorithm is based on William Pugh’s original paper with some optimizations I made for performance. References in code.

The code has been implemented to follow the RtlGenericTabel model as close as possible. To test it, I simply dropped it into some existing code. The performance is O(log n). In some areas, AVL trees perform a little better, but the difference is nominal. The advantage is faster inserts and deletes, less memory than AVL/Splay, and a far, far less complicated algorithm.

There are about five more functions that could be implemented to round out parity with the full RtlGenericTable interfaces, but this is complete enough to use.

The code has been put into the public domain for free use by anyone.

Get the source via:

git clone https://github.com/jameykirby/public.git

Comments, suggestions, and updates welcomed.


Jamey Kirby
Disrupting the establishment since 1964

This is a personal email account and as such, emails are not subject to archiving. Nothing else really matters.
[https://mailfoogae.appspot.com/t?sender=aa2lyYnkuamFtZXlAZ21haWwuY29t&type=zerocontent&guid=3577507b-9a22-45fe-a914-b21196828f8c]ᐧ
— NTDEV is sponsored by OSR Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev OSR is HIRING!! See http://www.osr.com/careers For our schedule of WDF, WDM, debugging and other seminars visit: http://www.osr.com/seminars To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer