[SKIPLIST]

The Park-Miller Lehmer Random Number Generator only outputs 31 uniformly distributed random bits. Bit 32 is always zero.
Fix the code accordingly.

This limits the maximum number of Skiplist levels to 31, but we only use 16 anyway so far.

svn path=/branches/colins-printing-for-freedom/; revision=68991

diff --git a/reactos/lib/skiplist/skiplist.c b/reactos/lib/skiplist/skiplist.c
index b4d7fd2..b1764df 100644 (file)
--- a/reactos/lib/skiplist/skiplist.c
+++ b/reactos/lib/skiplist/skiplist.c
@@ -28,11 +28,11 @@ _GetRandomLevel()
     DWORD dwLevel = 0;
     DWORD dwShifted;
 
-    // Generate 32 uniformly distributed pseudo-random bits using the Park-Miller Lehmer Minimal Standard Random Number Generator.
+    // Generate 31 uniformly distributed pseudo-random bits using the Park-Miller Lehmer Minimal Standard Random Number Generator.
     dwRandom = (DWORD)(((ULONGLONG)dwRandom * 48271UL) % 2147483647UL);
 
-    // Shift out (32 - SKIPLIST_LEVELS) bits to the right to have no more than SKIPLIST_LEVELS bits set.
-    dwShifted = dwRandom >> (32 - SKIPLIST_LEVELS);
+    // Shift out (31 - SKIPLIST_LEVELS) bits to the right to have no more than SKIPLIST_LEVELS bits set.
+    dwShifted = dwRandom >> (31 - SKIPLIST_LEVELS);
 
     // BitScanForward doesn't operate on a zero input value.
     if (dwShifted)
@@ -42,7 +42,7 @@ _GetRandomLevel()
         BitScanForward(&dwLevel, dwShifted);
     }
 
-    // dwLevel can't have a value higher than 31 this way, so a CHAR is more than enough.
+    // dwLevel can't have a value higher than 30 this way, so a CHAR is more than enough.
     return (CHAR)dwLevel;
 }
 

diff --git a/reactos/lib/skiplist/skiplist.h b/reactos/lib/skiplist/skiplist.h
index 6fb4761..1bdd118 100644 (file)
--- a/reactos/lib/skiplist/skiplist.h
+++ b/reactos/lib/skiplist/skiplist.h
@@ -8,15 +8,15 @@
 #ifndef _REACTOS_SKIPLIST_H
 #define _REACTOS_SKIPLIST_H
 
-// Define SKIPLIST_LEVELS to a value between 1 and 32 before including this header.
+// Define SKIPLIST_LEVELS to a value between 1 and 31 before including this header.
 // This specifies the maximum number of levels you want your Skiplist to have.
 // A value of X is recommended for handling up to 2^X elements.
 #ifndef SKIPLIST_LEVELS
-#error Please define SKIPLIST_LEVELS to a value between 1 and 32.
+#error Please define SKIPLIST_LEVELS to a value between 1 and 31.
 #endif
 
 C_ASSERT(SKIPLIST_LEVELS >= 1);
-C_ASSERT(SKIPLIST_LEVELS <= 32);
+C_ASSERT(SKIPLIST_LEVELS <= 31);
 
 // Function pointer definitions
 typedef PVOID (WINAPI *PSKIPLIST_ALLOCATE_ROUTINE)(DWORD);