1 /* 2 * Copyright (c) 2022 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef RED_BLACK_TREE_H 17 #define RED_BLACK_TREE_H 18 19 #include <stdint.h> 20 21 #ifdef __cplusplus 22 extern "C" { 23 #endif 24 25 typedef uint32_t RbTreeKey; 26 typedef void* RbTreeValue; 27 typedef void (*RbTreeNodeHandler)(RbTreeKey key, RbTreeValue value, const void *context); 28 29 typedef int (*RbTreeValueEncoder)(RbTreeValue value, uint8_t *buf, uint32_t *size); 30 typedef int (*RbTreeValueDecoder)(RbTreeValue *value, const uint8_t *buf, uint32_t size); 31 typedef void (*RbTreeValueFree)(RbTreeValue *value); 32 33 enum TraverseOrder { 34 IN, PRE, POST 35 }; 36 37 struct RbTreeNode { 38 RbTreeKey key; 39 RbTreeValue value; 40 struct RbTreeNode *p; 41 struct RbTreeNode *left; 42 struct RbTreeNode *right; 43 }; 44 45 struct RbTree { 46 struct RbTreeNode *nil; 47 struct RbTreeNode *root; 48 }; 49 50 int RbTreeNew(struct RbTree *t); 51 52 RbTreeKey RbTreeNodeKey(const struct RbTreeNode *n); 53 54 int32_t RbTreeDelete(struct RbTree *t, struct RbTreeNode *z); 55 56 int32_t RbTreeInsert(struct RbTree *t, RbTreeKey key, const RbTreeValue value); 57 58 int32_t RbTreeFindNode(struct RbTreeNode **nodePtr, RbTreeKey key, const struct RbTree *tree); 59 60 int32_t RbTreeDecode(struct RbTree *t, RbTreeValueDecoder dec, RbTreeValueFree freeFunc, 61 uint8_t *buf, uint32_t size); 62 63 int32_t RbTreeEncode(const struct RbTree *t, RbTreeValueEncoder enc, uint8_t *buf, uint32_t *size); 64 65 void RbTreeDestroyEx(struct RbTree *t, RbTreeNodeHandler freeFunc); 66 67 #ifdef __cplusplus 68 } 69 #endif 70 #endif