diff options
author | Thomas Haller <thaller@redhat.com> | 2022-10-07 12:25:58 +0200 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2022-10-11 08:59:48 +0200 |
commit | 28fa48aee44cae8349b3614ee2b9c1837fea0074 (patch) | |
tree | 5f3ec7ee5ee468a898a3b6e885de7b3b56408298 | |
parent | 2f0808a6108c0bc8f8ec6192772494659c9a1288 (diff) |
glib-aux: add an inlinable version of nm_array_find_bsearch()
To implement binary search is not very hard. It's almost easy enough to
just open-code it, without using the existing nm_array_find_bsearch() function.
In particular, because nm_array_find_bsearch() won't be inlined,
and thus it is slower than implementing it by hand.
Add nm_array_find_bsearch_inline() as a variant that will be inlined.
This actually is as fast as reimplementing it by hand (I measured),
which takes away any reason to avoid the function.
However, our headers get huge. That may be a problem for complication
time. To counter that a bit, only define the function when the caller
requests it with a NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE define.
-rw-r--r-- | src/libnm-glib-aux/nm-shared-utils.c | 34 | ||||
-rw-r--r-- | src/libnm-glib-aux/nm-shared-utils.h | 53 |
2 files changed, 56 insertions, 31 deletions
diff --git a/src/libnm-glib-aux/nm-shared-utils.c b/src/libnm-glib-aux/nm-shared-utils.c index f60ae1f2d6..66eb17e709 100644 --- a/src/libnm-glib-aux/nm-shared-utils.c +++ b/src/libnm-glib-aux/nm-shared-utils.c @@ -3,6 +3,8 @@ * Copyright (C) 2016 Red Hat, Inc. */ +#define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE + #include "libnm-glib-aux/nm-default-glib-i18n-lib.h" #include "nm-shared-utils.h" @@ -3943,37 +3945,7 @@ nm_array_find_bsearch(gconstpointer list, GCompareDataFunc cmpfcn, gpointer user_data) { - gssize imax; - gssize imid; - gssize imin; - int cmp; - - nm_assert(list || len == 0); - nm_assert(cmpfcn); - nm_assert(elem_size > 0); - - imin = 0; - if (len == 0) - return ~imin; - - imax = len - 1; - - while (imin <= imax) { - imid = imin + (imax - imin) / 2; - - cmp = cmpfcn(&((const char *) list)[elem_size * imid], needle, user_data); - if (cmp == 0) - return imid; - - if (cmp < 0) - imin = imid + 1; - else - imax = imid - 1; - } - - /* return the inverse of @imin. This is a negative number, but - * also is ~imin the position where the value should be inserted. */ - return ~imin; + return nm_array_find_bsearch_inline(list, len, elem_size, needle, cmpfcn, user_data); } /*****************************************************************************/ diff --git a/src/libnm-glib-aux/nm-shared-utils.h b/src/libnm-glib-aux/nm-shared-utils.h index 3383e6d03f..c1325a8c41 100644 --- a/src/libnm-glib-aux/nm-shared-utils.h +++ b/src/libnm-glib-aux/nm-shared-utils.h @@ -2135,6 +2135,57 @@ gssize nm_ptrarray_find_bsearch_range(gconstpointer *list, NULL); \ }) +/*****************************************************************************/ + +#ifdef NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE +/** + * nm_array_find_bsearch_inline: + * + * An inlined version of nm_array_find_bsearch(). See there. + * Define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE to get it. + */ +_nm_always_inline static inline gssize +nm_array_find_bsearch_inline(gconstpointer list, + gsize len, + gsize elem_size, + gconstpointer needle, + GCompareDataFunc cmpfcn, + gpointer user_data) +{ + gssize imax; + gssize imid; + gssize imin; + int cmp; + + nm_assert(list || len == 0); + nm_assert(cmpfcn); + nm_assert(elem_size > 0); + + imin = 0; + if (len == 0) + return ~imin; + + imax = len - 1; + + while (imin <= imax) { + imid = imin + (imax - imin) / 2; + + cmp = cmpfcn(&((const char *) list)[elem_size * imid], needle, user_data); + if (cmp == 0) + return imid; + + if (cmp < 0) + imin = imid + 1; + else + imax = imid - 1; + } + + /* return the inverse of @imin. This is a negative number, but + * also is ~imin the position where the value should be inserted. */ + return ~imin; +} +#endif + gssize nm_array_find_bsearch(gconstpointer list, gsize len, gsize elem_size, @@ -2142,6 +2193,8 @@ gssize nm_array_find_bsearch(gconstpointer list, GCompareDataFunc cmpfcn, gpointer user_data); +/*****************************************************************************/ + gssize nm_utils_ptrarray_find_first(gconstpointer *list, gssize len, gconstpointer needle); /*****************************************************************************/ |