|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/tools/db_slist.c |
source navigation diff markup identifier search freetext search file search |
1 static char const rcsid[] = "$Id: db_slist.c,v 6.2 2003/05/30 17:25:36 coulouri Exp $";
2
3 /* db_slist.c
4 * ===========================================================================
5 *
6 * PUBLIC DOMAIN NOTICE
7 * National Center for Biotechnology Information
8 *
9 * This software/database is a "United States Government Work" under the
10 * terms of the United States Copyright Act. It was written as part of
11 * the author's official duties as a United States Government employee and
12 * thus cannot be copyrighted. This software/database is freely available
13 * to the public for use. The National Library of Medicine and the U.S.
14 * Government have not placed any restriction on its use or reproduction.
15 *
16 * Although all reasonable efforts have been taken to ensure the accuracy
17 * and reliability of the software and data, the NLM and the U.S.
18 * Government do not and cannot warrant the performance or results that
19 * may be obtained by using this software or data. The NLM and the U.S.
20 * Government disclaim all warranties, express or implied, including
21 * warranties of performance, merchantability or fitness for any particular
22 * purpose.
23 *
24 * Please cite the author in any work or product based on this material.
25 *
26 * ===========================================================================
27 *
28 * File Name: db_slist.c
29 *
30 * Author: Kun-Mao Chao and Jinghui Zhang
31 *
32 * Version Creation Date: 5/24/95
33 *
34 *
35 * File Description:
36 * Example of Skip List source code for C:
37
38 * Skip Lists are a probabilistic alternative to balanced trees, as
39 * described in the June 1990 issue of CACM and were invented by
40 * William Pugh in 1987.
41
42 * This file contains source code to implement a dictionary using
43 * skip lists and a test driver to test the routines.
44
45 * A couple of comments about this implementation:
46 * The routine randomLevel has been hard-coded to generate random
47 * levels using p=0.25. It can be easily changed.
48 *
49 * The insertion routine has been implemented so as to use the
50 * dirty hack described in the CACM paper: if a random level is
51 * generated that is more than the current maximum level, the
52 * current maximum level plus one is used instead.
53
54 * Levels start at zero and go up to MaxLevel (which is equal to
55 * (MaxNumberOfLevels-1).
56
57 * The compile flag allowDuplicates determines whether or not duplicates
58 * are allowed. If defined, duplicates are allowed and act in a FIFO manner.
59 * If not defined, an insertion of a value already in the file updates the
60 * previously existing binding.
61 *
62 * BitsInRandom is defined to be the number of bits returned by a call to
63 * random(). For most all machines with 32-bit integers, this is 31 bits
64 * as currently set.
65
66 *
67 * Modifications:
68 * --------------------------------------------------------------------------
69 * Date Name Description of modification
70 *
71 * $Log: db_slist.c,v $
72 * Revision 6.2 2003/05/30 17:25:36 coulouri
73 * add rcsid
74 *
75 * Revision 6.1 1998/08/24 21:19:37 kans
76 * fixed -v -fd warnings
77 *
78 * Revision 6.0 1997/08/25 18:53:01 madden
79 * Revision changed to 6.0
80 *
81 * Revision 5.0 1996/05/28 13:43:15 ostell
82 * Set to revision 5.0
83 *
84 * Revision 4.0 1995/07/26 13:50:15 ostell
85 * force revision to 4.0
86 *
87 * Revision 1.2 1995/05/25 20:15:32 zjing
88 * falign.c
89 *
90 *
91 *
92 * ==========================================================================
93 */
94
95
96 #ifndef _LIST_
97 #include <list.h>
98 #endif
99
100 #ifndef _DB_LIST_
101 #include <db_list.h>
102 #endif
103
104 db_node NIL;
105
106 extern Int4 randomsLeft;
107 extern Int4 randomBits;
108
109 /* db_init - defines NIL and initializes the random bit source */
110 void db_init(void) {
111
112 NIL = db_newNodeOfLevel(0);
113 NIL->key = 0x7fffffff;
114 NIL->value = NULL;
115 NIL->forward[0] = NIL;
116 randomBits = rand();
117 randomsLeft = BitsInRandom/2;
118 }
119
120 /* dblist_NIL_free - free NIL 1/27/94 */
121 void dblist_NIL_free(void)
122 {
123 MemFree(NIL);
124 }
125
126 /* db_newList - create a new list */
127 db_list db_newList(void) {
128 db_list l;
129 Int4 i;
130
131 l = (db_list)ckalloc(sizeof(struct db_listStructure));
132 l->level = 0;
133 l->header = db_newNodeOfLevel(MaxNumberOfLevels);
134 l->header->key = -1;
135 l->header->value = NULL;
136 l->header->back = NULL;
137 for(i=0;i<MaxNumberOfLevels;i++) l->header->forward[i] = NIL;
138 return(l);
139 }
140
141 /* idb_newList - create a new list */
142 idb_list idb_newList(void) {
143 idb_list l;
144 Int4 i;
145
146 l = (idb_list)ckalloc(sizeof(struct idb_listStructure));
147 l->level = 0;
148 l->header = db_newNodeOfLevel(IMaxNumberOfLevels);
149 l->header->key = -1;
150 l->header->value = NULL;
151 l->header->back = NULL;
152 for(i=0;i<IMaxNumberOfLevels;i++) l->header->forward[i] = NIL;
153 return(l);
154 }
155
156 /* db_reset_pos - reset cur_p */
157 void db_reset_pos(db_list l)
158 {
159 register Int4 k;
160 register db_node p;
161
162 p = l->header;
163 for (k = 0; k <= l->level; ++k) l->update[k] = p;
164 }
165
166 /* db_sreset_pos - reset l->update[0] */
167 void db_sreset_pos(db_list l)
168 {
169 l->update[0] = l->header;
170 }
171
172 /* idb_reset_pos - reset cur_p */
173 void idb_reset_pos(idb_list l)
174 {
175 l->update = l->header;
176 }
177
178 /* db_freeList - free the space of the list */
179 void db_freeList(db_list l)
180 {
181 register db_node p,q;
182 void decre(fragment PNTR);
183
184 p = l->header;
185 do {
186 q = p->forward[0];
187 decre(p->value);
188 MemFree(p);
189 p = q; }
190 while (p!=NIL);
191 MemFree(l);
192 }
193
194 /* idb_freeList - free the space of the list */
195 void idb_freeList(idb_list l)
196 {
197 register db_node p,q;
198 p = l->header;
199 while (p != NIL) {
200 q = p->forward[0];
201 MemFree(p);
202 p = q; }
203 MemFree(l);
204 }
205
206 /* db_randomLevel - return a random level */
207 Int4 db_randomLevel(Int4 maxl)
208 {register Int4 level = 0;
209 register Int4 b;
210 do {
211 b = randomBits&3;
212 if (!b) level++;
213 randomBits>>=2;
214 if (--randomsLeft == 0) {
215 randomBits = rand();
216 randomsLeft = BitsInRandom/2;
217 }
218 } while (!b);
219 return(level>maxl ? maxl : level);
220 }
221
222 /* db_insert - insert a new node to the list */
223 void db_insert(idb_list l, keyType key, valueType value)
224 {
225 register Int4 k;
226 register db_node p,q;
227 db_node update[IMaxNumberOfLevels];
228
229 if (!l) return;
230 p = l->header;
231 k = l->level;
232 do {
233 while (q = p->forward[k], q->key < key) p = q;
234 update[k] = p;
235 } while(--k>=0);
236
237
238 k = db_randomLevel(IMaxLevel);
239 if (k>l->level) {
240 k = ++l->level;
241 update[k] = l->header;
242 }
243 q = db_newNodeOfLevel(k);
244 q->key = key;
245 q->value = value;
246 do {
247 p = update[k];
248 q->forward[k] = p->forward[k];
249 p->forward[k] = q;
250 } while(--k>=0);
251 q->back = update[0];
252 (q->forward[0])->back = q;
253 return;
254 }
255
256 /* db_delete - delete a node from the list by key */
257 void db_delete(idb_list l, keyType key)
258 {
259 register Int4 k,m;
260 register db_node p,q;
261 db_node update[IMaxNumberOfLevels];
262
263 if (!l) return;
264 p = l->header;
265 k = m = l->level;
266 do {
267 while (q = p->forward[k], q->key < key) p = q;
268 update[k] = p;
269 } while(--k>=0);
270
271 for(k=0; k<=m && (p=update[k])->forward[k] == q; k++)
272 p->forward[k] = q->forward[k];
273 (q->forward[0])->back = p;
274 MemFree(q);
275 while( l->header->forward[m] == NIL && m > 0 )
276 m--;
277 l->level = m;
278 }
279
280 /* db_rsearch - search a node in the list by key */
281 /* find p s.t. p->key < key <= (p->forward[0])->key */
282 valueType db_rsearch(db_list l, keyType key)
283 {
284 register Int4 k;
285 register db_node p,q;
286 p = l->header;
287 k = l->level;
288 do {
289 while (q = p->forward[k], q->key < key) p = q;
290 l->update[k] = p;
291 } while(--k>=0);
292 return(p->value);
293 }
294
295 /* db_rsearch_next - search from cur_p */
296 /* find p s.t. p->key < key <= (p->forward[0])->key */
297 valueType db_rsearch_next(db_list l, keyType key)
298 {
299 register Int4 k;
300 register db_node p,q;
301 k = l->level;
302 p = l->update[k];
303 do {
304 while (q = p->forward[k] , q->key < key) p = q;
305 l->update[k] = p;
306 } while(--k>=0);
307 return(p->value);
308 }
309
310 /* db_lsearch - search a node in the list by key */
311 /* find p s.t. p->key <= key < (p->forward[0])->key */
312 valueType db_lsearch(db_list l, keyType key)
313 {
314 register Int4 k;
315 register db_node p,q;
316 p = l->header;
317 k = l->level;
318 do {
319 while (q = p->forward[k], q->key <= key) p = q;
320 l->update[k] = p;
321 } while(--k>=0);
322 return(p->value);
323 }
324
325 /* db_lsearch_next - search from cur_p */
326 /* find p s.t. p->key <= key < (p->forward[0])->key */
327 valueType db_lsearch_next(db_list l, keyType key)
328 {
329 register Int4 k;
330 register db_node p,q;
331 k = l->level;
332 p = l->update[k];
333 do {
334 while (q = p->forward[k] , q->key <= key) p = q;
335 l->update[k] = p;
336 } while(--k>=0);
337 return(p->value);
338 }
339
340 /* db_cur_key - return the key of the node pointed by the pointer cur_p */
341 keyType db_cur_key(db_list l)
342 {
343 return((l->update[0])->key);
344 }
345
346 /* db_update_node - update the value of the node pointed by cur_p */
347 void db_update_node(db_list l, valueType value)
348 {
349 (l->update[0])->value = value;
350 }
351
352 /* db_next_key - return the key of the node next to the node pointed by cur_p */
353 keyType db_next_key(db_list l)
354 {
355 db_node p;
356
357 p = (l->update[0])->forward[0];
358 if (p != NIL) return(p->key);
359 else return(-1);
360 }
361
362 /* db_next_val - return the value of the node next to the node pointed by cur_p */
363 valueType db_next_val(db_list l)
364 {
365 db_node p;
366
367 p = (l->update[0])->forward[0];
368 if (p != NIL) return(p->value);
369 else return(NULL);
370 }
371
372 /* db_prev_key - return the key of the node before the node pointed by cur_p */
373 keyType db_prev_key(db_list l)
374 {
375 db_node p;
376
377 p = (l->update[0])->back;
378 if (p) return(p->key);
379 else return(-1);
380 }
381
382 /* db_prev_val - return the value of the node before the node pointed by cur_p */
383 valueType db_prev_val(db_list l)
384 {
385 db_node p;
386
387 p = (l->update[0])->back;
388 if (p) return(p->value);
389 else return(NULL);
390 }
391
392 /* db_key_next - move l->cur_p right */
393 keyType db_key_next(db_list l)
394 {
395 db_node p, q;
396 Int4 k;
397
398 p = l->update[0];
399 q = p->forward[0];
400 if (q == NIL) return (-1);
401 else {
402 for (k = 0; k <= l->level && (((l->update[k])->forward[k])
403 == q); k++) l->update[k] = q;
404 return(q->key);
405 }
406 }
407
408 /* idb_key_next - move l->cur_p right */
409 keyType idb_key_next(idb_list l)
410 {
411 db_node p, q;
412
413 p = l->update;
414 q = p->forward[0];
415 if (q == NIL) return (-1);
416 else {
417 l->update = q;
418 return(q->key);
419 }
420 }
421
422 /* db_next - move l->cur_p right */
423 valueType db_next(db_list l)
424 {
425 db_node p, q;
426 Int4 k;
427
428 p = l->update[0];
429 q = p->forward[0];
430 if (q == NIL) return (NULL);
431 else {
432 for (k = 0; k <= l->level && (((l->update[k])->forward[k])
433 == q); k++) l->update[k] = q;
434 return(q->value);
435 }
436 }
437
438 /* db_snext - search sequencially */
439 valueType db_snext(db_list l)
440 {
441 db_node p, q;
442
443 p = l->update[0];
444 q = p->forward[0];
445 l->update[0]=q;
446 return(q->value);
447 }
448
449 /*db_delete_next - delete the node next to the node pointed by cur_p */
450 void db_delete_next(db_list l)
451 {
452 register Int4 k,m;
453 register db_node p,q;
454
455 m = l->level;
456 q = (l->update[0])->forward[0];
457 if (q == NIL) return;
458 for (k=0; k<=m && (p=l->update[k])->forward[k] == q; k++)
459 p->forward[k] = q->forward[k];
460 (q->forward[0])->back = l->update[0];
461 MemFree(q);
462 while (l->header->forward[m] == NIL && m > 0) m--;
463 l->level = m;
464 }
465
466 /* db_insert_next - insert a new node next to the node pointed by cur_p */
467 void db_insert_next(db_list l, keyType key, valueType value)
468 {
469 register Int4 k;
470 register db_node p,q;
471
472 k = db_randomLevel(MaxLevel);
473 if (k>l->level) {
474 k = ++l->level;
475 l->update[k] = l->header;
476 }
477 q = db_newNodeOfLevel(k);
478 q->key = key;
479 q->value = value;
480 do {
481 p = l->update[k];
482 q->forward[k] = p->forward[k];
483 p->forward[k] = q;
484 l->update[k] = q;
485 } while (--k >= 0);
486 q->back = p;
487 (q->forward[0])->back = q;
488 }
489
490 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |