aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHanspeter Portner <dev@open-music-kontrollers.ch>2019-04-03 21:40:35 +0200
committerHanspeter Portner <dev@open-music-kontrollers.ch>2019-04-03 21:40:35 +0200
commitf635906c5b15708e2a337af0eec1a650f91a547d (patch)
treea4790c5586cb56d8c8820fbc7de1a0c1f860faa3
parent2051e564e78c3bb18559b0e1cb9338251f4e3a96 (diff)
downloadprops.lv2-f635906c5b15708e2a337af0eec1a650f91a547d.tar.xz
Revert "migrate brom bsearch to linear probing."
This reverts commit fca36e5ef63481463f4d27d14894e84ad4a2a811.
-rw-r--r--props.h78
1 files changed, 45 insertions, 33 deletions
diff --git a/props.h b/props.h
index 3f1dd99..6f28959 100644
--- a/props.h
+++ b/props.h
@@ -232,40 +232,52 @@ _props_restoring_set(props_t *props)
atomic_store_explicit(&props->restoring, true, memory_order_release);
}
-static inline props_impl_t *
-_props_impl_get(props_t *props, LV2_URID property)
+static inline void
+_props_qsort(props_impl_t *A, int n)
{
- for(unsigned i = 0, idx = (property + i) % props->nimpls;
- i < props->nimpls;
- i++, idx = (property + i) % props->nimpls)
+ if(n < 2)
+ return;
+
+ const props_impl_t *p = A;
+
+ int i = -1;
+ int j = n;
+
+ while(true)
{
- props_impl_t *impl = &props->impls[idx];
+ do {
+ i += 1;
+ } while(A[i].property < p->property);
- if(impl->property == property)
- {
- return impl;
- }
+ do {
+ j -= 1;
+ } while(A[j].property > p->property);
+
+ if(i >= j)
+ break;
+
+ const props_impl_t tmp = A[i];
+ A[i] = A[j];
+ A[j] = tmp;
}
- return NULL;
+ _props_qsort(A, j + 1);
+ _props_qsort(A + j + 1, n - j - 1);
}
static inline props_impl_t *
-_props_impl_add(props_t *props, LV2_URID property)
+_props_bsearch(props_t *props, LV2_URID property)
{
- for(unsigned i = 0, idx = (property + i) % props->nimpls;
- i < props->nimpls;
- i++, idx = (property + i) % props->nimpls)
- {
- props_impl_t *impl = &props->impls[idx];
+ props_impl_t *base = props->impls;
- if(impl->property == 0)
- {
- return impl;
- }
+ for(int N = props->nimpls, half; N > 1; N -= half)
+ {
+ half = N/2;
+ props_impl_t *dst = &base[half];
+ base = (dst->property > property) ? base : dst;
}
- return NULL;
+ return (base->property == property) ? base : NULL;
}
static inline LV2_Atom_Forge_Ref
@@ -452,7 +464,7 @@ static inline int
_props_impl_init(props_t *props, props_impl_t *impl, const props_def_t *def,
void *value_base, void *stash_base, LV2_URID_Map *map)
{
- if(!impl || !def->property || !def->type)
+ if(!def->property || !def->type)
return 0;
const LV2_URID type = map->map(map->handle, def->type);
@@ -571,14 +583,14 @@ props_init(props_t *props, const char *subject,
int status = 1;
for(unsigned i = 0; i < props->nimpls; i++)
{
- const props_def_t *def = &defs[i];
- const LV2_URID property = map->map(map->handle, def->property);
- props_impl_t *impl = _props_impl_add(props, property);
+ props_impl_t *impl = &props->impls[i];
status = status
- && _props_impl_init(props, impl, def, value_base, stash_base, map);
+ && _props_impl_init(props, impl, &defs[i], value_base, stash_base, map);
}
+ _props_qsort(props->impls, props->nimpls);
+
return status;
}
@@ -659,7 +671,7 @@ props_advance(props_t *props, LV2_Atom_Forge *forge, uint32_t frames,
}
else if(property->atom.type == props->urid.atom_urid)
{
- props_impl_t *impl = _props_impl_get(props, property->body);
+ props_impl_t *impl = _props_bsearch(props, property->body);
if(impl)
{
@@ -719,7 +731,7 @@ props_advance(props_t *props, LV2_Atom_Forge *forge, uint32_t frames,
return 0;
}
- props_impl_t *impl = _props_impl_get(props, property->body);
+ props_impl_t *impl = _props_bsearch(props, property->body);
if(impl && (impl->access == props->urid.patch_writable) )
{
_props_impl_set(props, impl, value->type, value->size,
@@ -785,7 +797,7 @@ props_advance(props_t *props, LV2_Atom_Forge *forge, uint32_t frames,
const LV2_URID property = prop->key;
const LV2_Atom *value = &prop->value;
- props_impl_t *impl = _props_impl_get(props, property);
+ props_impl_t *impl = _props_bsearch(props, property);
if(impl && (impl->access == props->urid.patch_writable) )
{
_props_impl_set(props, impl, value->type, value->size,
@@ -813,7 +825,7 @@ static inline void
props_set(props_t *props, LV2_Atom_Forge *forge, uint32_t frames,
LV2_URID property, LV2_Atom_Forge_Ref *ref)
{
- props_impl_t *impl = _props_impl_get(props, property);
+ props_impl_t *impl = _props_bsearch(props, property);
if(impl)
{
@@ -840,7 +852,7 @@ props_get(props_t *props, LV2_Atom_Forge *forge, uint32_t frames,
static inline void
props_stash(props_t *props, LV2_URID property)
{
- props_impl_t *impl = _props_impl_get(props, property);
+ props_impl_t *impl = _props_bsearch(props, property);
if(impl)
_props_impl_stash(props, impl);
@@ -863,7 +875,7 @@ props_map(props_t *props, const char *uri)
static inline const char *
props_unmap(props_t *props, LV2_URID property)
{
- props_impl_t *impl = _props_impl_get(props, property);
+ props_impl_t *impl = _props_bsearch(props, property);
if(impl)
return impl->def->property;