← Back to branch summary

~ubuntu-branches/ubuntu/warty/ncbi-tools6/warty

« back to all changes in this revision

Viewing changes to tools/slist.c

  • Committer: Bazaar Package Importer
  • Author(s): Aaron M. Ucko
  • Date: 2002-04-04 22:13:09 UTC
  • Revision ID: james.westby@ubuntu.com-20020404221309-vfze028rfnlrldct
Tags: upstream-6.1.20011220a
Import upstream version 6.1.20011220a

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/slist.c
 
1
/*  slist.c
 
2
* ===========================================================================
 
3
*
 
4
*                            PUBLIC DOMAIN NOTICE
 
5
*               National Center for Biotechnology Information
 
6
*
 
7
*  This software/database is a "United States Government Work" under the
 
8
*  terms of the United States Copyright Act.  It was written as part of
 
9
*  the author's official duties as a United States Government employee and
 
10
*  thus cannot be copyrighted.  This software/database is freely available
 
11
*  to the public for use. The National Library of Medicine and the U.S.
 
12
*  Government have not placed any restriction on its use or reproduction.
 
13
*
 
14
*  Although all reasonable efforts have been taken to ensure the accuracy
 
15
*  and reliability of the software and data, the NLM and the U.S.
 
16
*  Government do not and cannot warrant the performance or results that
 
17
*  may be obtained by using this software or data. The NLM and the U.S.
 
18
*  Government disclaim all warranties, express or implied, including
 
19
*  warranties of performance, merchantability or fitness for any particular
 
20
*  purpose.
 
21
*
 
22
*  Please cite the author in any work or product based on this material.
 
23
*
 
24
* ===========================================================================
 
25
*
 
26
* File Name:  slist.c
 
27
*
 
28
* Author:  Kun-Mao Chao and Jinghui Zhang
 
29
*
 
30
* Version Creation Date: 5/24/95
 
31
*
 
32
*
 
33
* File Description:  
 
34
*
 
35
* Example of Skip List source code for C:
 
36
 
 
37
* Skip Lists are a probabilistic alternative to balanced trees, as
 
38
* described in the June 1990 issue of CACM and were invented by 
 
39
* William Pugh in 1987. 
 
40
* 
 
41
* This file contains source code to implement a dictionary using 
 
42
* skip lists and a test driver to test the routines.
 
43
* 
 
44
* A couple of comments about this implementation:
 
45
* The routine randomLevel has been hard-coded to generate random
 
46
* levels using p=0.25. It can be easily changed.
 
47
  
 
48
* The insertion routine has been implemented so as to use the
 
49
* dirty hack described in the CACM paper: if a random level is
 
50
* generated that is more than the current maximum level, the
 
51
* current maximum level plus one is used instead.
 
52
* 
 
53
* Levels start at zero and go up to MaxLevel (which is equal to
 
54
*       (MaxNumberOfLevels-1).
 
55
* 
 
56
* The compile flag allowDuplicates determines whether or not duplicates
 
57
* are allowed. If defined, duplicates are allowed and act in a FIFO manner.
 
58
* If not defined, an insertion of a value already in the file updates the
 
59
* previously existing binding.
 
60
* 
 
61
* BitsInRandom is defined to be the number of bits returned by a call to
 
62
* random(). For most all machines with 32-bit integers, this is 31 bits
 
63
* as currently set. 
 
64
 
 
65
 
 
66
* Modifications:
 
67
* --------------------------------------------------------------------------
 
68
* Date     Name        Description of modification
 
69
*
 
70
* $Log: slist.c,v $
 
71
* Revision 6.1  1998/08/24 21:19:39  kans
 
72
* fixed -v -fd warnings
 
73
*
 
74
* Revision 6.0  1997/08/25 18:54:42  madden
 
75
* Revision changed to 6.0
 
76
*
 
77
* Revision 5.0  1996/05/28 13:43:15  ostell
 
78
* Set to revision 5.0
 
79
*
 
80
 * Revision 4.1  1996/05/21  13:43:39  epstein
 
81
 * change function-name 'delete' because it conflicts with VMS
 
82
 *
 
83
 * Revision 4.0  1995/07/26  13:50:15  ostell
 
84
 * force revision to 4.0
 
85
 *
 
86
 * Revision 1.2  1995/05/25  20:22:28  zjing
 
87
 * add header
 
88
 *
 
89
*
 
90
*
 
91
* ==========================================================================
 
92
*/
 
93
 
 
94
 
 
95
#ifndef _LIST_
 
96
#include <list.h>
 
97
#endif
 
98
 
 
99
node NIL1;
 
100
 
 
101
Int4 randomsLeft;
 
102
Int4 randomBits;
 
103
 
 
104
/* init - defines NIL1 and initializes the random bit source */ 
 
