1/*
2 * Copyright © 2004 Keith Packard and Bart Massey.
3 * All Rights Reserved.  See the file COPYING in this directory
4 * for licensing information.
5 */
6
7autoload PRNG;
8
9namespace Skiplist {
10    public typedef bool (poly a, poly b) Greater;
11
12    public typedef void (poly a) Visit;
13
14    public exception not_found (poly missing);
15
16    /*
17     * Private representation of an element
18     */
19    typedef Element;
20
21    typedef union {
22	*Element	element;
23	void		nil;
24    } ElementPtr;
25
26    const MaxLevel = 16;
27
28    typedef struct {
29	poly		value;
30	ElementPtr[*]	forward;
31    } Element;
32
33    typedef struct {
34	int		level;
35	Greater		greater;
36	Element		header;
37    } SkipRec;
38
39    public typedef *SkipRec Skip;
40
41    int random_level ()
42	/*
43	 * This uses a fixed probability of 1/4 for each level
44	 */
45    {
46	int bits = PRNG::randbits(MaxLevel * 2);
47	int level = 0;
48
49	while (++level < MaxLevel)
50	{
51	    if ((bits & 3) != 0)
52		break;
53	    bits >>= 2;
54	}
55	return level;
56    }
57
58    public Skip new (Greater greater)
59	/*
60	 * Allocate a new list with 'greater' as the ordering function
61	 */
62    {
63	return &(SkipRec) {
64	    .level = 0,
65	    .greater = greater,
66	    .header = {
67		.forward = (ElementPtr[MaxLevel]) { [i] = ElementPtr.nil },
68		.value = <>
69	    }
70	};
71    }
72
73    public poly search (Skip list, poly value)
74	/*
75	 * Search 'list' for 'value', returning a
76	 * matching value in the list else Raise 'not_found'.
77	 */
78    {
79	ElementPtr x = (ElementPtr.element) &list->header;
80
81	for (int i = list->level; --i >= 0; )
82	{
83	    while (x.element->forward[i] != ElementPtr.nil &&
84		   list->greater (value,
85				  x.element->forward[i].element->value))
86		x = x.element->forward[i];
87	}
88	x = x.element->forward[0];
89	if (x == ElementPtr.nil || list->greater (x.element->value, value))
90	    raise not_found (value);
91	return x.element->value;
92    }
93
94    public void insert (Skip list, poly value)
95	/*
96	 * Insert 'value' into 'list'
97	 */
98    {
99	ElementPtr[MaxLevel] update = {};
100	ElementPtr x = (ElementPtr.element) &list->header;
101
102	for (int i = list->level; --i >= 0;)
103	{
104	    while (x.element->forward[i] != ElementPtr.nil &&
105		   list->greater (value,
106				  x.element->forward[i].element->value))
107		x = x.element->forward[i];
108	    update[i] = x;
109	}
110	x = x.element->forward[0];
111	int level = random_level ();
112	if (level > list->level)
113	{
114	    level = list->level + 1;
115	    list->level = level;
116	    update[level-1] = (ElementPtr.element) &list->header;
117	}
118
119	/*
120	 * Allocate new list entry
121	 */
122	ElementPtr new = (ElementPtr.element) &(Element) {
123	    .value = value,
124	    .forward = (ElementPtr[level]) {}
125	};
126
127	for (int i = 0; i < level; i++)
128	{
129	    new.element->forward[i] = update[i].element->forward[i];
130	    update[i].element->forward[i] = new;
131	}
132    }
133
134    public void delete (Skip list, poly value)
135	 /*
136	  * delete entry matching 'value' from 'list', else
137	  * raise not_found.
138	  */
139    {
140	ElementPtr[MaxLevel] update = {};
141	ElementPtr x = (ElementPtr.element) &list->header;
142
143	for (int i = list->level; --i >= 0;)
144	{
145	    while (x.element->forward[i] != ElementPtr.nil &&
146		   list->greater (value,
147				  x.element->forward[i].element->value))
148		x = x.element->forward[i];
149	    update[i] = x;
150	}
151	x = x.element->forward[0];
152	if (x == ElementPtr.nil || list->greater (x.element->value, value))
153	    raise not_found (value);
154
155	for (int i = 0;
156	     i < list->level && update[i].element->forward[i] == x;
157	     i++)
158	{
159	    update[i].element->forward[i] = x.element->forward[i];
160	}
161
162	while (list->level > 0 &&
163	       list->header.forward[list->level-1] == ElementPtr.nil)
164	    list->level--;
165    }
166
167    public void walk (Skip list, Visit visit)
168	/*
169	 * Invoke 'visit' for each element of 'list'.
170	 * Operations on
171	 */
172    {
173	for (ElementPtr e = list->header.forward[0];
174	     e != ElementPtr.nil;
175	     e = (ElementPtr next))
176	 {
177	    next = e.element->forward[0];
178	    visit (e.element->value);
179	 }
180    }
181
182    public bool (&poly) iterate (Skip list)
183    {
184	ElementPtr  e = list->header.forward[0];
185
186	bool next (&poly value) {
187	    if (e == ElementPtr.nil)
188		return false;
189	    value = e.element->value;
190	    e = e.element->forward[0];
191	    return true;
192	}
193
194	return next;
195    }
196
197    public int length (Skip list)
198    {
199	int len = 0;
200	for (ElementPtr e = list->header.forward[0];
201	     e != ElementPtr.nil;
202	     e = e.element->forward[0])
203	{
204	    len++;
205	}
206	return len;
207    }
208
209    public int storage (Skip list, poly value)
210    {
211	ElementPtr x = (ElementPtr.element) &list->header;
212
213	for (int i = list->level; --i >= 0;)
214	{
215	    while (x.element->forward[i] != ElementPtr.nil &&
216		   list->greater (value,
217				  x.element->forward[i].element->value))
218		x = x.element->forward[i];
219	}
220	x = x.element->forward[0];
221	if (x == ElementPtr.nil || list->greater (x.element->value, value))
222	    raise not_found (value);
223	return dim (x.element->forward);
224    }
225}
226
227namespace Sortlist {
228    public import Skiplist;
229}
230