/* SPDX-License-Identifier: GPL-2.0-or-later */ /* Private definitions for the generic associative array implementation. * * See Documentation/core-api/assoc_array.rst for information. * * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. * Written by David Howells ([email protected]) */ #ifndef _LINUX_ASSOC_ARRAY_PRIV_H #define _LINUX_ASSOC_ARRAY_PRIV_H #ifdef CONFIG_ASSOCIATIVE_ARRAY #include <linux/assoc_array.h> #define ASSOC_ARRAY_FAN_OUT … #define ASSOC_ARRAY_FAN_MASK … #define ASSOC_ARRAY_LEVEL_STEP … #define ASSOC_ARRAY_LEVEL_STEP_MASK … #define ASSOC_ARRAY_KEY_CHUNK_MASK … #define ASSOC_ARRAY_KEY_CHUNK_SHIFT … /* * Undefined type representing a pointer with type information in the bottom * two bits. */ struct assoc_array_ptr; /* * An N-way node in the tree. * * Each slot contains one of four things: * * (1) Nothing (NULL). * * (2) A leaf object (pointer types 0). * * (3) A next-level node (pointer type 1, subtype 0). * * (4) A shortcut (pointer type 1, subtype 1). * * The tree is optimised for search-by-ID, but permits reasonable iteration * also. * * The tree is navigated by constructing an index key consisting of an array of * segments, where each segment is ilog2(ASSOC_ARRAY_FAN_OUT) bits in size. * * The segments correspond to levels of the tree (the first segment is used at * level 0, the second at level 1, etc.). */ struct assoc_array_node { … }; /* * A shortcut through the index space out to where a collection of nodes/leaves * with the same IDs live. */ struct assoc_array_shortcut { … }; /* * Preallocation cache. */ struct assoc_array_edit { … }; /* * Internal tree member pointers are marked in the bottom one or two bits to * indicate what type they are so that we don't have to look behind every * pointer to see what it points to. * * We provide functions to test type annotations and to create and translate * the annotated pointers. */ #define ASSOC_ARRAY_PTR_TYPE_MASK … #define ASSOC_ARRAY_PTR_LEAF_TYPE … #define ASSOC_ARRAY_PTR_META_TYPE … #define ASSOC_ARRAY_PTR_SUBTYPE_MASK … #define ASSOC_ARRAY_PTR_NODE_SUBTYPE … #define ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE … static inline bool assoc_array_ptr_is_meta(const struct assoc_array_ptr *x) { … } static inline bool assoc_array_ptr_is_leaf(const struct assoc_array_ptr *x) { … } static inline bool assoc_array_ptr_is_shortcut(const struct assoc_array_ptr *x) { … } static inline bool assoc_array_ptr_is_node(const struct assoc_array_ptr *x) { … } static inline void *assoc_array_ptr_to_leaf(const struct assoc_array_ptr *x) { … } static inline unsigned long __assoc_array_ptr_to_meta(const struct assoc_array_ptr *x) { … } static inline struct assoc_array_node *assoc_array_ptr_to_node(const struct assoc_array_ptr *x) { … } static inline struct assoc_array_shortcut *assoc_array_ptr_to_shortcut(const struct assoc_array_ptr *x) { … } static inline struct assoc_array_ptr *__assoc_array_x_to_ptr(const void *p, unsigned long t) { … } static inline struct assoc_array_ptr *assoc_array_leaf_to_ptr(const void *p) { … } static inline struct assoc_array_ptr *assoc_array_node_to_ptr(const struct assoc_array_node *p) { … } static inline struct assoc_array_ptr *assoc_array_shortcut_to_ptr(const struct assoc_array_shortcut *p) { … } #endif /* CONFIG_ASSOCIATIVE_ARRAY */ #endif /* _LINUX_ASSOC_ARRAY_PRIV_H */
Codebase Browser
linux