105
void init(void) { 
 
106
 
 
107
  NIL1 = newNodeOfLevel(0);
 
108
  NIL1->key = 0x7fffffff;
 
109
  NIL1->value = NULL;
 
110
  NIL1->forward[0] = NIL1;
 
111
  randomBits = rand();
 
112
  randomsLeft = BitsInRandom/2;
 
113
}
 
114
 
 
115
/* list_NIL_free - free NIL1 1/27/94 */
 
116
void list_NIL_free(void) {
 
117
   MemFree(NIL1);
 
118
}
 
119
 
 
120
/* newList - create a new list */
 
121
list newList(void) {
 
122
  list l;
 
123
  Int4 i;
 
124
 
 
125
  l = (list)ckalloc(sizeof(struct listStructure));
 
126
  l->level = 0;
 
127
  l->header = newNodeOfLevel(MaxNumberOfLevels);
 
128
  l->header->key = -1;
 
129
  l->header->value = NULL;
 
130
  for(i=0;i<MaxNumberOfLevels;i++) l->header->forward[i] = NIL1;
 
131
  return(l);
 
132
  } 
 
133
 
 
134
/* unewList - create a new list */
 
135
ulist unewList(void) {
 
136
  ulist l;
 
137
 
 
138
  l = (ulist)ckalloc(sizeof(struct ulistStructure));
 
139
  l->header = (unode)ckalloc(sizeof(struct unodeStructure)); 
 
140
  l->header->key = -1;
 
141
  l->header->link = NULL;
 
142
  return(l);
 
143
  } 
 
144
 
 
145
/* reset_pos - reset cur_p */
 
146
void reset_pos(list l)
 
147
{
 
148
        register Int4 k;
 
149
        register node p;
 
150
 
 
151
        p = l->header;
 
152
        for (k = 0; k <= l->level; ++k)   l->update[k] = p;
 
153
}
 
154
 
 
155
/* sreset_pos - reset l->update[0] */
 
156
void sreset_pos(list l)
 
157
{
 
158
        l->update[0] = l->header;
 
159
}
 
160
 
 
161
/* freeList - free the space of the list */
 
162
void freeList(list l) 
 
163
  {
 
164
  register node p,q;
 
165
  register Int4 i=0;
 
166
  void decre(fragment PNTR);
 
167
 
 
168
  p = l->header;
 
169
  do {
 
170
    ++i;
 
171
    q = p->forward[0];
 
172
    decre(p->value);
 
173
    MemFree(p);
 
174
    p = q; }
 
175
    while (p!=NIL1);
 
176
  MemFree(l);
 
177
  }
 
178
 
 
179
/* Feb. 1994*/
 
180
/* ufreeList - free the space of the ulist */
 
181
void ufreeList(ulist l) 
 
182
  {
 
183
  register unode p,q;
 
184
  register Int4 i=0;
 
185
 
 
186
  p = l->header;
 
187
  do {
 
188
    ++i;
 
189
    q = p->link;
 
190
    MemFree(p);
 
191
    p = q; }
 
192
    while (p!=NULL);
 
193
  MemFree(l);
 
194
  }
 
195
 
 
196
/* randomLevel - return a random level */
 
197
Int4 randomLevel(Int4 maxl)
 
198
  {register Int4 level = 0;
 
199
   register Int4 b;
 
200
   do {
 
201
    b = randomBits&3;
 
202
    if (!b) level++;
 
203
    randomBits>>=2;
 
204
    if (--randomsLeft == 0) {
 
205
        randomBits = rand();
 
206
        randomsLeft = BitsInRandom/2;
 
207
        };
 
208
    } while (!b);
 
209
    return(level>maxl ? maxl : level);
 
210
    }
 
211
 
 
212
/* uinsert - insert a new node to the ulist */
 
213
void uinsert(ulist l, keyType key) 
 
214
  {
 
215
  register unode p,q;
 
216
 
 
217
        for (p=l->header,q=p->link; q && q->key<key; p=q, q=p->link) continue;
 
218
        q = (unode)ckalloc(sizeof(struct unodeStructure));
 
219
        q->key = key;
 
220
        q->link = p->link;
 
221
        p->link = q;
 
222
    }
 
223
 
 
224
/* delete_by_key - delete a node from the list by key */
 
225
Int4 delete_by_key(list l, keyType key) 
 
226
  {
 
227
  register Int4 k,m;
 
228
  register node p,q;
 
229
 
 
230
  p = l->header;
 
231
  k = m = l->level;
 
232
  do {
 
233
        while (q = p->forward[k], q->key < key) p = q;
 
234
        l->update[k] = p;
 
235
        } while(--k>=0);
 
236
 
 
237
  if (q->key == key) {
 
238
        for(k=0; k<=m && (p=l->update[k])->forward[k] == q; k++) 
 
239
          p->forward[k] = q->forward[k];
 
240
        MemFree(q);
 
241
        while( l->header->forward[m] == NIL1 && m > 0 )
 
242
             m--;
 
243
        l->level = m;
 
244
        return(true);
 
245
        }
 
246
    else return(false);
 
247
    }
 
