cgit.sxemacs.org Git - sxemacs/blob - src/skiplist.h

   1 /*** skiplist.h -- Pugh's Skiplists
   2  *
   3  * Copyright (C) 2006, 2007, 2008 Sebastian Freundt
   4  *
   5  * Author:  Sebastian Freundt <hroptatyr@sxemacs.org>
   6  *
   7  * This file is part of SXEmacs.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  *
  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.
  19  *
  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.
  23  *
  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.
  35  *
  36  ***/
  37
  38 /* Synched up with: Not in FSF. */
  39
  40 #ifndef INCLUDED_skiplist_h_
  41 #define INCLUDED_skiplist_h_
  42
  43 #include "elhash.h"
  44 #include <stdbool.h>
  45 #include "seq.h"
  46 #include "dict.h"
  47
  48 /* Our implementation of skiplists:
  49
  50    +------+          +------+          +------+
  51    | data |   nil    | data |   nil    | data |   nil
  52    +------+    ^     +------+    ^     +------+    ^
  53           |\+--|--+          \+--|--+         |\+--|--+
  54           | |ptr0-|---------->|ptr0-|---------|>|ptr0-|---->nil
  55           | +--^--+           +--^--+         | +--^--+
  56           |    |                 |            |    |
  57            \+--|--+             head           \+--|--+
  58             |ptr1-|---------------------------->|ptr1-|---->nil
  59             +--^--+                             +--^--+
  60                |                                   |
  61 +--------+     |                                  head
  62 |Skiplist+--->head
  63 +--------+
  64
  65 */
  66
  67 extern Lisp_Object Qskiplistp;
  68 extern void skiplist_reinit(void);
  69
  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*);
  73 /* hidden structs */
  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;
  78
  79 #define MAX_SKIPLIST_HEIGHT     63
  80
  81 struct skiplist_s {
  82         struct lcrecord_header lheader;
  83
  84         /* the sequence category */
  85         void *si;
  86         /* the dict (aset) category */
  87         void *di;
  88
  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 */
  93
  94         Lisp_Object plist;      /* property list */
  95 };
  96
  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)
 104
 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))
 115
 116 \f
 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);
 126
 127 extern void map_skiplist(skiplist_t, skiplist_map_f);
 128 extern void map2_skiplist(skiplist_t, skiplist_map2_f, void*);
 129
 130 extern_inline bool
 131 skiplist_empty_p(skiplist_t sl)
 132 {
 133         return (skiplist_nnodes(sl) == 0 ? true : false);
 134 }
 135
 136 EXFUN(Fmake_skiplist, 0);
 137 EXFUN(Fget_skiplist,3);
 138 EXFUN(Fremove_skiplist,2);
 139
 140 extern_inline skiplist_path_t make_skiplist_path(skiplist_t);
 141 extern_inline void free_skiplist_path(skiplist_path_t);
 142 extern_inline size_t skiplist_path_size(skiplist_path_t);
 143 extern_inline skiplist_level_t skiplist_path_first(skiplist_path_t);
 144 extern_inline skiplist_level_t skiplist_path_last(skiplist_path_t);
 145 extern_inline void skiplist_path_push(skiplist_path_t, skiplist_level_t);
 146 extern_inline skiplist_level_t skiplist_path_pop(skiplist_path_t);
 147 extern_inline skiplist_level_t skiplist_path_pophead(skiplist_path_t);
 148 extern_inline int descend_level_p(void);
 149
 150
 151 #endif  /* INCLUDED_skiplist_h_ */