1 /* 2 * Copyright (c) 2024 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 #ifndef _TRIE_UTILITY_H_ 30 #define _TRIE_UTILITY_H_ 31 32 #include <sys/types.h> 33 34 #ifdef __cplusplus 35 BEGIN_DECLS 36 extern "C" { 37 #endif 38 39 #define MAX_TRIE_MEMORY (1024 * 1024) 40 #define FIRST_PRINTABLE_ASCII 32 41 #define LAST_PRINTABLE_ASCII 127 42 #define CHILD_MAP_SIZE (LAST_PRINTABLE_ASCII - FIRST_PRINTABLE_ASCII + 1) // printable ascii characters only 43 #define NULL_TRIE_IDX 0xffff 44 #define TRIE_NODE(t, i) ((t)->nodes[(i)]) 45 #define TRIE_CHILD_GET(t, i, b) ((b >= FIRST_PRINTABLE_ASCII && b <= LAST_PRINTABLE_ASCII) ? \ 46 (((t)->child_maps + (CHILD_MAP_SIZE * TRIE_NODE(t, i).child_map))[(b - FIRST_PRINTABLE_ASCII)]) : \ 47 NULL_TRIE_IDX) 48 49 #define TRIE_BYTE(t, i) ((t)->bytes[(i)]) 50 51 #define HIGH_ASCII(c) (c & 0x80) 52 53 #define NET_TRIE_MAGIC 0x5061747269636961 54 #define NET_TRIE_FORMAT_VERSION 2 55 56 struct net_trie_node { 57 uint16_t start; 58 uint16_t length:15; 59 uint16_t is_leaf:1; 60 uint16_t child_map; 61 uint16_t metadata; 62 uint16_t metadata_length; 63 }; 64 65 struct net_trie { 66 uint64_t magic; 67 uint64_t version; 68 struct net_trie_node *nodes __counted_by(nodes_count); 69 uint16_t *child_maps __counted_by(CHILD_MAP_SIZE * child_maps_count); 70 uint8_t *bytes __counted_by(bytes_count); 71 void *memory __sized_by(trie_memory_size); 72 uint16_t nodes_count; 73 uint16_t child_maps_count; 74 uint16_t bytes_count; 75 uint16_t nodes_free_next; 76 uint16_t child_maps_free_next; 77 uint16_t bytes_free_next; 78 uint16_t root; 79 size_t trie_memory_size; 80 size_t nodes_mem_size; 81 size_t child_maps_mem_size; 82 size_t bytes_mem_size; 83 }; 84 85 typedef boolean_t (*check_metadata_func)(const uint8_t *metadata, size_t metadata_length); 86 87 boolean_t net_trie_init(struct net_trie *new_trie, size_t prefix_count, size_t leaf_count, size_t bytes_count); 88 boolean_t net_trie_init_with_mem(struct net_trie *new_trie, uint8_t * __sized_by(trie_memory_size) memory, size_t trie_memory_size, 89 size_t nodes_mem_size, size_t child_maps_mem_size, size_t bytes_mem_size, 90 uint16_t nodes_count, uint16_t child_maps_count, uint16_t bytes_count); 91 uint16_t net_trie_insert(struct net_trie *trie, 92 const uint8_t * __sized_by(string_length) string, size_t string_length, 93 const uint8_t * __sized_by(metadata_length) metadata, size_t metadata_length, 94 boolean_t reverse); 95 uint16_t net_trie_search(struct net_trie *trie, 96 const uint8_t * __sized_by(string_length) string, size_t string_length, 97 const uint8_t * __sized_by(*metadata_length) * metadata, size_t *metadata_length, 98 boolean_t reverse, 99 boolean_t partial_match_allowed, 100 char partial_match_terminator, 101 boolean_t *high_ascii_detected, 102 check_metadata_func check_metadata); 103 void net_trie_free(struct net_trie *new_trie); 104 105 #ifdef __cplusplus 106 END_DECLS 107 } 108 #endif 109 110 #endif /* _TRIE_UTILITY_H_ */ 111