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