apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yla...@apache.org
Subject svn commit: r1667420 - in /apr/apr/trunk: include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c
Date Tue, 17 Mar 2015 22:42:47 GMT
Author: ylavic
Date: Tue Mar 17 22:42:46 2015
New Revision: 1667420

URL: http://svn.apache.org/r1667420
Log:
skiplist: Introduce apr_skiplist_replace[_compare]().

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=1667420&r1=1667419&r2=1667420&view=diff
==============================================================================
--- apr/apr/trunk/include/apr_skiplist.h (original)
+++ apr/apr/trunk/include/apr_skiplist.h Tue Mar 17 22:42:46 2015
@@ -217,11 +217,37 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data);
 
 /**
+ * Add an element into the skip list using the specified comparison function
+ * removing the existing duplicates.
+ * @param sl The skip list
+ * @param data The element to insert
+ * @param comp The comparison function to use for placement into the skip list
+ * @param myfree A function to be called for each replaced element
+ * @remark If no comparison function has been set for the skip list, the element
+ * will not be inserted, none will be replaced, and NULL will be returned.
+ */
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
+                                    void *data, apr_skiplist_freefunc myfree,
+                                    apr_skiplist_compare comp);
+
+/**
+ * Add an element into the skip list using the existing comparison function
+ * removing the existing duplicates.
+ * @param sl The skip list
+ * @param data The element to insert
+ * @param myfree A function to be called for each removed duplicate
+ * @remark If no comparison function has been set for the skip list, the element
+ * will not be inserted, none will be replaced, and NULL will be returned.
+ */
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
+                                    void *data, apr_skiplist_freefunc myfree);
+
+/**
  * Remove an element from the skip list using the specified comparison function for
  * locating the element. In the case of duplicates, the 1st entry will be removed.
  * @param sl The skip list
  * @param data The element to remove
- * @param myfree A function to be called for each removed element
+ * @param myfree A function to be called for each removed duplicate
  * @param comp The comparison function to use for placement into the skip list
  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
  * will be returned.

Modified: apr/apr/trunk/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1667420&r1=1667419&r2=1667420&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_skiplist.c (original)
+++ apr/apr/trunk/tables/apr_skiplist.c Tue Mar 17 22:42:46 2015
@@ -201,7 +201,7 @@ static apr_skiplistnode *skiplist_new_no
     return m;
 }
 
-static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m)
+static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m)
 {
     return skiplist_qpush(&sl->nodes_q, m);
 }
@@ -304,8 +304,7 @@ static int skiplisti_find_compare(apr_sk
 {
     int count = 0;
     apr_skiplistnode *m;
-    m = sl->top;
-    while (m) {
+    for (m = sl->top; m; count++) {
         if (m->next) {
             int compared = comp(data, m->next->data);
             if (compared == 0) {
@@ -318,12 +317,10 @@ static int skiplisti_find_compare(apr_sk
             }
             if (compared > 0) {
                 m = m->next;
-                count++;
                 continue;
             }
         }
         m = m->down;
-        count++;
     }
     *ret = NULL;
     return count;
@@ -398,11 +395,16 @@ APR_DECLARE(void *) apr_skiplist_element
     return node->data;
 }
 
+/* forward declared */
+static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
+                            apr_skiplist_freefunc myfree);
+
 static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
