1 /* 2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved. 3 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without modification, 6 * are permitted provided that the following conditions are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright notice, this list of 9 * conditions and the following disclaimer. 10 * 11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list 12 * of conditions and the following disclaimer in the documentation and/or other materials 13 * provided with the distribution. 14 * 15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used 16 * to endorse or promote products derived from this software without specific prior written 17 * permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _LOS_BINARYTREE_PRI_H 33 #define _LOS_BINARYTREE_PRI_H 34 35 #include "los_typedef.h" 36 #ifdef __cplusplus 37 #if __cplusplus 38 extern "C" { 39 #endif /* __cplusplus */ 40 #endif /* __cplusplus */ 41 42 typedef struct tagBinNode { 43 struct tagBinNode *left; 44 struct tagBinNode *right; 45 UINT32 nodeID; 46 CHAR keyValue[0]; 47 } BinNode; 48 49 typedef struct { 50 BinNode leaf; 51 UINTPTR linkReg1; 52 UINTPTR linkReg2; 53 UINTPTR linkReg3; 54 } LinkRegNode; 55 56 #define LR_COUNT 4096 57 extern LinkRegNode g_linkRegNode[LR_COUNT]; 58 extern UINT32 g_linkRegNodeIndex; 59 extern LinkRegNode *g_linkRegRoot; 60 61 typedef struct { 62 BinNode leaf; 63 UINTPTR addr; 64 } AddrNode; 65 66 #define ADDR_COUNT 40960 67 extern AddrNode g_addrNode[ADDR_COUNT]; 68 extern UINT32 g_addrNodeIndex; 69 extern AddrNode *g_addrRoot; 70 71 typedef struct { 72 BinNode leaf; 73 UINT32 reqSize; 74 } ReqSizeNode; 75 76 #define REQ_SIZE_COUNT 4096 77 extern ReqSizeNode g_reqSizeNode[REQ_SIZE_COUNT]; 78 extern UINT32 g_reqSizeNodeIndex; 79 extern ReqSizeNode *g_reqSizeRoot; 80 81 typedef struct { 82 BinNode leaf; 83 UINT32 taskID; 84 } TaskIDNode; 85 86 #define TASK_ID_COUNT 1024 87 88 extern UINT32 OsBinTreeInsert(const VOID *node, UINT32 nodeLen, BinNode **leaf, 89 BinNode *(*GetMyBinNode)(UINT32 *nodeID), 90 INT32 (*CompareNode)(const VOID *node1, const VOID *node2)); 91 92 extern INT32 OsCompareLRNode(const VOID *node1, const VOID *node2); 93 extern BinNode *OsGetLRBinNode(UINT32 *nodeID); 94 95 extern INT32 OsCompareAddrNode(const VOID *node1, const VOID *node2); 96 extern BinNode *OsGetAddrBinNode(UINT32 *nodeID); 97 98 extern INT32 OsCompareReqSizeNode(const VOID *node1, const VOID *node2); 99 extern BinNode *OsGetReqSizeBinNode(UINT32 *nodeID); 100 101 extern INT32 OsCompareTaskIDNode(const VOID *node1, const VOID *node2); 102 extern BinNode *OsGetTaskIDBinNode(UINT32 *nodeID); 103 104 #ifdef __cplusplus 105 #if __cplusplus 106 } 107 #endif /* __cplusplus */ 108 #endif /* __cplusplus */ 109 110 #endif /* _LOS_BINARYTREE_PRI_H */ 111