1266072Sdes/* 2266072Sdes * radix.c -- generic radix tree 3266072Sdes * 4266072Sdes * Taken from NSD4, modified for ldns 5266072Sdes * 6266072Sdes * Copyright (c) 2012, NLnet Labs. All rights reserved. 7266072Sdes * 8266072Sdes * This software is open source. 9266072Sdes * 10266072Sdes * Redistribution and use in source and binary forms, with or without 11266072Sdes * modification, are permitted provided that the following conditions 12266072Sdes * are met: 13266072Sdes * 14266072Sdes * Redistributions of source code must retain the above copyright notice, 15266072Sdes * this list of conditions and the following disclaimer. 16266072Sdes * 17266072Sdes * Redistributions in binary form must reproduce the above copyright notice, 18266072Sdes * this list of conditions and the following disclaimer in the documentation 19266072Sdes * and/or other materials provided with the distribution. 20266072Sdes * 21266072Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 22266072Sdes * be used to endorse or promote products derived from this software without 23266072Sdes * specific prior written permission. 24266072Sdes * 25266072Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26266072Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 27266072Sdes * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28266072Sdes * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 29266072Sdes * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 30266072Sdes * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 31266072Sdes * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 32266072Sdes * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 33266072Sdes * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 34266072Sdes * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 35266072Sdes * POSSIBILITY OF SUCH DAMAGE. 36266072Sdes * 37266072Sdes */ 38266072Sdes 39266072Sdes/** 40266072Sdes * \file 41266072Sdes * Implementation of a radix tree. 42266072Sdes */ 43266072Sdes 44266072Sdes#include <ldns/config.h> 45266072Sdes#include <ldns/radix.h> 46266072Sdes#include <ldns/util.h> 47266072Sdes#include <stdlib.h> 48266072Sdes 49266072Sdes/** Helper functions */ 50266072Sdesstatic ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key, 51266072Sdes radix_strlen_t len); 52266072Sdesstatic int ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key, 53266072Sdes radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos); 54266072Sdesstatic int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte); 55266072Sdesstatic int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need); 56266072Sdesstatic int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key, 57266072Sdes radix_strlen_t pos, radix_strlen_t len); 58266072Sdesstatic int ldns_radix_prefix_remainder(radix_strlen_t prefix_len, 59266072Sdes uint8_t* longer_str, radix_strlen_t longer_len, uint8_t** split_str, 60266072Sdes radix_strlen_t* split_len); 61266072Sdesstatic int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key, 62266072Sdes radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add); 63266072Sdesstatic int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1, 64266072Sdes uint8_t* str2, radix_strlen_t len2); 65266072Sdesstatic radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1, 66266072Sdes uint8_t* str2, radix_strlen_t len2); 67266072Sdesstatic ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node); 68266072Sdesstatic ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node, 69266072Sdes uint8_t index); 70266072Sdesstatic ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self( 71266072Sdes ldns_radix_node_t* node); 72266072Sdesstatic ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node); 73266072Sdesstatic void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node); 74266072Sdesstatic void ldns_radix_cleanup_onechild(ldns_radix_node_t* node); 75266072Sdesstatic void ldns_radix_cleanup_leaf(ldns_radix_node_t* node); 76266072Sdesstatic void ldns_radix_node_free(ldns_radix_node_t* node, void* arg); 77266072Sdesstatic void ldns_radix_node_array_free(ldns_radix_node_t* node); 78266072Sdesstatic void ldns_radix_node_array_free_front(ldns_radix_node_t* node); 79266072Sdesstatic void ldns_radix_node_array_free_end(ldns_radix_node_t* node); 80266072Sdesstatic void ldns_radix_array_reduce(ldns_radix_node_t* node); 81266072Sdesstatic void ldns_radix_self_or_prev(ldns_radix_node_t* node, 82266072Sdes ldns_radix_node_t** result); 83266072Sdes 84266072Sdes 85266072Sdes/** 86266072Sdes * Create a new radix node. 87266072Sdes * 88266072Sdes */ 89266072Sdesstatic ldns_radix_node_t* 90266072Sdesldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len) 91266072Sdes{ 92266072Sdes ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t); 93266072Sdes if (!node) { 94266072Sdes return NULL; 95266072Sdes } 96266072Sdes node->data = data; 97266072Sdes node->key = key; 98266072Sdes node->klen = len; 99266072Sdes node->parent = NULL; 100266072Sdes node->parent_index = 0; 101266072Sdes node->len = 0; 102266072Sdes node->offset = 0; 103266072Sdes node->capacity = 0; 104266072Sdes node->array = NULL; 105266072Sdes return node; 106266072Sdes} 107266072Sdes 108266072Sdes 109266072Sdes/** 110266072Sdes * Create a new radix tree. 111266072Sdes * 112266072Sdes */ 113266072Sdesldns_radix_t * 114266072Sdesldns_radix_create(void) 115266072Sdes{ 116266072Sdes ldns_radix_t* tree; 117266072Sdes 118266072Sdes /** Allocate memory for it */ 119266072Sdes tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t); 120266072Sdes if (!tree) { 121266072Sdes return NULL; 122266072Sdes } 123266072Sdes /** Initialize it */ 124266072Sdes ldns_radix_init(tree); 125266072Sdes return tree; 126266072Sdes} 127266072Sdes 128266072Sdes 129266072Sdes/** 130266072Sdes * Initialize radix tree. 131266072Sdes * 132266072Sdes */ 133266072Sdesvoid 134266072Sdesldns_radix_init(ldns_radix_t* tree) 135266072Sdes{ 136266072Sdes /** Initialize it */ 137266072Sdes if (tree) { 138266072Sdes tree->root = NULL; 139266072Sdes tree->count = 0; 140266072Sdes } 141266072Sdes return; 142266072Sdes} 143266072Sdes 144266072Sdes 145266072Sdes/** 146266072Sdes * Free radix tree. 147266072Sdes * 148266072Sdes */ 149266072Sdesvoid 150266072Sdesldns_radix_free(ldns_radix_t* tree) 151266072Sdes{ 152266072Sdes if (tree) { 153266072Sdes if (tree->root) { 154266072Sdes ldns_radix_traverse_postorder(tree->root, 155266072Sdes ldns_radix_node_free, NULL); 156266072Sdes } 157266072Sdes LDNS_FREE(tree); 158266072Sdes } 159266072Sdes return; 160266072Sdes} 161266072Sdes 162266072Sdes 163266072Sdes/** 164266072Sdes * Insert data into the tree. 165266072Sdes * 166266072Sdes */ 167266072Sdesldns_status 168266072Sdesldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len, 169266072Sdes void* data) 170266072Sdes{ 171266072Sdes radix_strlen_t pos = 0; 172266072Sdes ldns_radix_node_t* add = NULL; 173266072Sdes ldns_radix_node_t* prefix = NULL; 174266072Sdes 175266072Sdes if (!tree || !key || !data) { 176266072Sdes return LDNS_STATUS_NULL; 177266072Sdes } 178266072Sdes add = ldns_radix_new_node(data, key, len); 179266072Sdes if (!add) { 180266072Sdes return LDNS_STATUS_MEM_ERR; 181266072Sdes } 182266072Sdes /** Search the trie until we can make no further process. */ 183266072Sdes if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) { 184266072Sdes /** No prefix found */ 185266072Sdes assert(tree->root == NULL); 186266072Sdes if (len == 0) { 187266072Sdes /** 188266072Sdes * Example 1: The root: 189266072Sdes * | [0] 190266072Sdes **/ 191266072Sdes tree->root = add; 192266072Sdes } else { 193266072Sdes /** Example 2: 'dns': 194266072Sdes * | [0] 195266072Sdes * --| [d+ns] dns 196266072Sdes **/ 197266072Sdes prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0); 198266072Sdes if (!prefix) { 199266072Sdes LDNS_FREE(add); 200266072Sdes return LDNS_STATUS_MEM_ERR; 201266072Sdes } 202266072Sdes /** Find some space in the array for the first byte */ 203266072Sdes if (!ldns_radix_array_space(prefix, key[0])) { 204266072Sdes LDNS_FREE(add); 205266072Sdes LDNS_FREE(prefix->array); 206266072Sdes LDNS_FREE(prefix); 207266072Sdes return LDNS_STATUS_MEM_ERR; 208266072Sdes } 209266072Sdes /** Set relational pointers */ 210266072Sdes add->parent = prefix; 211266072Sdes add->parent_index = 0; 212266072Sdes prefix->array[0].edge = add; 213266072Sdes if (len > 1) { 214266072Sdes /** Store the remainder of the prefix */ 215266072Sdes if (!ldns_radix_prefix_remainder(1, key, 216266072Sdes len, &prefix->array[0].str, 217266072Sdes &prefix->array[0].len)) { 218266072Sdes LDNS_FREE(add); 219266072Sdes LDNS_FREE(prefix->array); 220266072Sdes LDNS_FREE(prefix); 221266072Sdes return LDNS_STATUS_MEM_ERR; 222266072Sdes } 223266072Sdes } 224266072Sdes tree->root = prefix; 225266072Sdes } 226266072Sdes } else if (pos == len) { 227266072Sdes /** Exact match found */ 228266072Sdes if (prefix->data) { 229266072Sdes /* Element already exists */ 230266072Sdes LDNS_FREE(add); 231266072Sdes return LDNS_STATUS_EXISTS_ERR; 232266072Sdes } 233266072Sdes prefix->data = data; 234266072Sdes prefix->key = key; 235266072Sdes prefix->klen = len; /* redundant */ 236266072Sdes } else { 237266072Sdes /** Prefix found */ 238266072Sdes uint8_t byte = key[pos]; 239266072Sdes assert(pos < len); 240266072Sdes if (byte < prefix->offset || 241266072Sdes (byte - prefix->offset) >= prefix->len) { 242266072Sdes /** Find some space in the array for the byte. */ 243266072Sdes /** 244266072Sdes * Example 3: 'ldns' 245266072Sdes * | [0] 246266072Sdes * --| [d+ns] dns 247266072Sdes * --| [l+dns] ldns 248266072Sdes **/ 249266072Sdes if (!ldns_radix_array_space(prefix, byte)) { 250266072Sdes LDNS_FREE(add); 251266072Sdes return LDNS_STATUS_MEM_ERR; 252266072Sdes } 253266072Sdes assert(byte >= prefix->offset); 254266072Sdes assert((byte - prefix->offset) <= prefix->len); 255266072Sdes byte -= prefix->offset; 256266072Sdes if (pos+1 < len) { 257266072Sdes /** Create remainder of the string. */ 258266072Sdes if (!ldns_radix_str_create( 259266072Sdes &prefix->array[byte], key, pos+1, 260266072Sdes len)) { 261266072Sdes LDNS_FREE(add); 262266072Sdes return LDNS_STATUS_MEM_ERR; 263266072Sdes } 264266072Sdes } 265266072Sdes /** Add new node. */ 266266072Sdes add->parent = prefix; 267266072Sdes add->parent_index = byte; 268266072Sdes prefix->array[byte].edge = add; 269266072Sdes } else if (prefix->array[byte-prefix->offset].edge == NULL) { 270266072Sdes /** Use existing element. */ 271266072Sdes /** 272266072Sdes * Example 4: 'edns' 273266072Sdes * | [0] 274266072Sdes * --| [d+ns] dns 275266072Sdes * --| [e+dns] edns 276266072Sdes * --| [l+dns] ldns 277266072Sdes **/ 278266072Sdes byte -= prefix->offset; 279266072Sdes if (pos+1 < len) { 280266072Sdes /** Create remainder of the string. */ 281266072Sdes if (!ldns_radix_str_create( 282266072Sdes &prefix->array[byte], key, pos+1, 283266072Sdes len)) { 284266072Sdes LDNS_FREE(add); 285266072Sdes return LDNS_STATUS_MEM_ERR; 286266072Sdes } 287266072Sdes } 288266072Sdes /** Add new node. */ 289266072Sdes add->parent = prefix; 290266072Sdes add->parent_index = byte; 291266072Sdes prefix->array[byte].edge = add; 292266072Sdes } else { 293266072Sdes /** 294266072Sdes * Use existing element, but it has a shared prefix, 295266072Sdes * we need a split. 296266072Sdes */ 297266072Sdes if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)], 298266072Sdes key, pos+1, len, add)) { 299266072Sdes LDNS_FREE(add); 300266072Sdes return LDNS_STATUS_MEM_ERR; 301266072Sdes } 302266072Sdes } 303266072Sdes } 304266072Sdes 305266072Sdes tree->count ++; 306266072Sdes return LDNS_STATUS_OK; 307266072Sdes} 308266072Sdes 309266072Sdes 310266072Sdes/** 311266072Sdes * Delete data from the tree. 312266072Sdes * 313266072Sdes */ 314266072Sdesvoid* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len) 315266072Sdes{ 316266072Sdes ldns_radix_node_t* del = ldns_radix_search(tree, key, len); 317266072Sdes void* data = NULL; 318266072Sdes if (del) { 319266072Sdes tree->count--; 320266072Sdes data = del->data; 321266072Sdes del->data = NULL; 322266072Sdes ldns_radix_del_fix(tree, del); 323266072Sdes return data; 324266072Sdes } 325266072Sdes return NULL; 326266072Sdes} 327266072Sdes 328266072Sdes 329266072Sdes/** 330266072Sdes * Search data in the tree. 331266072Sdes * 332266072Sdes */ 333266072Sdesldns_radix_node_t* 334266072Sdesldns_radix_search(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len) 335266072Sdes{ 336266072Sdes ldns_radix_node_t* node = NULL; 337266072Sdes radix_strlen_t pos = 0; 338266072Sdes uint8_t byte = 0; 339266072Sdes 340266072Sdes if (!tree || !key) { 341266072Sdes return NULL; 342266072Sdes } 343266072Sdes node = tree->root; 344266072Sdes while (node) { 345266072Sdes if (pos == len) { 346266072Sdes return node->data?node:NULL; 347266072Sdes } 348266072Sdes byte = key[pos]; 349266072Sdes if (byte < node->offset) { 350266072Sdes return NULL; 351266072Sdes } 352266072Sdes byte -= node->offset; 353266072Sdes if (byte >= node->len) { 354266072Sdes return NULL; 355266072Sdes } 356266072Sdes pos++; 357266072Sdes if (node->array[byte].len > 0) { 358266072Sdes /** Must match additional string. */ 359266072Sdes if (pos + node->array[byte].len > len) { 360266072Sdes return NULL; 361266072Sdes } 362266072Sdes if (memcmp(&key[pos], node->array[byte].str, 363266072Sdes node->array[byte].len) != 0) { 364266072Sdes return NULL; 365266072Sdes } 366266072Sdes pos += node->array[byte].len; 367266072Sdes } 368266072Sdes node = node->array[byte].edge; 369266072Sdes } 370266072Sdes return NULL; 371266072Sdes} 372266072Sdes 373266072Sdes 374266072Sdes/** 375266072Sdes * Search data in the tree, and if not found, find the closest smaller 376266072Sdes * element in the tree. 377266072Sdes * 378266072Sdes */ 379266072Sdesint 380266072Sdesldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key, 381266072Sdes radix_strlen_t len, ldns_radix_node_t** result) 382266072Sdes{ 383266072Sdes ldns_radix_node_t* node = NULL; 384266072Sdes radix_strlen_t pos = 0; 385266072Sdes uint8_t byte; 386266072Sdes int memcmp_res = 0; 387266072Sdes 388266072Sdes if (!tree || !tree->root || !key) { 389266072Sdes *result = NULL; 390266072Sdes return 0; 391266072Sdes } 392266072Sdes 393266072Sdes node = tree->root; 394266072Sdes while (pos < len) { 395266072Sdes byte = key[pos]; 396266072Sdes if (byte < node->offset) { 397266072Sdes /** 398266072Sdes * No exact match. The lesser is in this or the 399266072Sdes * previous node. 400266072Sdes */ 401266072Sdes ldns_radix_self_or_prev(node, result); 402266072Sdes return 0; 403266072Sdes } 404266072Sdes byte -= node->offset; 405266072Sdes if (byte >= node->len) { 406266072Sdes /** 407266072Sdes * No exact match. The lesser is in this node or the 408266072Sdes * last of this array, or something before this node. 409266072Sdes */ 410266072Sdes *result = ldns_radix_last_in_subtree_incl_self(node); 411266072Sdes if (*result == NULL) { 412266072Sdes *result = ldns_radix_prev(node); 413266072Sdes } 414266072Sdes return 0; 415266072Sdes } 416266072Sdes pos++; 417266072Sdes if (!node->array[byte].edge) { 418266072Sdes /** 419266072Sdes * No exact match. Find the previous in the array 420266072Sdes * from this index. 421266072Sdes */ 422266072Sdes *result = ldns_radix_prev_from_index(node, byte); 423266072Sdes if (*result == NULL) { 424266072Sdes ldns_radix_self_or_prev(node, result); 425266072Sdes } 426266072Sdes return 0; 427266072Sdes } 428266072Sdes if (node->array[byte].len != 0) { 429266072Sdes /** Must match additional string. */ 430266072Sdes if (pos + node->array[byte].len > len) { 431266072Sdes /** Additional string is longer than key. */ 432266072Sdes if (memcmp(&key[pos], node->array[byte].str, 433266072Sdes len-pos) <= 0) { 434266072Sdes /** Key is before this node. */ 435266072Sdes *result = ldns_radix_prev( 436266072Sdes node->array[byte].edge); 437266072Sdes } else { 438266072Sdes /** Key is after additional string. */ 439266072Sdes *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge); 440266072Sdes if (*result == NULL) { 441266072Sdes *result = ldns_radix_prev(node->array[byte].edge); 442266072Sdes } 443266072Sdes } 444266072Sdes return 0; 445266072Sdes } 446266072Sdes memcmp_res = memcmp(&key[pos], node->array[byte].str, 447266072Sdes node->array[byte].len); 448266072Sdes if (memcmp_res < 0) { 449266072Sdes *result = ldns_radix_prev( 450266072Sdes node->array[byte].edge); 451266072Sdes return 0; 452266072Sdes } else if (memcmp_res > 0) { 453266072Sdes *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge); 454266072Sdes if (*result == NULL) { 455266072Sdes *result = ldns_radix_prev(node->array[byte].edge); 456266072Sdes } 457266072Sdes return 0; 458266072Sdes } 459266072Sdes 460266072Sdes pos += node->array[byte].len; 461266072Sdes } 462266072Sdes node = node->array[byte].edge; 463266072Sdes } 464266072Sdes if (node->data) { 465266072Sdes /** Exact match. */ 466266072Sdes *result = node; 467266072Sdes return 1; 468266072Sdes } 469266072Sdes /** There is a node which is an exact match, but has no element. */ 470266072Sdes *result = ldns_radix_prev(node); 471266072Sdes return 0; 472266072Sdes} 473266072Sdes 474266072Sdes 475266072Sdes/** 476266072Sdes * Get the first element in the tree. 477266072Sdes * 478266072Sdes */ 479266072Sdesldns_radix_node_t* 480266072Sdesldns_radix_first(ldns_radix_t* tree) 481266072Sdes{ 482266072Sdes ldns_radix_node_t* first = NULL; 483266072Sdes if (!tree || !tree->root) { 484266072Sdes return NULL; 485266072Sdes } 486266072Sdes first = tree->root; 487266072Sdes if (first->data) { 488266072Sdes return first; 489266072Sdes } 490266072Sdes return ldns_radix_next(first); 491266072Sdes} 492266072Sdes 493266072Sdes 494266072Sdes/** 495266072Sdes * Get the last element in the tree. 496266072Sdes * 497266072Sdes */ 498266072Sdesldns_radix_node_t* 499266072Sdesldns_radix_last(ldns_radix_t* tree) 500266072Sdes{ 501266072Sdes if (!tree || !tree->root) { 502266072Sdes return NULL; 503266072Sdes } 504266072Sdes return ldns_radix_last_in_subtree_incl_self(tree->root); 505266072Sdes} 506266072Sdes 507266072Sdes 508266072Sdes/** 509266072Sdes * Next element. 510266072Sdes * 511266072Sdes */ 512266072Sdesldns_radix_node_t* 513266072Sdesldns_radix_next(ldns_radix_node_t* node) 514266072Sdes{ 515266072Sdes if (!node) { 516266072Sdes return NULL; 517266072Sdes } 518266072Sdes if (node->len) { 519266072Sdes /** Go down: most-left child is the next. */ 520266072Sdes ldns_radix_node_t* next = ldns_radix_next_in_subtree(node); 521266072Sdes if (next) { 522266072Sdes return next; 523266072Sdes } 524266072Sdes } 525266072Sdes /** No elements in subtree, get to parent and go down next branch. */ 526266072Sdes while (node->parent) { 527266072Sdes uint8_t index = node->parent_index; 528266072Sdes node = node->parent; 529266072Sdes index++; 530266072Sdes for (; index < node->len; index++) { 531266072Sdes if (node->array[index].edge) { 532266072Sdes ldns_radix_node_t* next; 533266072Sdes /** Node itself. */ 534266072Sdes if (node->array[index].edge->data) { 535266072Sdes return node->array[index].edge; 536266072Sdes } 537266072Sdes /** Dive into subtree. */ 538266072Sdes next = ldns_radix_next_in_subtree(node); 539266072Sdes if (next) { 540266072Sdes return next; 541266072Sdes } 542266072Sdes } 543266072Sdes } 544266072Sdes } 545266072Sdes return NULL; 546266072Sdes} 547266072Sdes 548266072Sdes 549266072Sdes/** 550266072Sdes * Previous element. 551266072Sdes * 552266072Sdes */ 553266072Sdesldns_radix_node_t* 554266072Sdesldns_radix_prev(ldns_radix_node_t* node) 555266072Sdes{ 556266072Sdes if (!node) { 557266072Sdes return NULL; 558266072Sdes } 559266072Sdes 560266072Sdes /** Get to parent and go down previous branch. */ 561266072Sdes while (node->parent) { 562266072Sdes uint8_t index = node->parent_index; 563266072Sdes ldns_radix_node_t* prev; 564266072Sdes node = node->parent; 565266072Sdes assert(node->len > 0); 566266072Sdes prev = ldns_radix_prev_from_index(node, index); 567266072Sdes if (prev) { 568266072Sdes return prev; 569266072Sdes } 570266072Sdes if (node->data) { 571266072Sdes return node; 572266072Sdes } 573266072Sdes } 574266072Sdes return NULL; 575266072Sdes} 576266072Sdes 577266072Sdes 578266072Sdes/** 579266072Sdes * Print node. 580266072Sdes * 581266072Sdes */ 582266072Sdesstatic void 583266072Sdesldns_radix_node_print(FILE* fd, ldns_radix_node_t* node, 584266072Sdes uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d) 585266072Sdes{ 586266072Sdes uint8_t j; 587266072Sdes if (!node) { 588266072Sdes return; 589266072Sdes } 590266072Sdes for (j = 0; j < d; j++) { 591266072Sdes fprintf(fd, "--"); 592266072Sdes } 593266072Sdes if (str) { 594266072Sdes radix_strlen_t l; 595266072Sdes fprintf(fd, "| [%u+", (unsigned) i); 596266072Sdes for (l=0; l < len; l++) { 597266072Sdes fprintf(fd, "%c", (char) str[l]); 598266072Sdes } 599266072Sdes fprintf(fd, "]%u", (unsigned) len); 600266072Sdes } else { 601266072Sdes fprintf(fd, "| [%u]", (unsigned) i); 602266072Sdes } 603266072Sdes 604266072Sdes if (node->data) { 605266072Sdes fprintf(fd, " %s", (char*) node->data); 606266072Sdes } 607266072Sdes fprintf(fd, "\n"); 608266072Sdes 609266072Sdes for (j = 0; j < node->len; j++) { 610266072Sdes if (node->array[j].edge) { 611266072Sdes ldns_radix_node_print(fd, node->array[j].edge, j, 612266072Sdes node->array[j].str, node->array[j].len, d+1); 613266072Sdes } 614266072Sdes } 615266072Sdes return; 616266072Sdes} 617266072Sdes 618266072Sdes 619266072Sdes/** 620266072Sdes * Print radix tree. 621266072Sdes * 622266072Sdes */ 623266072Sdesvoid 624266072Sdesldns_radix_printf(FILE* fd, ldns_radix_t* tree) 625266072Sdes{ 626266072Sdes if (!fd || !tree) { 627266072Sdes return; 628266072Sdes } 629266072Sdes if (!tree->root) { 630266072Sdes fprintf(fd, "; empty radix tree\n"); 631266072Sdes return; 632266072Sdes } 633266072Sdes ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0); 634266072Sdes return; 635266072Sdes} 636266072Sdes 637266072Sdes 638266072Sdes/** 639266072Sdes * Join two radix trees. 640266072Sdes * 641266072Sdes */ 642266072Sdesldns_status 643266072Sdesldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2) 644266072Sdes{ 645266072Sdes ldns_radix_node_t* cur_node, *next_node; 646266072Sdes ldns_status status; 647266072Sdes if (!tree2 || !tree2->root) { 648266072Sdes return LDNS_STATUS_OK; 649266072Sdes } 650266072Sdes /** Add all elements from tree2 into tree1. */ 651266072Sdes 652266072Sdes cur_node = ldns_radix_first(tree2); 653266072Sdes while (cur_node) { 654266072Sdes status = LDNS_STATUS_NO_DATA; 655266072Sdes /** Insert current node into tree1 */ 656266072Sdes if (cur_node->data) { 657266072Sdes status = ldns_radix_insert(tree1, cur_node->key, 658266072Sdes cur_node->klen, cur_node->data); 659266072Sdes /** Exist errors may occur */ 660266072Sdes if (status != LDNS_STATUS_OK && 661266072Sdes status != LDNS_STATUS_EXISTS_ERR) { 662266072Sdes return status; 663266072Sdes } 664266072Sdes } 665266072Sdes next_node = ldns_radix_next(cur_node); 666266072Sdes if (status == LDNS_STATUS_OK) { 667266072Sdes (void) ldns_radix_delete(tree2, cur_node->key, 668266072Sdes cur_node->klen); 669266072Sdes } 670266072Sdes cur_node = next_node; 671266072Sdes } 672266072Sdes 673266072Sdes return LDNS_STATUS_OK; 674266072Sdes} 675266072Sdes 676266072Sdes 677266072Sdes/** 678266072Sdes * Split a radix tree intwo. 679266072Sdes * 680266072Sdes */ 681266072Sdesldns_status 682266072Sdesldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2) 683266072Sdes{ 684266072Sdes size_t count = 0; 685266072Sdes ldns_radix_node_t* cur_node; 686266072Sdes ldns_status status = LDNS_STATUS_OK; 687266072Sdes if (!tree1 || !tree1->root || num == 0) { 688266072Sdes return LDNS_STATUS_OK; 689266072Sdes } 690266072Sdes if (!tree2) { 691266072Sdes return LDNS_STATUS_NULL; 692266072Sdes } 693266072Sdes if (!*tree2) { 694266072Sdes *tree2 = ldns_radix_create(); 695266072Sdes if (!*tree2) { 696266072Sdes return LDNS_STATUS_MEM_ERR; 697266072Sdes } 698266072Sdes } 699266072Sdes cur_node = ldns_radix_first(tree1); 700266072Sdes while (count < num && cur_node) { 701266072Sdes if (cur_node->data) { 702266072Sdes /** Delete current node from tree1. */ 703266072Sdes uint8_t* cur_key = cur_node->key; 704266072Sdes radix_strlen_t cur_len = cur_node->klen; 705266072Sdes void* cur_data = ldns_radix_delete(tree1, cur_key, 706266072Sdes cur_len); 707266072Sdes /** Insert current node into tree2/ */ 708266072Sdes if (!cur_data) { 709266072Sdes return LDNS_STATUS_NO_DATA; 710266072Sdes } 711266072Sdes status = ldns_radix_insert(*tree2, cur_key, cur_len, 712266072Sdes cur_data); 713266072Sdes if (status != LDNS_STATUS_OK && 714266072Sdes status != LDNS_STATUS_EXISTS_ERR) { 715266072Sdes return status; 716266072Sdes } 717266072Sdes/* 718266072Sdes if (status == LDNS_STATUS_OK) { 719266072Sdes cur_node->key = NULL; 720266072Sdes cur_node->klen = 0; 721266072Sdes } 722266072Sdes*/ 723266072Sdes /** Update count; get first element from tree1 again. */ 724266072Sdes count++; 725266072Sdes cur_node = ldns_radix_first(tree1); 726266072Sdes } else { 727266072Sdes cur_node = ldns_radix_next(cur_node); 728266072Sdes } 729266072Sdes } 730266072Sdes return LDNS_STATUS_OK; 731266072Sdes} 732266072Sdes 733266072Sdes 734266072Sdes/** 735266072Sdes * Call function for all nodes in the tree, such that leaf nodes are 736266072Sdes * called before parent nodes. 737266072Sdes * 738266072Sdes */ 739266072Sdesvoid 740266072Sdesldns_radix_traverse_postorder(ldns_radix_node_t* node, 741266072Sdes void (*func)(ldns_radix_node_t*, void*), void* arg) 742266072Sdes{ 743266072Sdes uint8_t i; 744266072Sdes if (!node) { 745266072Sdes return; 746266072Sdes } 747266072Sdes for (i=0; i < node->len; i++) { 748266072Sdes ldns_radix_traverse_postorder(node->array[i].edge, 749266072Sdes func, arg); 750266072Sdes } 751266072Sdes /** Call user function */ 752266072Sdes (*func)(node, arg); 753266072Sdes return; 754266072Sdes} 755266072Sdes 756266072Sdes 757266072Sdes/** Static helper functions */ 758266072Sdes 759266072Sdes/** 760266072Sdes * Find a prefix of the key. 761266072Sdes * @param tree: tree. 762266072Sdes * @param key: key. 763266072Sdes * @param len: length of key. 764266072Sdes * @param result: the longest prefix, the entry itself if *pos==len, 765266072Sdes * otherwise an array entry. 766266072Sdes * @param pos: position in string where next unmatched byte is. 767266072Sdes * If *pos==len, an exact match is found. 768266072Sdes * If *pos== 0, a "" match was found. 769266072Sdes * @return 0 (false) if no prefix found. 770266072Sdes * 771266072Sdes */ 772266072Sdesstatic int 773266072Sdesldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key, 774266072Sdes radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos) 775266072Sdes{ 776266072Sdes /** Start searching at the root node */ 777266072Sdes ldns_radix_node_t* n = tree->root; 778266072Sdes radix_strlen_t pos = 0; 779266072Sdes uint8_t byte; 780266072Sdes *respos = 0; 781266072Sdes *result = n; 782266072Sdes if (!n) { 783266072Sdes /** No root, no prefix found */ 784266072Sdes return 0; 785266072Sdes } 786266072Sdes /** For each node, look if we can make further progress */ 787266072Sdes while (n) { 788266072Sdes if (pos == len) { 789266072Sdes /** Exact match */ 790266072Sdes return 1; 791266072Sdes } 792266072Sdes byte = key[pos]; 793266072Sdes if (byte < n->offset) { 794266072Sdes /** key < node */ 795266072Sdes return 1; 796266072Sdes } 797266072Sdes byte -= n->offset; 798266072Sdes if (byte >= n->len) { 799266072Sdes /** key > node */ 800266072Sdes return 1; 801266072Sdes } 802266072Sdes /** So far, the trie matches */ 803266072Sdes pos++; 804266072Sdes if (n->array[byte].len != 0) { 805266072Sdes /** Must match additional string */ 806266072Sdes if (pos + n->array[byte].len > len) { 807266072Sdes return 1; /* no match at child node */ 808266072Sdes } 809266072Sdes if (memcmp(&key[pos], n->array[byte].str, 810266072Sdes n->array[byte].len) != 0) { 811266072Sdes return 1; /* no match at child node */ 812266072Sdes } 813266072Sdes pos += n->array[byte].len; 814266072Sdes } 815266072Sdes /** Continue searching prefix at this child node */ 816266072Sdes n = n->array[byte].edge; 817266072Sdes if (!n) { 818266072Sdes return 1; 819266072Sdes } 820266072Sdes /** Update the prefix node */ 821266072Sdes *respos = pos; 822266072Sdes *result = n; 823266072Sdes } 824266072Sdes /** Done */ 825266072Sdes return 1; 826266072Sdes} 827266072Sdes 828266072Sdes 829266072Sdes/** 830266072Sdes * Make space in the node's array for another byte. 831266072Sdes * @param node: node. 832266072Sdes * @param byte: byte. 833266072Sdes * @return 1 if successful, 0 otherwise. 834266072Sdes * 835266072Sdes */ 836266072Sdesstatic int 837266072Sdesldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte) 838266072Sdes{ 839266072Sdes /** Is there an array? */ 840266072Sdes if (!node->array) { 841266072Sdes assert(node->capacity == 0); 842266072Sdes /** No array, create new array */ 843266072Sdes node->array = LDNS_MALLOC(ldns_radix_array_t); 844266072Sdes if (!node->array) { 845266072Sdes return 0; 846266072Sdes } 847266072Sdes memset(&node->array[0], 0, sizeof(ldns_radix_array_t)); 848266072Sdes node->len = 1; 849266072Sdes node->capacity = 1; 850266072Sdes node->offset = byte; 851266072Sdes return 1; 852266072Sdes } 853266072Sdes /** Array exist */ 854266072Sdes assert(node->array != NULL); 855266072Sdes assert(node->capacity > 0); 856266072Sdes 857266072Sdes if (node->len == 0) { 858266072Sdes /** Unused array */ 859266072Sdes node->len = 1; 860266072Sdes node->offset = byte; 861266072Sdes } else if (byte < node->offset) { 862266072Sdes /** Byte is below the offset */ 863266072Sdes uint8_t index; 864266072Sdes uint16_t need = node->offset - byte; 865266072Sdes /** Is there enough capacity? */ 866266072Sdes if (node->len + need > node->capacity) { 867266072Sdes /** Not enough capacity, grow array */ 868266072Sdes if (!ldns_radix_array_grow(node, 869266072Sdes (unsigned) (node->len + need))) { 870266072Sdes return 0; /* failed to grow array */ 871266072Sdes } 872266072Sdes } 873266072Sdes /** Move items to the end */ 874266072Sdes memmove(&node->array[need], &node->array[0], 875266072Sdes node->len*sizeof(ldns_radix_array_t)); 876266072Sdes /** Fix parent index */ 877266072Sdes for (index = 0; index < node->len; index++) { 878266072Sdes if (node->array[index+need].edge) { 879266072Sdes node->array[index+need].edge->parent_index = 880266072Sdes index + need; 881266072Sdes } 882266072Sdes } 883266072Sdes /** Zero the first */ 884266072Sdes memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t)); 885266072Sdes node->len += need; 886266072Sdes node->offset = byte; 887266072Sdes } else if (byte - node->offset >= node->len) { 888266072Sdes /** Byte does not fit in array */ 889266072Sdes uint16_t need = (byte - node->offset) - node->len + 1; 890266072Sdes /** Is there enough capacity? */ 891266072Sdes if (node->len + need > node->capacity) { 892266072Sdes /** Not enough capacity, grow array */ 893266072Sdes if (!ldns_radix_array_grow(node, 894266072Sdes (unsigned) (node->len + need))) { 895266072Sdes return 0; /* failed to grow array */ 896266072Sdes } 897266072Sdes } 898266072Sdes /** Zero the added items */ 899266072Sdes memset(&node->array[node->len], 0, 900266072Sdes need*sizeof(ldns_radix_array_t)); 901266072Sdes node->len += need; 902266072Sdes } 903266072Sdes return 1; 904266072Sdes} 905266072Sdes 906266072Sdes 907266072Sdes/** 908266072Sdes * Grow the array. 909266072Sdes * @param node: node. 910266072Sdes * @param need: number of elements the array at least need to grow. 911266072Sdes * Can't be bigger than 256. 912266072Sdes * @return: 0 if failed, 1 if was successful. 913266072Sdes * 914266072Sdes */ 915266072Sdesstatic int 916266072Sdesldns_radix_array_grow(ldns_radix_node_t* node, unsigned need) 917266072Sdes{ 918266072Sdes unsigned size = ((unsigned)node->capacity)*2; 919266072Sdes ldns_radix_array_t* a = NULL; 920266072Sdes if (need > size) { 921266072Sdes size = need; 922266072Sdes } 923266072Sdes if (size > 256) { 924266072Sdes size = 256; 925266072Sdes } 926266072Sdes a = LDNS_XMALLOC(ldns_radix_array_t, size); 927266072Sdes if (!a) { 928266072Sdes return 0; 929266072Sdes } 930266072Sdes assert(node->len <= node->capacity); 931266072Sdes assert(node->capacity < size); 932266072Sdes memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t)); 933266072Sdes LDNS_FREE(node->array); 934266072Sdes node->array = a; 935266072Sdes node->capacity = size; 936266072Sdes return 1; 937266072Sdes} 938266072Sdes 939266072Sdes 940266072Sdes/** 941266072Sdes * Create a prefix in the array string. 942266072Sdes * @param array: array. 943266072Sdes * @param key: key. 944266072Sdes * @param pos: start position in key. 945266072Sdes * @param len: length of key. 946266072Sdes * @return 0 if failed, 1 if was successful. 947266072Sdes * 948266072Sdes */ 949266072Sdesstatic int 950266072Sdesldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key, 951266072Sdes radix_strlen_t pos, radix_strlen_t len) 952266072Sdes{ 953266072Sdes array->str = LDNS_XMALLOC(uint8_t, (len-pos)); 954266072Sdes if (!array->str) { 955266072Sdes return 0; 956266072Sdes } 957266072Sdes memmove(array->str, key+pos, len-pos); 958266072Sdes array->len = (len-pos); 959266072Sdes return 1; 960266072Sdes} 961266072Sdes 962266072Sdes 963266072Sdes/** 964266072Sdes * Allocate remainder from prefixes for a split. 965266072Sdes * @param prefixlen: length of prefix. 966266072Sdes * @param longer_str: the longer string. 967266072Sdes * @param longer_len: the longer string length. 968266072Sdes * @param split_str: the split string. 969266072Sdes * @param split_len: the split string length. 970266072Sdes * @return 0 if failed, 1 if successful. 971266072Sdes * 972266072Sdes */ 973266072Sdesstatic int 974266072Sdesldns_radix_prefix_remainder(radix_strlen_t prefix_len, 975266072Sdes uint8_t* longer_str, radix_strlen_t longer_len, 976266072Sdes uint8_t** split_str, radix_strlen_t* split_len) 977266072Sdes{ 978266072Sdes *split_len = longer_len - prefix_len; 979266072Sdes *split_str = LDNS_XMALLOC(uint8_t, (*split_len)); 980266072Sdes if (!*split_str) { 981266072Sdes return 0; 982266072Sdes } 983266072Sdes memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len); 984266072Sdes return 1; 985266072Sdes} 986266072Sdes 987266072Sdes 988266072Sdes/** 989266072Sdes * Create a split when two nodes have a shared prefix. 990266072Sdes * @param array: array. 991266072Sdes * @param key: key. 992266072Sdes * @param pos: start position in key. 993266072Sdes * @param len: length of the key. 994266072Sdes * @param add: node to be added. 995266072Sdes * @return 0 if failed, 1 if was successful. 996266072Sdes * 997266072Sdes */ 998266072Sdesstatic int 999266072Sdesldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key, 1000266072Sdes radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add) 1001266072Sdes{ 1002266072Sdes uint8_t* str_to_add = key + pos; 1003266072Sdes radix_strlen_t strlen_to_add = len - pos; 1004266072Sdes 1005266072Sdes if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add, 1006266072Sdes array->str, array->len)) { 1007266072Sdes /** The string to add is a prefix of the existing string */ 1008266072Sdes uint8_t* split_str = NULL, *dup_str = NULL; 1009266072Sdes radix_strlen_t split_len = 0; 1010266072Sdes /** 1011266072Sdes * Example 5: 'ld' 1012266072Sdes * | [0] 1013266072Sdes * --| [d+ns] dns 1014266072Sdes * --| [e+dns] edns 1015266072Sdes * --| [l+d] ld 1016266072Sdes * ----| [n+s] ldns 1017266072Sdes **/ 1018266072Sdes assert(strlen_to_add < array->len); 1019266072Sdes /** Store the remainder in the split string */ 1020266072Sdes if (array->len - strlen_to_add > 1) { 1021266072Sdes if (!ldns_radix_prefix_remainder(strlen_to_add+1, 1022266072Sdes array->str, array->len, &split_str, 1023266072Sdes &split_len)) { 1024266072Sdes return 0; 1025266072Sdes } 1026266072Sdes } 1027266072Sdes /** Duplicate the string to add */ 1028266072Sdes if (strlen_to_add != 0) { 1029266072Sdes dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add); 1030266072Sdes if (!dup_str) { 1031266072Sdes LDNS_FREE(split_str); 1032266072Sdes return 0; 1033266072Sdes } 1034266072Sdes memcpy(dup_str, str_to_add, strlen_to_add); 1035266072Sdes } 1036266072Sdes /** Make space in array for the new node */ 1037266072Sdes if (!ldns_radix_array_space(add, 1038266072Sdes array->str[strlen_to_add])) { 1039266072Sdes LDNS_FREE(split_str); 1040266072Sdes LDNS_FREE(dup_str); 1041266072Sdes return 0; 1042266072Sdes } 1043266072Sdes /** 1044266072Sdes * The added node should go direct under the existing parent. 1045266072Sdes * The existing node should go under the added node. 1046266072Sdes */ 1047266072Sdes add->parent = array->edge->parent; 1048266072Sdes add->parent_index = array->edge->parent_index; 1049266072Sdes add->array[0].edge = array->edge; 1050266072Sdes add->array[0].str = split_str; 1051266072Sdes add->array[0].len = split_len; 1052266072Sdes array->edge->parent = add; 1053266072Sdes array->edge->parent_index = 0; 1054266072Sdes LDNS_FREE(array->str); 1055266072Sdes array->edge = add; 1056266072Sdes array->str = dup_str; 1057266072Sdes array->len = strlen_to_add; 1058266072Sdes } else if (ldns_radix_str_is_prefix(array->str, array->len, 1059266072Sdes str_to_add, strlen_to_add)) { 1060266072Sdes /** The existing string is a prefix of the string to add */ 1061266072Sdes /** 1062266072Sdes * Example 6: 'dns-ng' 1063266072Sdes * | [0] 1064266072Sdes * --| [d+ns] dns 1065266072Sdes * ----| [-+ng] dns-ng 1066266072Sdes * --| [e+dns] edns 1067266072Sdes * --| [l+d] ld 1068266072Sdes * ----| [n+s] ldns 1069266072Sdes **/ 1070266072Sdes uint8_t* split_str = NULL; 1071266072Sdes radix_strlen_t split_len = 0; 1072266072Sdes assert(array->len < strlen_to_add); 1073266072Sdes if (strlen_to_add - array->len > 1) { 1074266072Sdes if (!ldns_radix_prefix_remainder(array->len+1, 1075266072Sdes str_to_add, strlen_to_add, &split_str, 1076266072Sdes &split_len)) { 1077266072Sdes return 0; 1078266072Sdes } 1079266072Sdes } 1080266072Sdes /** Make space in array for the new node */ 1081266072Sdes if (!ldns_radix_array_space(array->edge, 1082266072Sdes str_to_add[array->len])) { 1083266072Sdes LDNS_FREE(split_str); 1084266072Sdes return 0; 1085266072Sdes } 1086266072Sdes /** 1087266072Sdes * The added node should go direct under the existing node. 1088266072Sdes */ 1089266072Sdes add->parent = array->edge; 1090266072Sdes add->parent_index = str_to_add[array->len] - 1091266072Sdes array->edge->offset; 1092266072Sdes array->edge->array[add->parent_index].edge = add; 1093266072Sdes array->edge->array[add->parent_index].str = split_str; 1094266072Sdes array->edge->array[add->parent_index].len = split_len; 1095266072Sdes } else { 1096266072Sdes /** Create a new split node. */ 1097266072Sdes /** 1098266072Sdes * Example 7: 'dndns' 1099266072Sdes * | [0] 1100266072Sdes * --| [d+n] 1101266072Sdes * ----| [d+ns] dndns 1102266072Sdes * ----| [s] dns 1103266072Sdes * ------| [-+ng] dns-ng 1104266072Sdes * --| [e+dns] edns 1105266072Sdes * --| [l+d] ld 1106266072Sdes * ----| [n+s] ldns 1107266072Sdes **/ 1108266072Sdes ldns_radix_node_t* common = NULL; 1109266072Sdes uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL; 1110266072Sdes radix_strlen_t common_len = 0, l1 = 0, l2 = 0; 1111266072Sdes common_len = ldns_radix_str_common(array->str, array->len, 1112266072Sdes str_to_add, strlen_to_add); 1113266072Sdes assert(common_len < array->len); 1114266072Sdes assert(common_len < strlen_to_add); 1115266072Sdes /** Create the new common node. */ 1116266072Sdes common = ldns_radix_new_node(NULL, (uint8_t*)"", 0); 1117266072Sdes if (!common) { 1118266072Sdes return 0; 1119266072Sdes } 1120266072Sdes if (array->len - common_len > 1) { 1121266072Sdes if (!ldns_radix_prefix_remainder(common_len+1, 1122266072Sdes array->str, array->len, &s1, &l1)) { 1123266072Sdes return 0; 1124266072Sdes } 1125266072Sdes } 1126266072Sdes if (strlen_to_add - common_len > 1) { 1127266072Sdes if (!ldns_radix_prefix_remainder(common_len+1, 1128266072Sdes str_to_add, strlen_to_add, &s2, &l2)) { 1129266072Sdes return 0; 1130266072Sdes } 1131266072Sdes } 1132266072Sdes /** Create the shared prefix. */ 1133266072Sdes if (common_len > 0) { 1134266072Sdes common_str = LDNS_XMALLOC(uint8_t, common_len); 1135266072Sdes if (!common_str) { 1136266072Sdes LDNS_FREE(common); 1137266072Sdes LDNS_FREE(s1); 1138266072Sdes LDNS_FREE(s2); 1139266072Sdes return 0; 1140266072Sdes } 1141266072Sdes memcpy(common_str, str_to_add, common_len); 1142266072Sdes } 1143266072Sdes /** Make space in the common node array. */ 1144266072Sdes if (!ldns_radix_array_space(common, array->str[common_len]) || 1145266072Sdes !ldns_radix_array_space(common, str_to_add[common_len])) { 1146266072Sdes LDNS_FREE(common->array); 1147266072Sdes LDNS_FREE(common); 1148266072Sdes LDNS_FREE(common_str); 1149266072Sdes LDNS_FREE(s1); 1150266072Sdes LDNS_FREE(s2); 1151266072Sdes return 0; 1152266072Sdes } 1153266072Sdes /** 1154266072Sdes * The common node should go direct under the parent node. 1155266072Sdes * The added and existing nodes go under the common node. 1156266072Sdes */ 1157266072Sdes common->parent = array->edge->parent; 1158266072Sdes common->parent_index = array->edge->parent_index; 1159266072Sdes array->edge->parent = common; 1160266072Sdes array->edge->parent_index = array->str[common_len] - 1161266072Sdes common->offset; 1162266072Sdes add->parent = common; 1163266072Sdes add->parent_index = str_to_add[common_len] - common->offset; 1164266072Sdes common->array[array->edge->parent_index].edge = array->edge; 1165266072Sdes common->array[array->edge->parent_index].str = s1; 1166266072Sdes common->array[array->edge->parent_index].len = l1; 1167266072Sdes common->array[add->parent_index].edge = add; 1168266072Sdes common->array[add->parent_index].str = s2; 1169266072Sdes common->array[add->parent_index].len = l2; 1170266072Sdes LDNS_FREE(array->str); 1171266072Sdes array->edge = common; 1172266072Sdes array->str = common_str; 1173266072Sdes array->len = common_len; 1174266072Sdes } 1175266072Sdes return 1; 1176266072Sdes} 1177266072Sdes 1178266072Sdes 1179266072Sdes/** 1180266072Sdes * Check if one string prefix of other string. 1181266072Sdes * @param str1: one string. 1182266072Sdes * @param len1: one string length. 1183266072Sdes * @param str2: other string. 1184266072Sdes * @param len2: other string length. 1185266072Sdes * @return 1 if prefix, 0 otherwise. 1186266072Sdes * 1187266072Sdes */ 1188266072Sdesstatic int 1189266072Sdesldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1, 1190266072Sdes uint8_t* str2, radix_strlen_t len2) 1191266072Sdes{ 1192266072Sdes if (len1 == 0) { 1193266072Sdes return 1; /* empty prefix is also a prefix */ 1194266072Sdes } 1195266072Sdes if (len1 > len2) { 1196266072Sdes return 0; /* len1 is longer so str1 cannot be a prefix */ 1197266072Sdes } 1198266072Sdes return (memcmp(str1, str2, len1) == 0); 1199266072Sdes} 1200266072Sdes 1201266072Sdes 1202266072Sdes/** 1203266072Sdes * Return the number of bytes in common for the two strings. 1204266072Sdes * @param str1: one string. 1205266072Sdes * @param len1: one string length. 1206266072Sdes * @param str2: other string. 1207266072Sdes * @param len2: other string length. 1208266072Sdes * @return length of substring that the two strings have in common. 1209266072Sdes * 1210266072Sdes */ 1211266072Sdesstatic radix_strlen_t 1212266072Sdesldns_radix_str_common(uint8_t* str1, radix_strlen_t len1, 1213266072Sdes uint8_t* str2, radix_strlen_t len2) 1214266072Sdes{ 1215266072Sdes radix_strlen_t i, max = (len1<len2)?len1:len2; 1216266072Sdes for (i=0; i<max; i++) { 1217266072Sdes if (str1[i] != str2[i]) { 1218266072Sdes return i; 1219266072Sdes } 1220266072Sdes } 1221266072Sdes return max; 1222266072Sdes} 1223266072Sdes 1224266072Sdes 1225266072Sdes/** 1226266072Sdes * Find the next element in the subtree of this node. 1227266072Sdes * @param node: node. 1228266072Sdes * @return: node with next element. 1229266072Sdes * 1230266072Sdes */ 1231266072Sdesstatic ldns_radix_node_t* 1232266072Sdesldns_radix_next_in_subtree(ldns_radix_node_t* node) 1233266072Sdes{ 1234266072Sdes uint16_t i; 1235266072Sdes ldns_radix_node_t* next; 1236266072Sdes /** Try every subnode. */ 1237266072Sdes for (i = 0; i < node->len; i++) { 1238266072Sdes if (node->array[i].edge) { 1239266072Sdes /** Node itself. */ 1240266072Sdes if (node->array[i].edge->data) { 1241266072Sdes return node->array[i].edge; 1242266072Sdes } 1243266072Sdes /** Dive into subtree. */ 1244266072Sdes next = ldns_radix_next_in_subtree(node->array[i].edge); 1245266072Sdes if (next) { 1246266072Sdes return next; 1247266072Sdes } 1248266072Sdes } 1249266072Sdes } 1250266072Sdes return NULL; 1251266072Sdes} 1252266072Sdes 1253266072Sdes 1254266072Sdes/** 1255266072Sdes * Find the previous element in the array of this node, from index. 1256266072Sdes * @param node: node. 1257266072Sdes * @param index: index. 1258266072Sdes * @return previous node from index. 1259266072Sdes * 1260266072Sdes */ 1261266072Sdesstatic ldns_radix_node_t* 1262266072Sdesldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index) 1263266072Sdes{ 1264266072Sdes uint8_t i = index; 1265266072Sdes while (i > 0) { 1266266072Sdes i--; 1267266072Sdes if (node->array[i].edge) { 1268266072Sdes ldns_radix_node_t* prev = 1269266072Sdes ldns_radix_last_in_subtree_incl_self(node); 1270266072Sdes if (prev) { 1271266072Sdes return prev; 1272266072Sdes } 1273266072Sdes } 1274266072Sdes } 1275266072Sdes return NULL; 1276266072Sdes} 1277266072Sdes 1278266072Sdes 1279266072Sdes/** 1280266072Sdes * Find last node in subtree, or this node (if have data). 1281266072Sdes * @param node: node. 1282266072Sdes * @return last node in subtree, or this node, or NULL. 1283266072Sdes * 1284266072Sdes */ 1285266072Sdesstatic ldns_radix_node_t* 1286266072Sdesldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node) 1287266072Sdes{ 1288266072Sdes ldns_radix_node_t* last = ldns_radix_last_in_subtree(node); 1289266072Sdes if (last) { 1290266072Sdes return last; 1291266072Sdes } else if (node->data) { 1292266072Sdes return node; 1293266072Sdes } 1294266072Sdes return NULL; 1295266072Sdes} 1296266072Sdes 1297266072Sdes 1298266072Sdes/** 1299266072Sdes * Find last node in subtree. 1300266072Sdes * @param node: node. 1301266072Sdes * @return last node in subtree. 1302266072Sdes * 1303266072Sdes */ 1304266072Sdesstatic ldns_radix_node_t* 1305266072Sdesldns_radix_last_in_subtree(ldns_radix_node_t* node) 1306266072Sdes{ 1307266072Sdes int i; 1308266072Sdes /** Look for the most right leaf node. */ 1309266072Sdes for (i=(int)(node->len)-1; i >= 0; i--) { 1310266072Sdes if (node->array[i].edge) { 1311266072Sdes /** Keep looking for the most right leaf node. */ 1312266072Sdes if (node->array[i].edge->len > 0) { 1313266072Sdes ldns_radix_node_t* last = 1314266072Sdes ldns_radix_last_in_subtree( 1315266072Sdes node->array[i].edge); 1316266072Sdes if (last) { 1317266072Sdes return last; 1318266072Sdes } 1319266072Sdes } 1320266072Sdes /** Could this be the most right leaf node? */ 1321266072Sdes if (node->array[i].edge->data) { 1322266072Sdes return node->array[i].edge; 1323266072Sdes } 1324266072Sdes } 1325266072Sdes } 1326266072Sdes return NULL; 1327266072Sdes} 1328266072Sdes 1329266072Sdes 1330266072Sdes/** 1331266072Sdes * Fix tree after deleting element. 1332266072Sdes * @param tree: tree. 1333266072Sdes * @param node: node with deleted element. 1334266072Sdes * 1335266072Sdes */ 1336266072Sdesstatic void 1337266072Sdesldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node) 1338266072Sdes{ 1339266072Sdes while (node) { 1340266072Sdes if (node->data) { 1341266072Sdes /** Thou should not delete nodes with data attached. */ 1342266072Sdes return; 1343266072Sdes } else if (node->len == 1 && node->parent) { 1344266072Sdes /** Node with one child is fold back into. */ 1345266072Sdes ldns_radix_cleanup_onechild(node); 1346266072Sdes return; 1347266072Sdes } else if (node->len == 0) { 1348266072Sdes /** Leaf node. */ 1349266072Sdes ldns_radix_node_t* parent = node->parent; 1350266072Sdes if (!parent) { 1351266072Sdes /** The root is a leaf node. */ 1352266072Sdes ldns_radix_node_free(node, NULL); 1353266072Sdes tree->root = NULL; 1354266072Sdes return; 1355266072Sdes } 1356266072Sdes /** Cleanup leaf node and continue with parent. */ 1357266072Sdes ldns_radix_cleanup_leaf(node); 1358266072Sdes node = parent; 1359266072Sdes } else { 1360266072Sdes /** 1361266072Sdes * Node cannot be deleted, because it has edge nodes 1362266072Sdes * and no parent to fix up to. 1363266072Sdes */ 1364266072Sdes return; 1365266072Sdes } 1366266072Sdes } 1367266072Sdes /** Not reached. */ 1368266072Sdes return; 1369266072Sdes} 1370266072Sdes 1371266072Sdes 1372266072Sdes/** 1373266072Sdes * Clean up a node with one child. 1374266072Sdes * @param node: node with one child. 1375266072Sdes * 1376266072Sdes */ 1377266072Sdesstatic void 1378266072Sdesldns_radix_cleanup_onechild(ldns_radix_node_t* node) 1379266072Sdes{ 1380266072Sdes uint8_t* join_str; 1381266072Sdes radix_strlen_t join_len; 1382266072Sdes uint8_t parent_index = node->parent_index; 1383266072Sdes ldns_radix_node_t* child = node->array[0].edge; 1384266072Sdes ldns_radix_node_t* parent = node->parent; 1385266072Sdes 1386266072Sdes /** Node has one child, merge the child node into the parent node. */ 1387266072Sdes assert(parent_index < parent->len); 1388266072Sdes join_len = parent->array[parent_index].len + node->array[0].len + 1; 1389266072Sdes 1390266072Sdes join_str = LDNS_XMALLOC(uint8_t, join_len); 1391266072Sdes if (!join_str) { 1392266072Sdes /** 1393266072Sdes * Cleanup failed due to out of memory. 1394266072Sdes * This tree is now inefficient, with the empty node still 1395266072Sdes * existing, but it is still valid. 1396266072Sdes */ 1397266072Sdes return; 1398266072Sdes } 1399266072Sdes 1400266072Sdes memcpy(join_str, parent->array[parent_index].str, 1401266072Sdes parent->array[parent_index].len); 1402266072Sdes join_str[parent->array[parent_index].len] = child->parent_index + 1403266072Sdes node->offset; 1404266072Sdes memmove(join_str + parent->array[parent_index].len+1, 1405266072Sdes node->array[0].str, node->array[0].len); 1406266072Sdes 1407266072Sdes LDNS_FREE(parent->array[parent_index].str); 1408266072Sdes parent->array[parent_index].str = join_str; 1409266072Sdes parent->array[parent_index].len = join_len; 1410266072Sdes parent->array[parent_index].edge = child; 1411266072Sdes child->parent = parent; 1412266072Sdes child->parent_index = parent_index; 1413266072Sdes ldns_radix_node_free(node, NULL); 1414266072Sdes return; 1415266072Sdes} 1416266072Sdes 1417266072Sdes 1418266072Sdes/** 1419266072Sdes * Clean up a leaf node. 1420266072Sdes * @param node: leaf node. 1421266072Sdes * 1422266072Sdes */ 1423266072Sdesstatic void 1424266072Sdesldns_radix_cleanup_leaf(ldns_radix_node_t* node) 1425266072Sdes{ 1426266072Sdes uint8_t parent_index = node->parent_index; 1427266072Sdes ldns_radix_node_t* parent = node->parent; 1428266072Sdes /** Delete lead node and fix parent array. */ 1429266072Sdes assert(parent_index < parent->len); 1430266072Sdes ldns_radix_node_free(node, NULL); 1431266072Sdes LDNS_FREE(parent->array[parent_index].str); 1432266072Sdes parent->array[parent_index].str = NULL; 1433266072Sdes parent->array[parent_index].len = 0; 1434266072Sdes parent->array[parent_index].edge = NULL; 1435266072Sdes /** Fix array in parent. */ 1436266072Sdes if (parent->len == 1) { 1437266072Sdes ldns_radix_node_array_free(parent); 1438266072Sdes } else if (parent_index == 0) { 1439266072Sdes ldns_radix_node_array_free_front(parent); 1440266072Sdes } else { 1441266072Sdes ldns_radix_node_array_free_end(parent); 1442266072Sdes } 1443266072Sdes return; 1444266072Sdes} 1445266072Sdes 1446266072Sdes 1447266072Sdes/** 1448266072Sdes * Free a radix node. 1449266072Sdes * @param node: node. 1450266072Sdes * @param arg: user argument. 1451266072Sdes * 1452266072Sdes */ 1453266072Sdesstatic void 1454266072Sdesldns_radix_node_free(ldns_radix_node_t* node, void* arg) 1455266072Sdes{ 1456266072Sdes uint16_t i; 1457266072Sdes (void) arg; 1458266072Sdes if (!node) { 1459266072Sdes return; 1460266072Sdes } 1461266072Sdes for (i=0; i < node->len; i++) { 1462266072Sdes LDNS_FREE(node->array[i].str); 1463266072Sdes } 1464266072Sdes node->key = NULL; 1465266072Sdes node->klen = 0; 1466266072Sdes LDNS_FREE(node->array); 1467266072Sdes LDNS_FREE(node); 1468266072Sdes return; 1469266072Sdes} 1470266072Sdes 1471266072Sdes 1472266072Sdes/** 1473266072Sdes * Free select edge array. 1474266072Sdes * @param node: node. 1475266072Sdes * 1476266072Sdes */ 1477266072Sdesstatic void 1478266072Sdesldns_radix_node_array_free(ldns_radix_node_t* node) 1479266072Sdes{ 1480266072Sdes node->offset = 0; 1481266072Sdes node->len = 0; 1482266072Sdes LDNS_FREE(node->array); 1483266072Sdes node->array = NULL; 1484266072Sdes node->capacity = 0; 1485266072Sdes return; 1486266072Sdes} 1487266072Sdes 1488266072Sdes 1489266072Sdes/** 1490266072Sdes * Free front of select edge array. 1491266072Sdes * @param node: node. 1492266072Sdes * 1493266072Sdes */ 1494266072Sdesstatic void 1495266072Sdesldns_radix_node_array_free_front(ldns_radix_node_t* node) 1496266072Sdes{ 1497266072Sdes uint16_t i, n = 0; 1498266072Sdes /** Remove until a non NULL entry. */ 1499266072Sdes while (n < node->len && node->array[n].edge == NULL) { 1500266072Sdes n++; 1501266072Sdes } 1502266072Sdes if (n == 0) { 1503266072Sdes return; 1504266072Sdes } 1505266072Sdes if (n == node->len) { 1506266072Sdes ldns_radix_node_array_free(node); 1507266072Sdes return; 1508266072Sdes } 1509266072Sdes assert(n < node->len); 1510266072Sdes assert((int) n <= (255 - (int) node->offset)); 1511266072Sdes memmove(&node->array[0], &node->array[n], 1512266072Sdes (node->len - n)*sizeof(ldns_radix_array_t)); 1513266072Sdes node->offset += n; 1514266072Sdes node->len -= n; 1515266072Sdes for (i=0; i < node->len; i++) { 1516266072Sdes if (node->array[i].edge) { 1517266072Sdes node->array[i].edge->parent_index = i; 1518266072Sdes } 1519266072Sdes } 1520266072Sdes ldns_radix_array_reduce(node); 1521266072Sdes return; 1522266072Sdes} 1523266072Sdes 1524266072Sdes 1525266072Sdes/** 1526266072Sdes * Free front of select edge array. 1527266072Sdes * @param node: node. 1528266072Sdes * 1529266072Sdes */ 1530266072Sdesstatic void 1531266072Sdesldns_radix_node_array_free_end(ldns_radix_node_t* node) 1532266072Sdes{ 1533266072Sdes uint16_t n = 0; 1534266072Sdes /** Shorten array. */ 1535266072Sdes while (n < node->len && node->array[node->len-1-n].edge == NULL) { 1536266072Sdes n++; 1537266072Sdes } 1538266072Sdes if (n == 0) { 1539266072Sdes return; 1540266072Sdes } 1541266072Sdes if (n == node->len) { 1542266072Sdes ldns_radix_node_array_free(node); 1543266072Sdes return; 1544266072Sdes } 1545266072Sdes assert(n < node->len); 1546266072Sdes node->len -= n; 1547266072Sdes ldns_radix_array_reduce(node); 1548266072Sdes return; 1549266072Sdes} 1550266072Sdes 1551266072Sdes 1552266072Sdes/** 1553266072Sdes * Reduce the capacity of the array if needed. 1554266072Sdes * @param node: node. 1555266072Sdes * 1556266072Sdes */ 1557266072Sdesstatic void 1558266072Sdesldns_radix_array_reduce(ldns_radix_node_t* node) 1559266072Sdes{ 1560266072Sdes if (node->len <= node->capacity/2 && node->len != node->capacity) { 1561266072Sdes ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t, 1562266072Sdes node->len); 1563266072Sdes if (!a) { 1564266072Sdes return; 1565266072Sdes } 1566266072Sdes memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len); 1567266072Sdes LDNS_FREE(node->array); 1568266072Sdes node->array = a; 1569266072Sdes node->capacity = node->len; 1570266072Sdes } 1571266072Sdes return; 1572266072Sdes} 1573266072Sdes 1574266072Sdes 1575266072Sdes/** 1576266072Sdes * Return this element if it exists, the previous otherwise. 1577266072Sdes * @param node: from this node. 1578266072Sdes * @param result: result node. 1579266072Sdes * 1580266072Sdes */ 1581266072Sdesstatic void 1582266072Sdesldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result) 1583266072Sdes{ 1584266072Sdes if (node->data) { 1585266072Sdes *result = node; 1586266072Sdes } else { 1587266072Sdes *result = ldns_radix_prev(node); 1588266072Sdes } 1589266072Sdes return; 1590266072Sdes} 1591