On Sat, Jun 24, 2017 at 05:01:50PM -0400, Lance Richardson wrote:
> Skiplist implementation intended for use in the IDL compound indexes
> feature.
>
> Signed-off-by: Esteban Rodriguez Betancourt <[email protected]>
> Co-authored-by: Lance Richardson <[email protected]>
> Signed-off-by: Lance Richardson <[email protected]>
Thanks for reviving this series.
I have a few style suggestions, see the following incremental.
My only concern here is the following declaration in skiplist_insert()
and skiplist_delete(). Because of the semantics of initialization in C,
this means that, on a 64-bit system, this will always memset 33*8 == 264
bytes of memory to zero on each invocation. Can we avoid the
initialization?
struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1] = { NULL };
Thanks,
Ben.
--8<--------------------------cut here-------------------------->8--
diff --git a/lib/skiplist.c b/lib/skiplist.c
index e4160884acb9..9077fa5cd55b 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -150,7 +150,7 @@ skiplist_find(struct skiplist *sl, const void *value)
/*
* Determines the level for a skiplist node. Computes level N with
- * probabilty P(N) = 1/(2**(N+1)) in the range 0..32, with the returned
+ * probability P(N) = 1/(2**(N+1)) in the range 0..32, with the returned
* level clamped at the current skiplist height plus 1.
*/
static int
diff --git a/lib/skiplist.h b/lib/skiplist.h
index b714e868b4ee..1133202c0efc 100644
--- a/lib/skiplist.h
+++ b/lib/skiplist.h
@@ -17,15 +17,15 @@
#ifndef LIB_SKIPLIST_H_
#define LIB_SKIPLIST_H_
-#include<stdbool.h>
-#include<stdint.h>
-#include<stdlib.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
/*
* Skiplist key comparison function.
*/
-typedef int
- (skiplist_comparator)(const void *a, const void *b, const void *conf);
+typedef int skiplist_comparator(const void *a, const void *b,
+ const void *conf);
struct skiplist_node;
@@ -33,8 +33,8 @@ struct skiplist;
#define SKIPLIST_FOR_EACH (SKIPLIST_NODE, SKIPLIST) \
for (SKIPLIST_NODE = skiplist_first(SKIPLIST); \
- SKIPLIST_NODE; \
- SKIPLIST_NODE = skiplist_next(SKIPLIST_NODE))
+ SKIPLIST_NODE; \
+ SKIPLIST_NODE = skiplist_next(SKIPLIST_NODE))
struct skiplist *skiplist_create(skiplist_comparator *object_comparator,
void *configuration);
@@ -48,4 +48,5 @@ struct skiplist_node *skiplist_forward_to(struct skiplist *sl,
struct skiplist_node *skiplist_first(struct skiplist *sl);
struct skiplist_node *skiplist_next(struct skiplist_node *node);
void skiplist_destroy(struct skiplist *sl, void (*func)(void *));
+
#endif /* LIB_SKIPLIST_H_ */
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
