You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2014/01/01 15:26:49 UTC
svn commit: r1554622 - in /subversion/trunk/subversion: include/svn_sorts.h
libsvn_fs_fs/index.c libsvn_fs_x/index.c libsvn_subr/sorts.c
Author: stefan2
Date: Wed Jan 1 14:26:48 2014
New Revision: 1554622
URL: http://svn.apache.org/r1554622
Log:
Add a private lookup API for sorted arrays. This one is easier
to use than svn_sort__bsearch_lower_bound as it will return
actual matches only, i.e. requires less post-processing for
certain callers.
* subversion/include/svn_sorts.h
(svn_sort__array_lookup): Declare the new private API function.
* subversion/libsvn_subr/sorts.c
(svn_sort__array_lookup): Implement it.
* subversion/libsvn_fs_fs/index.c
(get_p2l_entry_from_cached_page,
svn_fs_fs__p2l_entry_lookup): Simplify using the new API.
* subversion/libsvn_fs_x/index.c
(get_p2l_entry_from_cached_page,
p2l_entry_lookup): Ditto.
Modified:
subversion/trunk/subversion/include/svn_sorts.h
subversion/trunk/subversion/libsvn_fs_fs/index.c
subversion/trunk/subversion/libsvn_fs_x/index.c
subversion/trunk/subversion/libsvn_subr/sorts.c
Modified: subversion/trunk/subversion/include/svn_sorts.h
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/include/svn_sorts.h?rev=1554622&r1=1554621&r2=1554622&view=diff
==============================================================================
--- subversion/trunk/subversion/include/svn_sorts.h (original)
+++ subversion/trunk/subversion/include/svn_sorts.h Wed Jan 1 14:26:48 2014
@@ -184,6 +184,29 @@ svn_sort__bsearch_lower_bound(const apr_
const void *key,
int (*compare_func)(const void *, const void *));
+/* Find the lowest index at which the element @a *key should be inserted into
+ * the array @a array, according to the ordering defined by @a compare_func.
+ * The array must already be sorted in the ordering defined by @a compare_func.
+ * @a compare_func is defined as for the C stdlib function bsearch(); the
+ * @a key will always passed to it as the second parameter.
+ *
+ * Returns a reference to the array element at the insertion location if
+ * that matches @a key and return NULL otherwise. If you call this function
+ * multiple times for the same array and expect the results to often be
+ * consecutive array elements, provide @a hint. It should be initialized
+ * with -1 for the first call and receives the array index if the returned
+ * element. If the return value is NULL, @a *hint is the location where
+ * the respective key would be inserted.
+ *
+ * @note Private. For use by Subversion's own code only.
+ */
+void *
+svn_sort__array_lookup(const apr_array_header_t *array,
+ const void *key,
+ int *hint,
+ int (*compare_func)(const void *, const void *));
+
+
/* Insert a shallow copy of @a *new_element into the array @a array at the index
* @a insert_index, growing the array and shuffling existing elements along to
* make room.
Modified: subversion/trunk/subversion/libsvn_fs_fs/index.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/index.c?rev=1554622&r1=1554621&r2=1554622&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/index.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/index.c Wed Jan 1 14:26:48 2014
@@ -2320,25 +2320,17 @@ get_p2l_entry_from_cached_page(const voi
/* resolve all pointer values of in-cache data */
const apr_array_header_t *page = data;
apr_array_header_t *entries = apr_pmemdup(pool, page, sizeof(*page));
- int idx;
+ svn_fs_fs__p2l_entry_t *entry;
entries->elts = (char *)svn_temp_deserializer__ptr(page,
(const void *const *)&page->elts);
/* search of the offset we want */
- idx = svn_sort__bsearch_lower_bound(entries, &offset,
+ entry = svn_sort__array_lookup(entries, &offset, NULL,
(int (*)(const void *, const void *))compare_p2l_entry_offsets);
/* return it, if it is a perfect match */
- if (idx < entries->nelts)
- {
- svn_fs_fs__p2l_entry_t *entry
- = &APR_ARRAY_IDX(entries, idx, svn_fs_fs__p2l_entry_t);
- if (entry->offset == offset)
- return apr_pmemdup(pool, entry, sizeof(*entry));
- }
-
- return NULL;
+ return entry ? apr_pmemdup(pool, entry, sizeof(*entry)) : NULL;
}
/* Implements svn_cache__partial_getter_func_t for P2L index pages, copying
@@ -2385,25 +2377,14 @@ svn_fs_fs__p2l_entry_lookup(svn_fs_fs__p
p2l_entry_lookup_func, &offset, pool));
if (!is_cached)
{
- int idx;
-
/* do a standard index lookup. This is will automatically prefetch
* data to speed up future lookups. */
apr_array_header_t *entries;
SVN_ERR(p2l_index_lookup(&entries, rev_file, fs, revision, offset, pool));
/* Find the entry that we want. */
- idx = svn_sort__bsearch_lower_bound(entries, &offset,
+ *entry_p = svn_sort__array_lookup(entries, &offset, NULL,
(int (*)(const void *, const void *))compare_p2l_entry_offsets);
-
- /* return it, if it is a perfect match */
- if (idx < entries->nelts)
- {
- svn_fs_fs__p2l_entry_t *entry
- = &APR_ARRAY_IDX(entries, idx, svn_fs_fs__p2l_entry_t);
- if (entry->offset == offset)
- *entry_p = entry;
- }
}
return SVN_NO_ERROR;
Modified: subversion/trunk/subversion/libsvn_fs_x/index.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_x/index.c?rev=1554622&r1=1554621&r2=1554622&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_x/index.c (original)
+++ subversion/trunk/subversion/libsvn_fs_x/index.c Wed Jan 1 14:26:48 2014
@@ -2431,29 +2431,24 @@ get_p2l_entry_from_cached_page(const voi
/* resolve all pointer values of in-cache data */
const apr_array_header_t *page = data;
apr_array_header_t *entries = apr_pmemdup(pool, page, sizeof(*page));
- int idx;
+ svn_fs_x__p2l_entry_t *entry;
entries->elts = (char *)svn_temp_deserializer__ptr(page,
(const void *const *)&page->elts);
/* search of the offset we want */
- idx = svn_sort__bsearch_lower_bound(entries, &offset,
+ entry = svn_sort__array_lookup(entries, &offset, NULL,
(int (*)(const void *, const void *))compare_p2l_entry_offsets);
/* return it, if it is a perfect match */
- if (idx < entries->nelts)
+ if (entry)
{
- svn_fs_x__p2l_entry_t *entry
- = &APR_ARRAY_IDX(entries, idx, svn_fs_x__p2l_entry_t);
- if (entry->offset == offset)
- {
- svn_fs_x__p2l_entry_t *result
- = apr_pmemdup(pool, entry, sizeof(*result));
- result->items
- = (svn_fs_x__id_part_t *)svn_temp_deserializer__ptr(entries->elts,
+ svn_fs_x__p2l_entry_t *result
+ = apr_pmemdup(pool, entry, sizeof(*result));
+ result->items
+ = (svn_fs_x__id_part_t *)svn_temp_deserializer__ptr(entries->elts,
(const void *const *)&entry->items);
- return result;
- }
+ return result;
}
return NULL;
@@ -2493,8 +2488,6 @@ p2l_entry_lookup(svn_fs_x__p2l_entry_t *
svn_boolean_t is_cached = FALSE;
p2l_page_info_baton_t page_info;
- *entry_p = NULL;
-
/* look for this info in our cache */
SVN_ERR(get_p2l_keys(&page_info, &key, stream, fs, revision, offset, pool));
SVN_ERR(svn_cache__get_partial((void**)entry_p, &is_cached,
@@ -2502,25 +2495,14 @@ p2l_entry_lookup(svn_fs_x__p2l_entry_t *
p2l_entry_lookup_func, &offset, pool));
if (!is_cached)
{
- int idx;
-
/* do a standard index lookup. This is will automatically prefetch
* data to speed up future lookups. */
apr_array_header_t *entries;
SVN_ERR(p2l_index_lookup(&entries, stream, fs, revision, offset, pool));
/* Find the entry that we want. */
- idx = svn_sort__bsearch_lower_bound(entries, &offset,
+ *entry_p = svn_sort__array_lookup(entries, &offset, NULL,
(int (*)(const void *, const void *))compare_p2l_entry_offsets);
-
- /* return it, if it is a perfect match */
- if (idx < entries->nelts)
- {
- svn_fs_x__p2l_entry_t *entry
- = &APR_ARRAY_IDX(entries, idx, svn_fs_x__p2l_entry_t);
- if (entry->offset == offset)
- *entry_p = entry;
- }
}
return SVN_NO_ERROR;
Modified: subversion/trunk/subversion/libsvn_subr/sorts.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/sorts.c?rev=1554622&r1=1554621&r2=1554622&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_subr/sorts.c (original)
+++ subversion/trunk/subversion/libsvn_subr/sorts.c Wed Jan 1 14:26:48 2014
@@ -224,6 +224,40 @@ svn_sort__bsearch_lower_bound(const apr_
compare_func);
}
+void *
+svn_sort__array_lookup(const apr_array_header_t *array,
+ const void *key,
+ int *hint,
+ int (*compare_func)(const void *, const void *))
+{
+ void *result;
+ int idx;
+
+ /* If provided, try the index following *HINT (i.e. probably the last
+ * hit location) first. This speeds up linear scans. */
+ if (hint)
+ {
+ idx = *hint;
+ *hint = ++idx;
+ if (idx >= 0 && idx < array->nelts)
+ {
+ result = array->elts + idx * array->elt_size;
+ if (!compare_func(result, key))
+ return result;
+ }
+ }
+
+ idx = bsearch_lower_bound(key, array->elts, array->nelts, array->elt_size,
+ compare_func);
+ if (hint)
+ *hint = idx;
+ if (idx >= array->nelts)
+ return NULL;
+
+ result = array->elts + idx * array->elt_size;
+ return compare_func(result, key) ? NULL : result;
+}
+
void
svn_sort__array_insert(apr_array_header_t *array,
const void *new_element,