ReactOS  0.4.15-dev-3187-ge372f2b
skiplist.c File Reference
#include <intrin.h>
#include <windef.h>
#include <winbase.h>
#include "skiplist.h"
Include dependency graph for skiplist.c:

Go to the source code of this file.

Functions

_GetRandomLevel

Returns a random level for the next element to be inserted. This level is geometrically distributed for p = 0.5, so perfectly suitable for an efficient Skiplist implementation.

Returns
A value between 0 and SKIPLIST_LEVELS - 1.
static __inline CHAR _GetRandomLevel ()
 
_InsertElementSkiplistWithInformation

Determines a level for the new element and inserts it at the given position in the Skiplist. This function is internally used by the Skiplist insertion functions.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
ElementThe element to insert.
pUpdateArray containing the last nodes before our new node on each level.
dwDistanceArray containing the distance to the last node before our new node on each level.
Returns
TRUE if the node was successfully inserted, FALSE if no memory could be allocated for it.
static BOOL _InsertElementSkiplistWithInformation (PSKIPLIST Skiplist, PVOID Element, PSKIPLIST_NODE *pUpdate, DWORD *dwDistance)
 
DeleteElementSkiplist

Deletes an element from the Skiplist. The efficiency of this operation is O(log N) on average.

Instead of the result of a LookupElementSkiplist call, it's sufficient to provide a dummy element with just enough information for your CompareRoutine. A lookup for the element to be deleted needs to be performed in any case.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
ElementInformation about the element to be deleted.
Returns
Returns the deleted element or NULL if no such element was found. You can then free memory for the deleted element if necessary.
PVOID DeleteElementSkiplist (PSKIPLIST Skiplist, PVOID Element)
 
InitializeSkiplist

