Line data    Source code

       1              : /**
       2              :  * Copyright (c) 2025 Huawei Technologies Co., Ltd.
       3              :  * This program is free software, you can redistribute it and/or modify it under the terms and conditions of
       4              :  * CANN Open Software License Agreement Version 2.0 (the "License").
       5              :  * Please refer to the License for details. You may not use this file except in compliance with the License.
       6              :  * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED,
       7              :  * INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY, OR FITNESS FOR A PARTICULAR PURPOSE.
       8              :  * See LICENSE in the root of the software repository for the full text of the License.
       9              :  */
      10              : #ifndef C_BASE_BINARY_SEARCH_H
      11              : #define C_BASE_BINARY_SEARCH_H
      12              : #include "c_base.h"
      13              : 
      14              : #ifdef __cplusplus
      15              : extern "C" {
      16              : #endif
      17              : 
      18              : typedef void* (*FnBinaryGet)(void* appInfo, size_t id);
      19              : typedef int (*FnBinaryCompare)(void* a, void* b, void* appInfo);
      20              : 
      21            0 : static inline int BinarySearchClosest(
      22              :     void* appInfo, size_t size, void* key, FnBinaryGet fnBinaryGet, FnBinaryCompare fnComp, size_t* closestIndex)
      23              : {
      24            0 :     if (size == 0) {
      25            0 :         *closestIndex = 0;
      26            0 :         return -1;
      27              :     }
      28              : 
      29            0 :     size_t left = 0;
      30            0 :     size_t right = size - 1;
      31              :     size_t mid;
      32            0 :     int compRet = 0;
      33            0 :     while (left <= right) {
      34            0 :         mid = (left + right) >> 1;
      35            0 :         void* midData = fnBinaryGet(appInfo, mid);
      36            0 :         compRet = fnComp(key, midData, appInfo);
      37            0 :         if (compRet > 0) {
      38            0 :             left = mid + 1;
      39            0 :         } else if (compRet < 0) {
      40            0 :             if (mid == 0) {
      41            0 :                 break;
      42              :             }
      43            0 :             right = mid - 1;
      44              :         } else {
      45            0 :             *closestIndex = mid;
      46            0 :             return 0;
      47              :         }
      48              :     }
      49            0 :     *closestIndex = mid;
      50            0 :     return compRet;
      51              : };
      52              : 
      53              : #ifdef __cplusplus
      54              : }
      55              : #endif
      56              : #endif // C_BASE_BINARY_SEARCH_H