Hi,
there seems to be no way to disable indexing in skiplist
implementationn whereas the user may not need/use it (eg. httpd uses
only insert(), pop() and peek()).
When indexing is enabled (always for now),
apr_skiplist_insert[_compare]() requires an additional insert to the
index(es) for all the values inserted, which is useless (and quite
costly) if skiplist_find_compare() or skiplist_remove_compare() are
never used.
Hence I propose the following change :
Index: srclib/apr/tables/apr_skiplist.c
===================================================================
--- srclib/apr/tables/apr_skiplist.c (revision 1628634)
+++ srclib/apr/tables/apr_skiplist.c (working copy)
@@ -228,11 +228,7 @@ static int indexing_compk(void *ac, void *b)
APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
{
- apr_skiplist *sl;
skiplisti_init(s, p);
- sl = *s;
- skiplisti_init(&(sl->index), p);
- apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
return APR_SUCCESS;
}
@@ -256,10 +252,16 @@ APR_DECLARE(void) apr_skiplist_add_index(apr_skipl
apr_skiplistnode *m;
apr_skiplist *ni;
int icount = 0;
- apr_skiplist_find(sl->index, (void *)comp, &m);
- if (m) {
- return; /* Index already there! */
+ if (!sl->index) {
+ skiplisti_init(&sl->index, sl->pool);
+ apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
}
+ else {
+ apr_skiplist_find(sl->index, (void *)comp, &m);
+ if (m) {
+ return; /* Index already there! */
+ }
+ }
skiplisti_init(&ni, sl->pool);
apr_skiplist_set_compare(ni, comp, compk);
/* Build the new index... This can be expensive! */
so that no index will be created unless the caller calls
apr_skiplist_add_index() explicitly (or apr_skiplist_set_compare()
twice).
This is an easy change that requires no API change (calling
apr_skiplist_add_index() to require an index is quite logical, and
1.5.x aware :p ), but I guess it can make existing code (taking
advantage of the index) less optimal.
So maybe a new apr_skiplist_create() with flags is better, or creating
(and populating) it on the first call to find/remove_compare(), or ...
Let me know.
Regards,
Yann.
