X-Git-Url: http://cgit.sxemacs.org/?a=blobdiff_plain;f=src%2Fskiplist.c;h=d073287462e6924fa37298693ae9b5ed62c32659;hb=29c4caea228ce22a9bfa76ef833d4473a9be8979;hp=43d9265c1345f6cc46815dd11deb1ddb8777a2aa;hpb=2f736345ae648bb1d2d13443c99da10816db7d61;p=sxemacs

diff --git a/src/skiplist.c b/src/skiplist.c
index 43d9265..d073287 100644
--- a/src/skiplist.c
+++ b/src/skiplist.c
@@ -5,7 +5,7 @@
  * 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:
@@ -46,6 +46,8 @@
 #include "lrecord.h"
 #include "lstream.h"
 
+/* for __ase_ffs() */
+#include "ent/ent.h"
 #include "skiplist.h"
 
 #define __SKIPLIST_DEBUG__(args...)	fprintf(stderr, "SKIPLIST " args)
@@ -113,8 +115,6 @@ static inline skiplist_level_t
 skiplist_find_hash_return_level(skiplist_t, hcode_t)
 	__attribute__((always_inline));
 
-extern int get_random(void);
-
 /* high level bindings */
 
 /* low level bindings */
@@ -354,7 +354,7 @@ skiplist_find_hash_return_level(skiplist_t slist, hcode_t hash)
 			     (tmphash < hash);
 		     tmp = next_node(tmp) ) {}
 		result = tmp;
- 	}
+	}
 
 	return result;
 }
@@ -404,20 +404,20 @@ mark_skiplist(Lisp_Object obj)
 		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;
 
@@ -464,8 +464,8 @@ Return the property list of SKIPLIST.
 */
       (skiplist))
 {
-        CHECK_SKIPLIST(skiplist);
-        return XSKIPLIST_PLIST(skiplist);
+	CHECK_SKIPLIST(skiplist);
+	return XSKIPLIST_PLIST(skiplist);
 }
 
 static const struct lrecord_description skiplist_description[] = {
@@ -561,8 +561,10 @@ _put_skiplist(skiplist_t sl, skiplist_level_t *path, size_t psz,
 	      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;
 
@@ -838,7 +840,7 @@ with the original.
 {
 
 	CHECK_SKIPLIST(skiplist);
-	
+
 	return copy_skiplist(XSKIPLIST(skiplist));
 }
 
@@ -861,7 +863,7 @@ DEFUN("skiplist-union", Fskiplist_union, 0, MANY, 0, /*
 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
@@ -977,11 +979,11 @@ may remove or reput the entry currently being processed by FUNCTION.
 	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;