On Sat, Mar 14, 2015 at 1:09 AM, <yla...@apache.org> wrote: > Author: ylavic > Date: Sat Mar 14 00:09:32 2015 > New Revision: 1666619 > > URL: http://svn.apache.org/r1666619 > Log: > mpm_motorz: follow up to r1666482. > We only need one compare function for add semantic with apr_skiplist_insert() > and unique timers (pointers). It also works with apr_skiplist_remove() and > apr_skiplist_find(). > > Modified: > httpd/httpd/trunk/server/mpm/motorz/motorz.c > > Modified: httpd/httpd/trunk/server/mpm/motorz/motorz.c > URL: > http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/motorz/motorz.c?rev=1666619&r1=1666618&r2=1666619&view=diff > ============================================================================== > --- httpd/httpd/trunk/server/mpm/motorz/motorz.c (original) > +++ httpd/httpd/trunk/server/mpm/motorz/motorz.c Sat Mar 14 00:09:32 2015 > @@ -64,21 +64,18 @@ static motorz_core_t *motorz_core_get() > return g_motorz_core; > } > > -static int indexing_comp(void *a, void *b) > +static int timer_comp(void *a, void *b) > { > - apr_time_t t1 = (apr_time_t) (((motorz_timer_t *) a)->expires); > - apr_time_t t2 = (apr_time_t) (((motorz_timer_t *) b)->expires); > - AP_DEBUG_ASSERT(t1); > - AP_DEBUG_ASSERT(t2); > - return ((t1 < t2) ? -1 : 1); > -} > - > -static int indexing_compk(void *ac, void *b) > -{ > - apr_time_t *t1 = (apr_time_t *) ac; > - apr_time_t t2 = (apr_time_t) (((motorz_timer_t *) b)->expires); > - AP_DEBUG_ASSERT(t2); > - return ((*t1 < t2) ? -1 : 1); > + if (a != b) { > + apr_time_t t1 = (apr_time_t) (((motorz_timer_t *) a)->expires); > + apr_time_t t2 = (apr_time_t) (((motorz_timer_t *) b)->expires); > + AP_DEBUG_ASSERT(t1); > + AP_DEBUG_ASSERT(t2); > + return ((t1 < t2) ? -1 : 1); > + } > + else { > + return 0; > + } > }
I expected this compare function to work with apr_skiplist_remove() but actually it does not. The goal was to match the given pointer only (and not any other duplicate!), but by returning +1 when a != b && t1 == t2, we may skip timers inserted first should any duplicate be inserted later with a higher eight. For example, the below is the gdb output (dump_dipklist) after 10 duplicates have been inserted, where each 2-tuple is the address of the node (0x...,) containing the address of the element (,000000...): (gdb) dump_skiplist skiplist skiplist@0x69aba0: size=10: height=3 (0x69b008,000000000000) (0x6ac3c0,000000000000) (0x6ac628,000000000000) (0x69b048,00000069b000) (0x6ac338,00000069b088) (0x6ac380,0000006ac378) (0x6ac400,0000006ac378) (0x6ac448,0000006ac440) (0x6ac490,0000006ac488) (0x6ac4d0,0000006ac488) (0x6ac518,0000006ac510) (0x6ac560,0000006ac558) (0x6ac5a8,0000006ac5a0) (0x6ac5e8,0000006ac5a0) (0x6ac668,0000006ac5a0) (0x6ac6b0,0000006ac6a8) (0x6ac6f0,0000006ac6a8) (0x6ac738,0000006ac730) (0x6ac778,0000006ac730) If e.g. we now try to remove the element (0x6ac448,0000006ac440), starting at the top (0x6ac628,000000000000), we will jump directly next to (0x6ac668,0000006ac5a0), then down (no next) to (0x6ac5e8,0000006ac5a0), then next to (0x6ac6f0,0000006ac6a8), then next to (0x6ac778,0000006ac730), then down (no next) to (0x6ac738,0000006ac730), and finally (no next, no down) to NULL. All the elements (all duplicates) between the top and (0x6ac668,0000006ac5a0) have been skipped, hence we had no chance to find (0x6ac448,0000006ac440), because at least one element was inserted later (exactly 4 here) with a higher eight. This is not an issue about insert vs add semantic, with both functions we still need a "reliable" compare function to remove the exact (requested) timer, and I see no way to build one... Thoughts?