Initializes a new Skiplist structure.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
AllocateRoutinePointer to a SKIPLIST_ALLOCATE_ROUTINE for allocating memory for new Skiplist nodes.
CompareRoutinePointer to a SKIPLIST_COMPARE_ROUTINE for comparing two elements of the Skiplist.
FreeRoutinePointer to a SKIPLIST_FREE_ROUTINE for freeing memory allocated with AllocateRoutine.
void InitializeSkiplist (PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
 
InsertElementSkiplist

Inserts a new element into the Skiplist. The efficiency of this operation is O(log N) on average. Uses CompareRoutine to find the right position for the insertion.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
ElementThe element to insert.
Returns
TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
BOOL InsertElementSkiplist (PSKIPLIST Skiplist, PVOID Element)
 
InsertTailElementSkiplist

Inserts a new element at the end of the Skiplist. The efficiency of this operation is O(log N) on average. In contrast to InsertElementSkiplist, this function is more efficient by not calling CompareRoutine at all and always inserting the element at the end. You're responsible for calling this function only when you can guarantee that InsertElementSkiplist would also insert the element at the end.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
ElementThe element to insert.
Returns
TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
BOOL InsertTailElementSkiplist (PSKIPLIST Skiplist, PVOID Element)
 
LookupElementSkiplist

Looks up an element in the Skiplist. The efficiency of this operation is O(log N) on average.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
ElementInformation about the element to look for.
ElementIndexPointer to a DWORD that will contain the zero-based index of the element in the Skiplist. If you're not interested in the index, you can set this parameter to NULL.
Returns
Returns the found element or NULL if no such element was found.
PVOID LookupElementSkiplist (PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
 
LookupNodeByIndexSkiplist

Looks up a node in the Skiplist at the given position. The efficiency of this operation is O(log N) on average.

Parameters
SkiplistPointer to the SKIPLIST structure to operate on.
ElementIndexZero-based position of the node in the Skiplist.
Returns
Returns the found node or NULL if the position is invalid.
PSKIPLIST_NODE LookupNodeByIndexSkiplist (PSKIPLIST Skiplist, DWORD ElementIndex)
 

Function Documentation

◆ _GetRandomLevel()

static __inline CHAR _GetRandomLevel ( )
static

Definition at line 23 of file skiplist.c.

24 {
25  // Using a simple fixed seed and the Park-Miller Lehmer Minimal Standard Random Number Generator gives an acceptable distribution for our "random" levels.
26  static DWORD dwRandom = 1;
27 
28  DWORD dwLevel = 0;
29  DWORD dwShifted;
30 
31  // Generate 31 uniformly distributed pseudo-random bits using the Park-Miller Lehmer Minimal Standard Random Number Generator.
32  dwRandom = (DWORD)(((ULONGLONG)dwRandom * 48271UL) % 2147483647UL);
33 
34  // Shift out (31 - SKIPLIST_LEVELS) bits to the right to have no more than SKIPLIST_LEVELS bits set.
35  dwShifted = dwRandom >> (31 - SKIPLIST_LEVELS);
36 
37  // BitScanForward doesn't operate on a zero input value.
38  if (dwShifted)
39  {
40  // BitScanForward sets dwLevel to the zero-based position of the first set bit (from LSB to MSB).
41  // This makes dwLevel a geometrically distributed value between 0 and SKIPLIST_LEVELS - 1 for p = 0.5.
42  BitScanForward(&dwLevel, dwShifted);
43  }
44 
45  // dwLevel can't have a value higher than 30 this way, so a CHAR is more than enough.
46  return (CHAR)dwLevel;
47 }
#define SKIPLIST_LEVELS
Definition: precomp.h:30
#define BitScanForward
Definition: interlocked.h:5
char CHAR
Definition: xmlstorage.h:175
#define DWORD
Definition: nt_native.h:44
uint64_t ULONGLONG
Definition: typedefs.h:67
unsigned long DWORD
Definition: ntddk_ex.h:95
#define UL
Definition: tui.h:82

Referenced by _InsertElementSkiplistWithInformation().

◆ _InsertElementSkiplistWithInformation()

static BOOL _InsertElementSkiplistWithInformation ( PSKIPLIST  Skiplist,
PVOID  Element,
PSKIPLIST_NODE pUpdate,
DWORD dwDistance 
)
static

Definition at line 71 of file skiplist.c.

72 {
73  CHAR chNewLevel;
74  CHAR i;
75  PSKIPLIST_NODE pNode;
76 
77  // Get the highest level, on which the node shall be inserted.
78  chNewLevel = _GetRandomLevel();
79 
80  // Check if the new level is higher than the maximum level we currently have in the Skiplist.
81  if (chNewLevel > Skiplist->MaximumLevel)
82  {
83  // It is, so we also need to insert the new node right after the Head node on some levels.
84  // These are the levels higher than the current maximum level up to the new level.
85  // We also need to set the distance of these elements to the new node count to account for the calculations below.
86  for (i = Skiplist->MaximumLevel + 1; i <= chNewLevel; i++)
87  {
88  pUpdate[i] = &Skiplist->Head;
89  pUpdate[i]->Distance[i] = Skiplist->NodeCount + 1;
90  }
91 
92  // The new level is the new maximum level of the entire Skiplist.
93  Skiplist->MaximumLevel = chNewLevel;
94  }
95 
96  // Finally create our new Skiplist node.
97  pNode = Skiplist->AllocateRoutine(sizeof(SKIPLIST_NODE));
98  if (!pNode)
99  return FALSE;
100 
101  pNode->Element = Element;
102 
103  // For each used level, insert us between the saved node for this level and its current next node.
104  for (i = 0; i <= chNewLevel; i++)
105  {
106  pNode->Next[i] = pUpdate[i]->Next[i];
107  pUpdate[i]->Next[i] = pNode;
108 
109  // We know the walked distance in this level: dwDistance[i]
110  // We also know the element index of the new node: dwDistance[0]
111  // The new node's distance is now the walked distance in this level plus the difference between the saved node's distance and the element index.
112  pNode->Distance[i] = dwDistance[i] + (pUpdate[i]->Distance[i] - dwDistance[0]);
113 
114  // The saved node's distance is now the element index plus one (to account for the added node) minus the walked distance in this level.
115  pUpdate[i]->Distance[i] = dwDistance[0] + 1 - dwDistance[i];
116  }
117 
118  // For all levels above the new node's level, we need to increment the distance, because we've just added our new node.
119  for (i = chNewLevel + 1; i <= Skiplist->MaximumLevel; i++)
120  ++pUpdate[i]->Distance[i];
121 
122  // We've successfully added a node :)
123  ++Skiplist->NodeCount;
124  return TRUE;
125 }
DWORD NodeCount
Definition: skiplist.h:39
PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine
Definition: skiplist.h:40
#define TRUE
Definition: types.h:120
SKIPLIST_NODE Head
Definition: skiplist.h:37
char CHAR
Definition: xmlstorage.h:175
CHAR MaximumLevel
Definition: skiplist.h:38
#define FALSE
Definition: types.h:117
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
static __inline CHAR _GetRandomLevel()
Definition: skiplist.c:23
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
PVOID Element
Definition: skiplist.h:31

Referenced by InsertElementSkiplist(), and InsertTailElementSkiplist().

◆ DeleteElementSkiplist()

PVOID DeleteElementSkiplist ( PSKIPLIST  Skiplist,
PVOID  Element 
)

Definition at line 146 of file skiplist.c.

147 {
148  CHAR i;
149  PSKIPLIST_NODE pLastComparedNode = NULL;
150  PSKIPLIST_NODE pNode = &Skiplist->Head;
152  PVOID pReturnValue;
153 
154  // Find the node on every currently used level, after which the node to be deleted must follow.
155  // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
156  for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
157  {
158  while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
159  pNode = pNode->Next[i];
160 
161  // Reduce the number of comparisons by not comparing the same node on different levels twice.
162  pLastComparedNode = pNode->Next[i];
163  pUpdate[i] = pNode;
164  }
165 
166  // Check if the node we're looking for has been found.
167  pNode = pNode->Next[0];
168  if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
169  {
170  // It hasn't been found, so there's nothing to delete.
171  return NULL;
172  }
173 
174  // Beginning at the lowest level, remove the node from each level of the list and merge distances.
175  // We can stop as soon as we found the first level that doesn't contain the node.
176  for (i = 0; i <= Skiplist->MaximumLevel && pUpdate[i]->Next[i] == pNode; i++)
177  {
178  pUpdate[i]->Distance[i] += pNode->Distance[i] - 1;
179  pUpdate[i]->Next[i] = pNode->Next[i];
180  }
181 
182  // Now decrement the distance of the corresponding node in levels higher than the deleted node's level to account for the deleted node.
183  while (i <= Skiplist->MaximumLevel)
184  {
185  --pUpdate[i]->Distance[i];
186  i++;
187  }
188 
189  // Return the deleted element (so the caller can free it if necessary) and free the memory for the node itself (allocated by us).
190  pReturnValue = pNode->Element;
191  Skiplist->FreeRoutine(pNode);
192 
193  // Find all levels which now contain no more nodes and reduce the maximum level of the entire Skiplist accordingly.
194  while (Skiplist->MaximumLevel > 0 && !Skiplist->Head.Next[Skiplist->MaximumLevel])
195  --Skiplist->MaximumLevel;
196 
197  // We've successfully deleted the node :)
198  --Skiplist->NodeCount;
199  return pReturnValue;
200 }
#define SKIPLIST_LEVELS
Definition: precomp.h:30
DWORD NodeCount
Definition: skiplist.h:39
SKIPLIST_NODE Head
Definition: skiplist.h:37
char CHAR
Definition: xmlstorage.h:175
CHAR MaximumLevel
Definition: skiplist.h:38
PSKIPLIST_COMPARE_ROUTINE CompareRoutine
Definition: skiplist.h:41
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define NULL
Definition: types.h:112
PVOID Element
Definition: skiplist.h:31
PSKIPLIST_FREE_ROUTINE FreeRoutine
Definition: skiplist.h:42

Referenced by _LocalSetJobLevel1(), _LocalSetJobLevel2(), FreeJob(), and main().

◆ InitializeSkiplist()

void InitializeSkiplist ( PSKIPLIST  Skiplist,
PSKIPLIST_ALLOCATE_ROUTINE  AllocateRoutine,
PSKIPLIST_COMPARE_ROUTINE  CompareRoutine,
PSKIPLIST_FREE_ROUTINE  FreeRoutine 
)

Definition at line 220 of file skiplist.c.

221 {
222  // Store the routines.
223  Skiplist->AllocateRoutine = AllocateRoutine;
224  Skiplist->CompareRoutine = CompareRoutine;
225  Skiplist->FreeRoutine = FreeRoutine;
226 
227  // Initialize the members and pointers.
228  // The Distance array is only used when a node is non-NULL, so it doesn't need initialization.
229  Skiplist->MaximumLevel = 0;
230  Skiplist->NodeCount = 0;
231  ZeroMemory(Skiplist->Head.Next, sizeof(Skiplist->Head.Next));
232 }
DWORD NodeCount
Definition: skiplist.h:39
PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine
Definition: skiplist.h:40
SKIPLIST_NODE Head
Definition: skiplist.h:37
CHAR MaximumLevel
Definition: skiplist.h:38
#define ZeroMemory
Definition: winbase.h:1664
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1088
PSKIPLIST_COMPARE_ROUTINE CompareRoutine
Definition: skiplist.h:41
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1088
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1088
PSKIPLIST_FREE_ROUTINE FreeRoutine
Definition: skiplist.h:42

Referenced by InitializeGlobalJobList(), InitializePrinterJobList(), InitializePrinterList(), and main().

◆ InsertElementSkiplist()

BOOL InsertElementSkiplist ( PSKIPLIST  Skiplist,
PVOID  Element 
)

Definition at line 250 of file skiplist.c.

251 {
252  CHAR i;
253  DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
254  PSKIPLIST_NODE pLastComparedNode = NULL;
255  PSKIPLIST_NODE pNode = &Skiplist->Head;
257 
258  // Find the node on every currently used level, after which the new node needs to be inserted.
259  // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
260  for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
261  {
262  // When entering this level, we begin at the distance of the last level we walked through.
263  dwDistance[i] = dwDistance[i + 1];
264 
265  while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
266  {
267  // Save our position in every level when walking through the nodes.
268  dwDistance[i] += pNode->Distance[i];
269 
270  // Advance to the next node.
271  pNode = pNode->Next[i];
272  }
273 
274  // Reduce the number of comparisons by not comparing the same node on different levels twice.
275  pLastComparedNode = pNode->Next[i];
276  pUpdate[i] = pNode;
277  }
278 
279  // Check if the node already exists in the Skiplist.
280  pNode = pNode->Next[0];
281  if (pNode && Skiplist->CompareRoutine(pNode->Element, Element) == 0)
282  {
283  // All elements to be inserted mustn't exist in the list, so we see this as a failure.
284  return FALSE;
285  }
286 
287  // The rest of the procedure is the same for both insertion functions.
288  return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
289 }
#define SKIPLIST_LEVELS
Definition: precomp.h:30
SKIPLIST_NODE Head
Definition: skiplist.h:37
char CHAR
Definition: xmlstorage.h:175
CHAR MaximumLevel
Definition: skiplist.h:38
static BOOL _InsertElementSkiplistWithInformation(PSKIPLIST Skiplist, PVOID Element, PSKIPLIST_NODE *pUpdate, DWORD *dwDistance)
Definition: skiplist.c:71
#define FALSE
Definition: types.h:117
PSKIPLIST_COMPARE_ROUTINE CompareRoutine
Definition: skiplist.h:41
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
unsigned long DWORD
Definition: ntddk_ex.h:95
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define NULL
Definition: types.h:112
PVOID Element
Definition: skiplist.h:31

Referenced by _LocalSetJobLevel1(), _LocalSetJobLevel2(), CreateJob(), InitializeGlobalJobList(), InitializePrinterList(), and main().

◆ InsertTailElementSkiplist()

BOOL InsertTailElementSkiplist ( PSKIPLIST  Skiplist,
PVOID  Element 
)

Definition at line 308 of file skiplist.c.

309 {
310  CHAR i;
311  DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
312  PSKIPLIST_NODE pNode = &Skiplist->Head;
314 
315  // Find the last node on every currently used level, after which the new node needs to be inserted.
316  // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
317  for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
318  {
319  // When entering this level, we begin at the distance of the last level we walked through.
320  dwDistance[i] = dwDistance[i + 1];
321 
322  while (pNode->Next[i])
323  {
324  // Save our position in every level when walking through the nodes.
325  dwDistance[i] += pNode->Distance[i];
326 
327  // Advance to the next node.
328  pNode = pNode->Next[i];
329  }
330 
331  pUpdate[i] = pNode;
332  }
333 
334  // The rest of the procedure is the same for both insertion functions.
335  return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
336 }
#define SKIPLIST_LEVELS
Definition: precomp.h:30
SKIPLIST_NODE Head
Definition: skiplist.h:37
char CHAR
Definition: xmlstorage.h:175
CHAR MaximumLevel
Definition: skiplist.h:38
static BOOL _InsertElementSkiplistWithInformation(PSKIPLIST Skiplist, PVOID Element, PSKIPLIST_NODE *pUpdate, DWORD *dwDistance)
Definition: skiplist.c:71
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
unsigned long DWORD
Definition: ntddk_ex.h:95
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248

Referenced by CreateJob().

◆ LookupElementSkiplist()

PVOID LookupElementSkiplist ( PSKIPLIST  Skiplist,
PVOID  Element,
PDWORD  ElementIndex 
)

Definition at line 357 of file skiplist.c.

358 {
359  CHAR i;
360  DWORD dwIndex = 0;
361  PSKIPLIST_NODE pLastComparedNode = NULL;
362  PSKIPLIST_NODE pNode = &Skiplist->Head;
363 
364  // Do the efficient lookup in Skiplists:
365  // * Start from the maximum level.
366  // * Walk through all nodes on this level that come before the node we're looking for.
367  // * When we have reached such a node, go down a level and continue there.
368  // * Repeat these steps till we're in level 0, right in front of the node we're looking for.
369  for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
370  {
371  while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
372  {
373  dwIndex += pNode->Distance[i];
374  pNode = pNode->Next[i];
375  }
376 
377  // Reduce the number of comparisons by not comparing the same node on different levels twice.
378  pLastComparedNode = pNode->Next[i];
379  }
380 
381  // We must be right in front of the node we're looking for now, otherwise it doesn't exist in the Skiplist at all.
382  pNode = pNode->Next[0];
383  if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
384  {
385  // It hasn't been found, so there's nothing to return.
386  return NULL;
387  }
388 
389  // Return the index of the element if the caller is interested.
390  if (ElementIndex)
391  *ElementIndex = dwIndex;
392 
393  // Return the stored element of the found node.
394  return pNode->Element;
395 }
SKIPLIST_NODE Head
Definition: skiplist.h:37
char CHAR
Definition: xmlstorage.h:175
CHAR MaximumLevel
Definition: skiplist.h:38
PSKIPLIST_COMPARE_ROUTINE CompareRoutine
Definition: skiplist.h:41
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
unsigned long DWORD
Definition: ntddk_ex.h:95
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define NULL
Definition: types.h:112
PVOID Element
Definition: skiplist.h:31

Referenced by _GetNextJobID(), _LocalGetJobLevel1(), _LocalGetJobLevel2(), _LocalOpenPrinterHandle(), LocalGetJob(), LocalScheduleJob(), LocalSetJob(), main(), and ReadJobShadowFile().

◆ LookupNodeByIndexSkiplist()

PSKIPLIST_NODE LookupNodeByIndexSkiplist ( PSKIPLIST  Skiplist,
DWORD  ElementIndex 
)

Definition at line 412 of file skiplist.c.

413 {
414  CHAR i;
415  DWORD dwIndex = 0;
416  PSKIPLIST_NODE pNode = &Skiplist->Head;
417 
418  // The only way the node can't be found is when the index is out of range.
419  if (ElementIndex >= Skiplist->NodeCount)
420  return NULL;
421 
422  // Do the efficient lookup in Skiplists:
423  // * Start from the maximum level.
424  // * Walk through all nodes on this level that come before the node we're looking for.
425  // * When we have reached such a node, go down a level and continue there.
426  // * Repeat these steps till we're in level 0, right in front of the node we're looking for.
427  for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
428  {
429  // We compare with <= instead of < here, because the added distances make up a 1-based index while ElementIndex is zero-based,
430  // so we have to jump one node further.
431  while (pNode->Next[i] && dwIndex + pNode->Distance[i] <= ElementIndex)
432  {
433  dwIndex += pNode->Distance[i];
434  pNode = pNode->Next[i];
435  }
436  }
437 
438  // We are right in front of the node we're looking for now.
439  return pNode->Next[0];
440 }
DWORD NodeCount
Definition: skiplist.h:39
SKIPLIST_NODE Head
Definition: skiplist.h:37
char CHAR
Definition: xmlstorage.h:175
CHAR MaximumLevel
Definition: skiplist.h:38
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
unsigned long DWORD
Definition: ntddk_ex.h:95
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define NULL
Definition: types.h:112

Referenced by LocalEnumJobs(), and main().