1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright (C) 2017 Intel Corporation. 3 * All rights reserved. 4 */ 5 6 #ifndef SPDK_TREE_H_ 7 #define SPDK_TREE_H_ 8 9 struct cache_buffer { 10 uint8_t *buf; 11 uint64_t offset; 12 uint32_t buf_size; 13 uint32_t bytes_filled; 14 uint32_t bytes_flushed; 15 bool in_progress; 16 }; 17 18 #define CACHE_BUFFER_SHIFT (18) 19 #define CACHE_BUFFER_SIZE (1U << CACHE_BUFFER_SHIFT) 20 #define NEXT_CACHE_BUFFER_OFFSET(offset) \ 21 (((offset + CACHE_BUFFER_SIZE) >> CACHE_BUFFER_SHIFT) << CACHE_BUFFER_SHIFT) 22 23 #define CACHE_TREE_SHIFT 6 24 #define CACHE_TREE_WIDTH (1U << CACHE_TREE_SHIFT) 25 #define CACHE_TREE_LEVEL_SHIFT(level) (CACHE_BUFFER_SHIFT + (level) * CACHE_TREE_SHIFT) 26 #define CACHE_TREE_LEVEL_SIZE(level) (1ULL << CACHE_TREE_LEVEL_SHIFT(level)) 27 #define CACHE_TREE_LEVEL_MASK(level) (CACHE_TREE_LEVEL_SIZE(level) - 1) 28 #define CACHE_TREE_INDEX(level, offset) ((offset >> CACHE_TREE_LEVEL_SHIFT(level)) & (CACHE_TREE_WIDTH - 1)) 29 30 struct cache_tree { 31 uint8_t level; 32 uint64_t present_mask; 33 union { 34 struct cache_buffer *buffer[CACHE_TREE_WIDTH]; 35 struct cache_tree *tree[CACHE_TREE_WIDTH]; 36 } u; 37 }; 38 39 void cache_buffer_free(struct cache_buffer *cache_buffer); 40 41 struct cache_tree *tree_insert_buffer(struct cache_tree *root, struct cache_buffer *buffer); 42 void tree_free_buffers(struct cache_tree *tree); 43 struct cache_buffer *tree_find_buffer(struct cache_tree *tree, uint64_t offset); 44 struct cache_buffer *tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset); 45 void tree_remove_buffer(struct cache_tree *tree, struct cache_buffer *buffer); 46 47 #endif /* SPDK_TREE_H_ */ 48