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