avl.h (2843B)
1 /* 2 * 3 * This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file. 4 * 5 * Copyright 2007-2019 Broadcom Inc. All rights reserved. 6 * 7 * File: avl.h 8 * Purpose: Defines a generic AVL tree data structure. 9 */ 10 11 #ifndef _SHR_AVL_H 12 #define _SHR_AVL_H 13 14 /* 15 * NOTE: 16 * 17 * sizeof (shr_avl_datum_t) is actually datum_bytes. 18 * sizeof (shr_avl_entry_t) is also correspondingly larger. 19 */ 20 21 typedef int shr_avl_datum_t; 22 23 typedef int (*shr_avl_compare_fn)(void *user_data, 24 shr_avl_datum_t *datum1, 25 shr_avl_datum_t *datum2); 26 27 typedef int (*shr_avl_compare_fn_lkupdata)(void *user_data, 28 shr_avl_datum_t *datum1, 29 shr_avl_datum_t *datum2, 30 void *lkupdata); 31 32 typedef int (*shr_avl_traverse_fn)(void *user_data, 33 shr_avl_datum_t *datum, 34 void *trav_data); 35 36 typedef int (*shr_avl_datum_copy_fn)(void *user_data, 37 shr_avl_datum_t *datum1, 38 shr_avl_datum_t *datum2); 39 40 typedef struct shr_avl_entry_s { 41 struct shr_avl_entry_s *left; 42 struct shr_avl_entry_s *right; 43 int balance; 44 shr_avl_datum_t datum; /* NOTE: variable size field */ 45 } shr_avl_entry_t; 46 47 typedef struct shr_avl_s { 48 /* Static data configured on tree creation */ 49 void *user_data; 50 int datum_bytes; 51 int datum_max; 52 int entry_bytes; 53 54 /* Dynamic data */ 55 char *datum_base; 56 shr_avl_entry_t *root; 57 shr_avl_entry_t *free_list; 58 int count; /* Number entries in tree */ 59 shr_avl_datum_copy_fn datum_copy_fn; 60 } shr_avl_t; 61 62 extern int shr_avl_create(shr_avl_t **avl_ptr, 63 void *user_data, 64 int datum_bytes, 65 int datum_max); 66 67 extern int shr_avl_destroy(shr_avl_t *avl); 68 69 extern int shr_avl_insert(shr_avl_t *avl, 70 shr_avl_compare_fn cmp_fn, 71 shr_avl_datum_t *datum); 72 73 extern int shr_avl_delete(shr_avl_t *avl, 74 shr_avl_compare_fn key_cmp_fn, 75 shr_avl_datum_t *datum); 76 77 extern int shr_avl_delete_all(shr_avl_t *avl); 78 79 extern int shr_avl_count(shr_avl_t *avl); 80 81 extern int shr_avl_lookup(shr_avl_t *avl, 82 shr_avl_compare_fn key_cmp_fn, 83 shr_avl_datum_t *datum); 84 85 extern int shr_avl_lookup_lkupdata(shr_avl_t *avl, 86 shr_avl_compare_fn_lkupdata key_cmp_fn, 87 shr_avl_datum_t *datum, 88 void *userdata); 89 90 extern int shr_avl_lookup_min(shr_avl_t *avl, 91 shr_avl_datum_t *datum); 92 93 extern int shr_avl_lookup_max(shr_avl_t *avl, 94 shr_avl_datum_t *datum); 95 96 extern int shr_avl_traverse(shr_avl_t *avl, 97 shr_avl_traverse_fn trav_fn, 98 void *trav_data); 99 100 #ifdef BROADCOM_DEBUG 101 extern void shr_avl_dump(shr_avl_t *avl); 102 #endif /* BROADCOM_DEBUG */ 103 104 #endif /* !_SHR_AVL_H */