1 /* 2 * Copyright (c) 2014-2018, NVIDIA CORPORATION. All rights reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 * 16 */ 17 18 #ifndef RBTREE_H_ 19 #define RBTREE_H_ 20 21 typedef struct rbtree_root_struct rbroot; 22 typedef struct rbtree_struct *rbtree; 23 struct rbtree_root_struct { 24 rbtree root; 25 size_t blocksize, freesize; 26 char *datablocklist, *datafree; 27 }; 28 29 /* red-black tree */ 30 struct rbtree_struct { 31 rbtree left, right, parent; 32 int color; 33 int data[]; 34 }; 35 36 #define RBRED 1 37 #define RBBLK 2 38 #define RBCOLOR 3 39 40 #define ISBLACK(rb) (rb == NULL || (rb->color == RBBLK)) 41 #define ISRED(rb) (rb != NULL && (rb->color == RBRED)) 42 #define SETBLACK(rb) \ 43 if (rb) { \ 44 rb->color = RBBLK; \ 45 } 46 #define SETRED(rb) \ 47 if (rb) { \ 48 rb->color = RBRED; \ 49 } 50 #define COPYCOLOR(rb, fb) rb->color = fb->color 51 52 #define ALN(b, aln) ((((b) + (aln)-1)) & (~((aln)-1))) 53 54 typedef int (*rb_compare)(void *, void *); 55 typedef int (*rb_walk_proc)(rbtree, void *userdata); 56 57 /** 58 \brief ... 59 */ 60 int rb_walk(rbroot *T, rb_walk_proc proc, void *userdata); 61 62 /** 63 \brief ... 64 */ 65 rbtree rb_find(rbroot *T, void *data, rb_compare compare); 66 67 /** 68 \brief ... 69 */ 70 rbtree rb_insert(rbroot *T, size_t datasize, void *data, rb_compare compare); 71 72 /** 73 \brief ... 74 */ 75 void rb_free(rbroot *T); 76 77 78 #endif // RBTREE_H_ 79