-                                        apr_skiplist_compare comp, int add)
+                                        apr_skiplist_compare comp, int add,
+                                        apr_skiplist_freefunc myfree)
 {
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
-    int nh = 1, ch;
+    int ch, nh = 1;
 
     if (sl->preheight) {
         while (nh < sl->preheight && get_b_rand()) {
@@ -431,10 +433,26 @@ static apr_skiplistnode *insert_compare(
          */
         if (m->next) {
             int compared = comp(data, m->next->data);
-            if (compared == 0 && !add) {
-                /* Keep the existing element(s) */
-                skiplist_qclear(&sl->stack_q);
-                return NULL;
+            if (compared == 0) {
+                if (!add) {
+                    /* Keep the existing element(s) */
+                    skiplist_qclear(&sl->stack_q);
+                    return NULL;
+                }
+                if (add < 0) {
+                    /* Remove this element and continue with the next node
+                     * or the new top if the current one is also removed.
+                     */
+                    apr_skiplistnode *top = sl->top;
+                    skiplisti_remove(sl, m->next, myfree);
+                    if (top != sl->top) {
+                        m = sl->top;
+                        skiplist_qclear(&sl->stack_q);
+                        ch = sl->height;
+                        nh = ch + 1;
+                    }
+                    continue;
+                }
             }
             if (compared >= 0) {
                 m = m->next;
@@ -507,7 +525,7 @@ static apr_skiplistnode *insert_compare(
         li = ret;
         for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p))
{
             apr_skiplist *sli = (apr_skiplist *)p->data;
-            ni = insert_compare(sli, ret->data, sli->compare, add);
+            ni = insert_compare(sli, ret->data, sli->compare, add, myfree);
             li->nextindex = ni;
             ni->previndex = li;
             li = ni;
@@ -523,7 +541,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
     if (!comp) {
         return NULL;
     }
-    return insert_compare(sl, data, comp, 0);
+    return insert_compare(sl, data, comp, 0, NULL);
 }
 
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
@@ -537,7 +555,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
     if (!comp) {
         return NULL;
     }
-    return insert_compare(sl, data, comp, 1);
+    return insert_compare(sl, data, comp, 1, NULL);
 }
 
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
@@ -545,6 +563,22 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
     return apr_skiplist_add_compare(sl, data, sl->compare);
 }
 
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
+                                    void *data, apr_skiplist_freefunc myfree,
+                                    apr_skiplist_compare comp)
+{
+    if (!comp) {
+        return NULL;
+    }
+    return insert_compare(sl, data, comp, -1, myfree);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
+                                    void *data, apr_skiplist_freefunc myfree)
+{
+    return apr_skiplist_replace_compare(sl, data, myfree, sl->compare);
+}
+
 #if 0
 void skiplist_print_struct(apr_skiplist * sl, char *prefix)
 {
@@ -564,7 +598,8 @@ void skiplist_print_struct(apr_skiplist
 }
 #endif
 
-static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc
myfree)
+static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
+                            apr_skiplist_freefunc myfree)
 {
     apr_skiplistnode *p;
     if (!m) {
@@ -576,19 +611,20 @@ static int skiplisti_remove(apr_skiplist
     while (m->up) {
         m = m->up;
     }
-    while (m) {
+    do {
         p = m;
-        p->prev->next = p->next;/* take me out of the list */
+        /* take me out of the list */
+        p->prev->next = p->next;
         if (p->next) {
-            p->next->prev = p->prev;    /* take me out of the list */
+            p->next->prev = p->prev;
         }
         m = m->down;
         /* This only frees the actual data in the bottom one */
         if (!m && myfree && p->data) {
             myfree(p->data);
         }
-        skiplist_free_node(sl, p);
-    }
+        skiplist_put_node(sl, p);
+    } while (m);
     sl->size--;
     while (sl->top && sl->top->next == NULL) {
         /* While the row is empty and we are not on the bottom row */
@@ -597,7 +633,7 @@ static int skiplisti_remove(apr_skiplist
         if (sl->top) {
             sl->top->up = NULL; /* Make it think its the top */
         }
-        skiplist_free_node(sl, p);
+        skiplist_put_node(sl, p);
         sl->height--;
     }
     if (!sl->top) {
@@ -657,7 +693,7 @@ APR_DECLARE(void) apr_skiplist_remove_al
         }
         do {
             u = m->up;
-            skiplist_free_node(sl, m);
+            skiplist_put_node(sl, m);
             m = u;
         } while (m);
         m = p;

Modified: apr/apr/trunk/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/test/testskiplist.c?rev=1667420&r1=1667419&r2=1667420&view=diff
==============================================================================
--- apr/apr/trunk/test/testskiplist.c (original)
+++ apr/apr/trunk/test/testskiplist.c Tue Mar 17 22:42:46 2015
@@ -105,12 +105,16 @@ static void skiplist_insert(abts_case *t
     ABTS_STR_EQUAL(tc, "atfirst", val);
 }
 
+#define NUM_ADDS 100
 static void skiplist_add(abts_case *tc, void *data)
 {
     const char *val;
-    size_t i, n = skiplist_get_size(tc, skiplist);
+    size_t i, n = 0;
 
-    for (i = 0; i < 100; ++i) {
+    apr_skiplist_remove_all(skiplist, NULL);
+    ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+
+    for (i = 0; i < NUM_ADDS; ++i) {
         n++;
         apr_skiplist_add(skiplist, "daton");
         ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
@@ -141,10 +145,48 @@ static void skiplist_add(abts_case *tc,
     }
 }
 
+static void skiplist_replace(abts_case *tc, void *data)
+{
+    const char *val;
+    size_t n = skiplist_get_size(tc, skiplist);
+
+    n -= NUM_ADDS - 1;
+    apr_skiplist_replace(skiplist, "daton", NULL);
+    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 -= NUM_ADDS - 1;
+    apr_skiplist_replace(skiplist, "baton", NULL);
+    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 -= NUM_ADDS - 1;
+    apr_skiplist_replace(skiplist, "caton", NULL);
+    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 -= NUM_ADDS - 1;
+    apr_skiplist_replace(skiplist, "aaton", NULL);
+    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);
+
+    ABTS_TRUE(tc, n == 4);
+}
+
 static void skiplist_destroy(abts_case *tc, void *data)
 {
     apr_skiplist_destroy(skiplist, NULL);
-    ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+    ABTS_TRUE(tc, 0 == apr_skiplist_size(skiplist));
+    ABTS_TRUE(tc, 0 == apr_skiplist_height(skiplist));
+    ABTS_TRUE(tc, NULL == apr_skiplist_getlist(skiplist));
 }
 
 static void skiplist_size(abts_case *tc, void *data)
@@ -399,6 +441,7 @@ abts_suite *testskiplist(abts_suite *sui
     abts_run_test(suite, skiplist_dontfind, NULL);
     abts_run_test(suite, skiplist_insert, NULL);
     abts_run_test(suite, skiplist_add, NULL);
+    abts_run_test(suite, skiplist_replace, NULL);
     abts_run_test(suite, skiplist_destroy, NULL);
     abts_run_test(suite, skiplist_size, NULL);
     abts_run_test(suite, skiplist_remove, NULL);



Mime
View raw message