selftest: enable py3 for samba.tests.blackbox.check_output

[samba.git] / lib / util / binsearch.h

diff --git a/lib/util/binsearch.h b/lib/util/binsearch.h
index ac839900728354213c33ddb30f391200143a2bee..8ae9da2961f1771490281574e7524b4396f539a4 100644 (file)
--- a/lib/util/binsearch.h
+++ b/lib/util/binsearch.h
@@ -5,18 +5,22 @@
 
    Copyright (C) Andrew Tridgell 2009
 
-   This program is free software; you can redistribute it and/or modify
-   it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; either version 3 of the License, or
-   (at your option) any later version.
+     ** NOTE! The following LGPL license applies to the binsearch.h
+     ** header. This does NOT imply that all of Samba is released
+     ** under the LGPL
 
-   This program is distributed in the hope that it will be useful,
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-   GNU General Public License for more details.
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
 
-   You should have received a copy of the GNU General Public License
-   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
 */
 
 #ifndef _BINSEARCH_H
@@ -65,4 +69,53 @@
                if (_r < 0) _e = _i - 1; else _b = _i + 1; \
        }} } while (0)
 
+/*
+  like BINARY_ARRAY_SEARCH_P, but assumes that the array is an array
+  of elements, rather than pointers to structures
+
+  result points to the found structure, or NULL
+ */
+#define BINARY_ARRAY_SEARCH_V(array, array_size, target, comparison_fn, result) do { \
+       int32_t _b, _e; \
+       (result) = NULL; \
+       if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) {       \
+               int32_t _i = (_b+_e)/2; \
+               int _r = comparison_fn(target, array[_i]); \
+               if (_r == 0) { (result) = &array[_i]; break; } \
+               if (_r < 0) _e = _i - 1; else _b = _i + 1; \
+       }} } while (0)
+
+
+/*
+  like BINARY_ARRAY_SEARCH_V, but if an exact result is not found, the 'next'
+  argument will point to the element after the place where the exact result
+  would have been. If an exact result is found, 'next' will be NULL. If the
+  target is beyond the end of the list, both 'exact' and 'next' will be NULL.
+  Unlike other binsearch macros, where there are several elements that compare
+  the same, the exact result will always point to the first one.
+
+  If you don't care to distinguish between the 'greater than' and 'equals'
+  cases, you can use the same pointer for both 'exact' and 'next'.
+
+  As with all the binsearch macros, the comparison function is always called
+  with the search term first.
+ */
+#define BINARY_ARRAY_SEARCH_GTE(array, array_size, target, comparison_fn, \
+                               exact, next) do {               \
+       int32_t _b, _e;                                         \
+       (exact) = NULL; (next) = NULL;                  \
+       if ((array_size) > 0) {                                 \
+               for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
+                       int32_t _i = (_b + _e) / 2;                     \
+                       int _r = comparison_fn(target, &array[_i]); \
+                       if (_r == 0) {                                  \
+                               (exact) = &array[_i];                   \
+                               _e = _i - 1;                            \
+                       } else if (_r < 0) { _e = _i - 1;               \
+                       } else  { _b = _i + 1; }                        \
+               }                                                       \
+               if ((exact) == NULL &&_b < (array_size)) {              \
+                       (next) = &array[_b];                            \
+       } } } while (0)
+
 #endif