248
 
 
249
/* usearch - search a node in the ulist by key */
 
250
Boolean usearch(ulist l, keyType key) 
 
251
  {
 
252
  register unode p;
 
253
 
 
254
  if (!l) return(false);
 
255
  for (p=l->header; p && p->key < key; p=p->link) continue;
 
256
  if (p && p->key == key) return(true);
 
257
  else return(false);
 
258
    }
 
259
 
 
260
/* rsearch - search a node in the list by key */
 
261
/*           find p s.t. p->key < key <= (p->forward[0])->key */
 
262
valueType rsearch(list l, keyType key)
 
263
  {
 
264
  register Int4 k;
 
265
  register node p,q;
 
266
  p = l->header;
 
267
  k = l->level;
 
268
  do {
 
269
        while (q = p->forward[k], q->key < key) p = q;
 
270
        l->update[k] = p;
 
271
        } while(--k>=0);
 
272
  return(p->value);
 
273
  }
 
274
 
 
275
/* rsearch_next - search from cur_p */
 
276
/*           find p s.t. p->key < key <= (p->forward[0])->key */
 
277
valueType rsearch_next(list l, keyType key)
 
278
  {
 
279
  register Int4 k;
 
280
  register node p,q;
 
281
  k = l->level;
 
282
  p = l->update[k];
 
283
  do {
 
284
        while (q = p->forward[k] ,  q->key < key) p = q;
 
285
        l->update[k] = p;
 
286
        } while(--k>=0);
 
287
  return(p->value);
 
288
  }
 
289
 
 
290
/* cur_key - return the key of the node pointed by the pointer cur_p */
 
291
keyType cur_key(list l)
 
292
{
 
293
        return((l->update[0])->key);
 
294
}
 
295
 
 
296
/* update_node - update the value of the node pointed by cur_p */
 
297
void update_node(list l, valueType value)
 
298
{
 
299
        (l->update[0])->value = value;
 
300
}
 
301
 
 
302
/* next_key - return the key of the node next to the node pointed by cur_p */
 
303
keyType next_key(list l)
 
304
{
 
305
        node p;
 
306
 
 
307
        p = (l->update[0])->forward[0];
 
308
        if (p != NIL1) return(p->key);
 
309
        else return(-1);
 
310
}
 
311
 
 
312
/* next_val - return the value of the node next to the node pointed by cur_p */
 
313
valueType next_val(list l)
 
314
{
 
315
        node p;
 
316
 
 
317
        p = (l->update[0])->forward[0];
 
318
        if (p != NIL1) return(p->value);
 
319
        else return(NULL);
 
320
}
 
321
 
 
322
/* next - move l->cur_p right */
 
323
void next(list l)
 
324
{
 
325
        node p, q;
 
326
        Int4 k;
 
327
 
 
328
        p = l->update[0];
 
329
        q = p->forward[0];
 
330
        if (q == NIL1) return;
 
331
        else {
 
332
                for (k = 0; k <= l->level && (((l->update[k])->forward[k])
 
333
                        == q); k++)   l->update[k] = q;
 
334
        }
 
335
}
 
336
 
 
337
/* snext - move l->update[0] right */
 
338
valueType snext(list l)
 
339
{
 
340
        node p, q;
 
341
 
 
342
        p = l->update[0];
 
343
        q = p->forward[0];
 
344
        l->update[0] = q;
 
345
        return(q->value);
 
346
}
 
347
 
 
348
/*delete_next - delete the node next to the node pointed by cur_p */
 
349
void delete_next(list l)
 
350
{
 
351
        register Int4 k,m;
 
352
        register node p,q;
 
353
 
 
354
        m = l->level;
 
355
        q = (l->update[0])->forward[0];
 
356
        if (q == NIL1) return;
 
357
        for (k=0; k<=m && (p=l->update[k])->forward[k] == q; k++)
 
358
                p->forward[k] = q->forward[k];
 
359
        MemFree(q);
 
360
        while (l->header->forward[m] == NIL1 && m > 0)  m--;
 
361
        l->level = m;
 
362
}
 
363
 
 
364
/* insert_next - insert a new node next to the node pointed by cur_p */
 
365
void insert_next(list l, keyType key, valueType value)
 
366
{
 
367
        register Int4 k;
 
368
        register node p,q;
 
369
 
 
370
        k = randomLevel(MaxLevel);
 
371
        if (k>l->level) {
 
372
                k = ++l->level;
 
373
                l->update[k] = l->header;
 
374
        }
 
375
        q = newNodeOfLevel(k);
 
376
        q->key = key;
 
377
        q->value = value;
 
378
        do {
 
379
                p = l->update[k];
 
380
                q->forward[k] = p->forward[k];
 
381
                p->forward[k] = q;
 
382
                l->update[k] = q;
 
383
        } while (--k >= 0);
 
384
}
 
385
 
 
386