* Author: Sebastian Freundt <hroptatyr@sxemacs.org>
*
* This file is part of SXEmacs.
- *
+ *
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
#include "lrecord.h"
#include "lstream.h"
+/* for __ase_ffs() */
+#include "ent/ent.h"
#include "skiplist.h"
#define __SKIPLIST_DEBUG__(args...) fprintf(stderr, "SKIPLIST " args)
skiplist_find_hash_return_level(skiplist_t, hcode_t)
__attribute__((always_inline));
-extern int get_random(void);
-
/* high level bindings */
\f
/* low level bindings */
(tmphash < hash);
tmp = next_node(tmp) ) {}
result = tmp;
- }
+ }
return result;
}
mark_object(node_data_value(parent_node(tmp)));
}
- mark_object(XSKIPLIST_PLIST(obj));
+ mark_object(XSKIPLIST_PLIST(obj));
return XSKIPLIST_PLIST(obj);
}
static void
print_skiplist(Lisp_Object obj, Lisp_Object printcharfun, int escapeflag)
{
- write_fmt_str(printcharfun, "#<skiplist :size %lu :levels %lu >",
- (long unsigned int)XSKIPLIST_NNODES(obj),
+ write_fmt_str(printcharfun, "#<skiplist :size %lu :levels %lu >",
+ (long unsigned int)XSKIPLIST_NNODES(obj),
(long unsigned int)XSKIPLIST_NLEVELS(obj));
}
static void
-finalise_skiplist(void *header, int UNUSED(for_disksave))
+finalise_skiplist(void *header, int SXE_UNUSED(for_disksave))
{
skiplist_t sl = header;
*/
(skiplist))
{
- CHECK_SKIPLIST(skiplist);
- return XSKIPLIST_PLIST(skiplist);
+ CHECK_SKIPLIST(skiplist);
+ return XSKIPLIST_PLIST(skiplist);
}
static const struct lrecord_description skiplist_description[] = {
hcode_t h, Lisp_Object key, Lisp_Object value)
{
/* entirely new data, build a node for it */
- /* determine the number of levels to add */
- size_t nlevels = __ase_ffsl(random()), cnt;
+ /* determine the number of levels to add, this is a log distribution
+ * so we use ffs(3) of a random number */
+ size_t nlevels = __ase_ffsl(random());
+ size_t cnt;
skiplist_level_t levels, last = path[psz--];
skiplist_node_t node;
{
CHECK_SKIPLIST(skiplist);
-
+
return copy_skiplist(XSKIPLIST(skiplist));
}
Return the union skiplist of SKIPLISTS.
Args are &rest SKIPLIST.
-The union is a skiplist containing all key-value-pairs which are
+The union is a skiplist containing all key-value-pairs which are
in at least one of the SKIPLISTS.
Note: Key-value-pairs with equal keys and distinct values are
Lisp_Object args[3];
skiplist_level_t lev;
struct gcpro gcpro1, gcpro2;
-
- CHECK_SKIPLIST(skiplist);
+
+ CHECK_SKIPLIST(skiplist);
GCPRO2(function, skiplist);
- sl = XSKIPLIST(skiplist);
+ sl = XSKIPLIST(skiplist);
lev = next_node(skiplist_foot(sl)); /* start at the bottom */
while (lev) {
args[0] = function;