1 /*** skiplist.h -- Pugh's Skiplists
3 * Copyright (C) 2006, 2007, 2008 Sebastian Freundt
5 * Author: Sebastian Freundt <hroptatyr@sxemacs.org>
7 * This file is part of SXEmacs.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the author nor the names of any contributors
21 * may be used to endorse or promote products derived from this
22 * software without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
31 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
32 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
33 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
34 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 /* Synched up with: Not in FSF. */
40 #ifndef INCLUDED_skiplist_h_
41 #define INCLUDED_skiplist_h_
48 /* Our implementation of skiplists:
50 +------+ +------+ +------+
51 | data | nil | data | nil | data | nil
52 +------+ ^ +------+ ^ +------+ ^
53 |\+--|--+ \+--|--+ |\+--|--+
54 | |ptr0-|---------->|ptr0-|---------|>|ptr0-|---->nil
55 | +--^--+ +--^--+ | +--^--+
57 \+--|--+ head \+--|--+
58 |ptr1-|---------------------------->|ptr1-|---->nil
67 extern Lisp_Object Qskiplistp;
68 extern void skiplist_reinit(void);
70 typedef struct skiplist_s *skiplist_t;
71 typedef Lisp_Object(*skiplist_map_f)(Lisp_Object key, Lisp_Object value);
72 typedef Lisp_Object(*skiplist_map2_f)(Lisp_Object key, Lisp_Object val, void*);
74 typedef struct skiplist_data_s *skiplist_data_t;
75 typedef struct skiplist_level_s *skiplist_level_t;
76 typedef struct skiplist_node_s *skiplist_node_t;
77 typedef struct skiplist_path_s *skiplist_path_t;
79 #define MAX_SKIPLIST_HEIGHT 63
82 struct lcrecord_header lheader;
84 /* the sequence category */
86 /* the dict (aset) category */
89 /* the head levels are just a fixed size array */
90 skiplist_level_t headlevs;
91 size_t nnodes; /* number of nodes in this skiplist */
92 size_t nlevels; /* maximum over all numbers of levels */
94 Lisp_Object plist; /* property list */
97 DECLARE_LRECORD(skiplist, struct skiplist_s);
98 #define XSKIPLIST(x) XRECORD(x, skiplist, struct skiplist_s)
99 #define XSETSKIPLIST(x, p) XSETRECORD(x, p, skiplist)
100 #define wrap_skiplist(p) wrap_object(p)
101 #define SKIPLISTP(x) RECORDP(x, skiplist)
102 #define CHECK_SKIPLIST(x) CHECK_RECORD(x, skiplist)
103 #define CONCHECK_SKIPLIST(x) CONCHECK_RECORD(x, skiplist)
105 #define skiplist_nnodes(ms) (ms)->nnodes
106 #define skiplist_nlevels(ms) (ms)->nlevels
107 #define skiplist_head(ms) (&((ms)->headlevs[skiplist_nlevels(ms)]))
108 #define skiplist_foot(ms) (&((ms)->headlevs[0]))
109 #define skiplist_plist(ms) (ms)->plist
110 #define XSKIPLIST_HEAD(x) skiplist_head(XSKIPLIST(x))
111 #define XSKIPLIST_FOOT(x) skiplist_foot(XSKIPLIST(x))
112 #define XSKIPLIST_NNODES(x) skiplist_nnodes(XSKIPLIST(x))
113 #define XSKIPLIST_NLEVELS(x) skiplist_nlevels(XSKIPLIST(x))
114 #define XSKIPLIST_PLIST(x) skiplist_plist(XSKIPLIST(x))
117 extern Lisp_Object make_skiplist(void);
118 extern void put_skiplist(skiplist_t, Lisp_Object, Lisp_Object);
119 extern Lisp_Object get_skiplist(skiplist_t, Lisp_Object, Lisp_Object);
120 extern void remove_skiplist(skiplist_t, Lisp_Object);
121 extern_inline bool skiplist_empty_p(skiplist_t);
122 extern bool skiplist_owns_p(skiplist_t, Lisp_Object);
123 extern Lisp_Object copy_skiplist(skiplist_t);
124 extern void unite_skiplist(skiplist_t, skiplist_t);
125 extern void intersect_skiplist(skiplist_t, skiplist_t);
127 extern void map_skiplist(skiplist_t, skiplist_map_f);
128 extern void map2_skiplist(skiplist_t, skiplist_map2_f, void*);
131 skiplist_empty_p(skiplist_t sl)
133 return (skiplist_nnodes(sl) == 0 ? true : false);
136 EXFUN(Fmake_skiplist, 0);
137 EXFUN(Fget_skiplist,3);
138 EXFUN(Fremove_skiplist,2);
141 extern_inline skiplist_path_t make_skiplist_path(skiplist_t);
142 extern_inline void free_skiplist_path(skiplist_path_t);
143 extern_inline size_t skiplist_path_size(skiplist_path_t);
144 extern_inline skiplist_level_t skiplist_path_first(skiplist_path_t);
145 extern_inline skiplist_level_t skiplist_path_last(skiplist_path_t);
146 extern_inline void skiplist_path_push(skiplist_path_t, skiplist_level_t);
147 extern_inline skiplist_level_t skiplist_path_pop(skiplist_path_t);
148 extern_inline skiplist_level_t skiplist_path_pophead(skiplist_path_t);
149 extern_inline int descend_level_p(void);
152 #endif /* INCLUDED_skiplist_h_ */