1 /* 2 * Copyright (c) 2015-2016, Intel Corporation 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * * Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * * Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * * Neither the name of Intel Corporation nor the names of its contributors 13 * may be used to endorse or promote products derived from this software 14 * without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 /** \file 30 * \brief Multibit: data structures. 31 * 32 * If all you need is the sizes of multibit's few structures, then including 33 * this file is a much better idea than including all of multibit.h. 34 */ 35 #ifndef MULTIBIT_INTERNAL_H 36 #define MULTIBIT_INTERNAL_H 37 38 #include "ue2common.h" 39 40 #ifdef __cplusplus 41 extern "C" { 42 #endif 43 44 /** \brief Sentinel value meaning "no key found". */ 45 #define MMB_INVALID 0xffffffffu 46 47 typedef u64a MMB_TYPE; /**< Basic block type for mmbit operations. */ 48 #define MMB_MAX_LEVEL 6 /**< Maximum level in the mmbit pyramid. */ 49 50 /** \brief Maximum number of keys (bits) in a multibit. */ 51 #define MMB_MAX_BITS (1U << 31) 52 53 /** \brief Sparse iterator record type. 54 * 55 * A sparse iterator is a tree of these records, where val identifies the 56 * offset of the result for leaf nodes and points to the next record for 57 * intermediate nodes. Built by the code in multibit_build.cpp. 58 */ 59 struct mmbit_sparse_iter { 60 MMB_TYPE mask; 61 u32 val; 62 }; 63 64 /** \brief Sparse iterator runtime state type. 65 * 66 * An array of these records (one per "level" in the multibit pyramid) is used 67 * to store the current iteration state. 68 */ 69 struct mmbit_sparse_state { 70 MMB_TYPE mask; //!< \brief masked last block read at this level. 71 u32 itkey; //!< \brief iterator offset for this level. 72 }; 73 74 /** \brief Maximum number of \ref mmbit_sparse_state that could be needed. */ 75 #define MAX_SPARSE_ITER_STATES (6 + 1) 76 77 #ifdef __cplusplus 78 } // extern "C" 79 #endif 80 81 #endif // MULTIBIT_INTERNAL_H 82