c25356d5978632df6203437e1953bcb29e0c736fTimo Sirainen#ifndef BSEARCH_INSERT_POS_H
c25356d5978632df6203437e1953bcb29e0c736fTimo Sirainen#define BSEARCH_INSERT_POS_H
8b1ff8af3123607dde63c516e007b47f6519c69aTimo Sirainen
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody/* Binary search template - getdata must be the name of a pure function
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody or a function-like macro that takes the two obvious parameters. */
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody#define BINARY_NUMERIC_SEARCH(getdata, data, count, value, idx_r) \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen unsigned int idx, left_idx, right_idx; \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen \
25480af2e21cf136e461ec802177f52b43154485Timo Sirainen i_assert((count) < INT_MAX); \
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody left_idx = 0; right_idx = (count); \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen while (left_idx < right_idx) { \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen idx = (left_idx + right_idx) / 2; \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen \
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody if (getdata(data, idx) < (value)) \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen left_idx = idx+1; \
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody else if (getdata(data, idx) > (value))\
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen right_idx = idx; \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen else { \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen *(idx_r) = idx; \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen return TRUE; \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen } \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen } \
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen return FALSE
810bf6e564ebef9655fc0ca3b5273fbb6022c098Timo Sirainen
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody#define BINARY_SEARCH_ARRAY_GET(array, index) ((array)[(index)])
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody#define BINARY_NUMBER_SEARCH(data, count, value, idx_r) \
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody BINARY_NUMERIC_SEARCH(BINARY_SEARCH_ARRAY_GET, data, count, value, idx_r);
1f0b3ea95f45146b6860a37f43bc02b62891e354Phil Carmody
9f5f6bdc3fd1304720b5d541bc31eb21417af6cbTimo Sirainen/* If key is found, returns TRUE and sets idx_r to the position where the key
9f5f6bdc3fd1304720b5d541bc31eb21417af6cbTimo Sirainen was found. If key isn't found, returns FALSE and sets idx_r to the position
9f5f6bdc3fd1304720b5d541bc31eb21417af6cbTimo Sirainen where the key should be inserted. */
b66d803de86bfb411165b3465b0d9ef64ecfe2a1Timo Sirainenbool ATTR_NOWARN_UNUSED_RESULT
b66d803de86bfb411165b3465b0d9ef64ecfe2a1Timo Sirainenbsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen size_t size, int (*cmp)(const void *, const void *),
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen unsigned int *idx_r);
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen#define bsearch_insert_pos(key, base, nmemb, size, cmp, idx_r) \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen bsearch_insert_pos(key, base, nmemb, size + \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen typeof(const typeof(*base) *))), \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen (int (*)(const void *, const void *))cmp, idx_r)
8b1ff8af3123607dde63c516e007b47f6519c69aTimo Sirainen
b66d803de86bfb411165b3465b0d9ef64ecfe2a1Timo Sirainenbool ATTR_NOWARN_UNUSED_RESULT
b66d803de86bfb411165b3465b0d9ef64ecfe2a1Timo Sirainenarray_bsearch_insert_pos_i(const struct array *array, const void *key,
b66d803de86bfb411165b3465b0d9ef64ecfe2a1Timo Sirainen int (*cmp)(const void *, const void *),
b66d803de86bfb411165b3465b0d9ef64ecfe2a1Timo Sirainen unsigned int *idx_r);
91f07a54b8102a604dd6410831a73e917a20a06cTimo Sirainen#define array_bsearch_insert_pos(array, key, cmp, idx_r) \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen array_bsearch_insert_pos_i(&(array)->arr + \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen typeof(*(array)->v))), \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen (const void *)key, (int (*)(const void *, const void *))cmp, idx_r)
0f184ee80e97f8a8312e9fab4f7f5a9d2187a18fTimo Sirainen
8b1ff8af3123607dde63c516e007b47f6519c69aTimo Sirainen#endif