svn commit: r1611515 - in /apr/apr/trunk: include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c

[yl...@apache.org]

Author: ylavic
Date: Thu Jul 17 23:58:02 2014
New Revision: 1611515

URL: http://svn.apache.org/r1611515
Log:
Provide apr_skiplist_size/height/preheight() to get the corresponding values
in O(1), and apr_skiplist_set_preheight() to configure preheight mode.

Modified:
    apr/apr/trunk/include/apr_skiplist.h
    apr/apr/trunk/tables/apr_skiplist.c
    apr/apr/trunk/test/testskiplist.c

Modified: apr/apr/trunk/include/apr_skiplist.h
URL: http://svn.apache.org/viewvc/apr/apr/trunk/include/apr_skiplist.h?rev=1611515&r1=1611514&r2=1611515&view=diff
==============================================================================
--- apr/apr/trunk/include/apr_skiplist.h (original)
+++ apr/apr/trunk/include/apr_skiplist.h Thu Jul 17 23:58:02 2014
@@ -264,6 +264,40 @@ APR_DECLARE(void *) apr_skiplist_pop(apr
 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
 
 /**
+ * Return the size of the list (number of elements), in O(1).
+ * @param sl The skip list
+ */
+APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl);
+
+/**
+ * Return the height of the list (number of skip paths), in O(1).
+ * @param sl The skip list
+ */
+APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl);
+
+/**
+ * Return the predefined maximum height of the skip list.
+ * @param sl The skip list
+ */
+APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl);
+
+/**
+ * Set a predefined maximum height for the skip list.
+ * @param sl The skip list
+ * @param to The preheight to set, or a nul/negative value to disable.
+ * @remark When a preheight is used, the height of each inserted element is
+ * computed randomly up to this preheight instead of the current skip list's
+ * height plus one used by the default implementation. Using a preheight can
+ * probably ensure more fairness with long living elements (since with an
+ * adaptative height, former elements may have been created with a low height,
+ * hence a longest path to reach them while the skip list grows). On the other
+ * hand, the default behaviour (preheight <= 0) with a growing and decreasing
+ * maximum height is more adaptative/suitable for short living values.
+ * @note Should be called before any insertion/add.
+ */
+APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to);
+
+/**
  * Merge two skip lists.  XXX SEMANTICS
  * @param sl1 One of two skip lists to be merged
  * @param sl2 The other of two skip lists to be merged

Modified: apr/apr/trunk/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1611515&r1=1611514&r2=1611515&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_skiplist.c (original)
+++ apr/apr/trunk/tables/apr_skiplist.c Thu Jul 17 23:58:02 2014
@@ -25,12 +25,14 @@
 
 #include "apr_skiplist.h"
 
+#include <limits.h> /* for INT_MAX */
+
 struct apr_skiplist {
     apr_skiplist_compare compare;
     apr_skiplist_compare comparek;
     int height;
     int preheight;
-    int size;
+    size_t size;
     apr_skiplistnode *top;
     apr_skiplistnode *bottom;
     /* These two are needed for appending */
@@ -675,6 +677,26 @@ APR_DECLARE(void *) apr_skiplist_peek(ap
     return NULL;
 }
 
+APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
+{
+    return sl->size;
+}
+
+APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
+{
+    return sl->height;
+}
+
+APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
+{
+    return sl->preheight;
+}
+
+APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to)
+{
+    sl->preheight = (to > 0) ? to : 0;
+}
+
 static void skiplisti_destroy(void *vsl)
 {
     apr_skiplist_destroy((apr_skiplist *) vsl, NULL);

Modified: apr/apr/trunk/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/test/testskiplist.c?rev=1611515&r1=1611514&r2=1611515&view=diff
==============================================================================
--- apr/apr/trunk/test/testskiplist.c (original)
+++ apr/apr/trunk/test/testskiplist.c Thu Jul 17 23:58:02 2014
@@ -33,14 +33,14 @@
 static apr_pool_t *ptmp = NULL;
 static apr_skiplist *skiplist = NULL;
 
-/* apr_skiplist_size() is missing in 1.5.x, wrap it */
-static int apr_skiplist_size(apr_skiplist *sl)
+static int skiplist_get_size(abts_case *tc, apr_skiplist *sl)
 {
-    int size = 0;
+    size_t size = 0;
     apr_skiplistnode *n;
     for (n = apr_skiplist_getlist(sl); n; apr_skiplist_next(sl, &n)) {
         ++size;
     }
+    ABTS_TRUE(tc, size == apr_skiplist_size(sl));
     return size;
 }
 
@@ -75,53 +75,66 @@ static void skiplist_dontfind(abts_case 
 static void skiplist_insert(abts_case *tc, void *data)
 {
     const char *val;
-    int i;
+    int i, height = 0;
 
     for (i = 0; i < 10; ++i) {
         apr_skiplist_insert(skiplist, "baton");
-        ABTS_INT_EQUAL(tc, 1, apr_skiplist_size(skiplist));
+        ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "baton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, "baton", val);
+
+        if (height == 0) {
+            height = apr_skiplist_height(skiplist);
+        }
+        else {
+            ABTS_INT_EQUAL(tc, height, apr_skiplist_height(skiplist));
+        }
     }
 
     apr_skiplist_insert(skiplist, "foo");
-    ABTS_INT_EQUAL(tc, 2, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "foo", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "foo", val);
+
+    apr_skiplist_insert(skiplist, "atfirst");
+    ABTS_TRUE(tc, 3 == skiplist_get_size(tc, skiplist));
+    val = apr_skiplist_find(skiplist, "atfirst", NULL);
+    ABTS_PTR_NOTNULL(tc, val);
+    ABTS_STR_EQUAL(tc, "atfirst", val);
 }
 
 static void skiplist_add(abts_case *tc, void *data)
 {
     const char *val;
-    size_t i, n = apr_skiplist_size(skiplist);
+    size_t i, n = skiplist_get_size(tc, skiplist);
 
     for (i = 0; i < 100; ++i) {
         n++;
         apr_skiplist_add(skiplist, "daton");
-        ABTS_INT_EQUAL(tc, n, apr_skiplist_size(skiplist));
+        ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "daton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, "daton", val);
 
         n++;
         apr_skiplist_add(skiplist, "baton");
-        ABTS_INT_EQUAL(tc, n, apr_skiplist_size(skiplist));
+        ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "baton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, "baton", val);
 
         n++;
         apr_skiplist_add(skiplist, "caton");
-        ABTS_INT_EQUAL(tc, n, apr_skiplist_size(skiplist));
+        ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "caton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, "caton", val);
 
         n++;
         apr_skiplist_add(skiplist, "aaton");
-        ABTS_INT_EQUAL(tc, n, apr_skiplist_size(skiplist));
+        ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "aaton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, "aaton", val);
@@ -131,14 +144,14 @@ static void skiplist_add(abts_case *tc, 
 static void skiplist_destroy(abts_case *tc, void *data)
 {
     apr_skiplist_destroy(skiplist, NULL);
-    ABTS_INT_EQUAL(tc, 0, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 }
 
 static void skiplist_size(abts_case *tc, void *data)
 {
     const char *val;
 
-    ABTS_INT_EQUAL(tc, 0, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 
     apr_skiplist_insert(skiplist, "abc");
     apr_skiplist_insert(skiplist, "ghi");
@@ -153,7 +166,7 @@ static void skiplist_size(abts_case *tc,
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "def", val);
 
-    ABTS_INT_EQUAL(tc, 3, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 3 == skiplist_get_size(tc, skiplist));
     apr_skiplist_destroy(skiplist, NULL);
 }
 
@@ -161,28 +174,28 @@ static void skiplist_remove(abts_case *t
 {
     const char *val;
 
-    ABTS_INT_EQUAL(tc, 0, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 
     apr_skiplist_add(skiplist, "baton");
-    ABTS_INT_EQUAL(tc, 1, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
 
     apr_skiplist_add(skiplist, "baton");
-    ABTS_INT_EQUAL(tc, 2, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
 
     apr_skiplist_remove(skiplist, "baton", NULL);
-    ABTS_INT_EQUAL(tc, 1, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
 
     apr_skiplist_add(skiplist, "baton");
-    ABTS_INT_EQUAL(tc, 2, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
@@ -190,7 +203,7 @@ static void skiplist_remove(abts_case *t
     /* remove all "baton"s */
     while (apr_skiplist_remove(skiplist, "baton", NULL))
         ;
-    ABTS_INT_EQUAL(tc, 0, apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_EQUAL(tc, NULL, val);
 }
@@ -206,6 +219,9 @@ static void skiplist_random_loop(abts_ca
 
     ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&sl, ptmp));
     apr_skiplist_set_compare(sl, (void*)strcmp, (void*)strcmp);
+    apr_skiplist_set_preheight(sl, 7);
+    ABTS_INT_EQUAL(tc, 7, apr_skiplist_preheight(sl));
+
     batons = apr_palloc(ptmp, NUM_FIND * sizeof(char*));
 
     for (i = 0; i < NUM_FIND; ++i) {