Line data    Source code

       1             : /*
       2             :  * lwan - web server
       3             :  * Copyright (c) 2012 L. A. F. Pereira <l@tia.mat.br>
       4             :  *
       5             :  * This program is free software; you can redistribute it and/or
       6             :  * modify it under the terms of the GNU General Public License
       7             :  * as published by the Free Software Foundation; either version 2
       8             :  * of the License, or any later version.
       9             :  *
      10             :  * This program is distributed in the hope that it will be useful,
      11             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      12             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13             :  * GNU General Public License for more details.
      14             :  *
      15             :  * You should have received a copy of the GNU General Public License
      16             :  * along with this program; if not, write to the Free Software
      17             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
      18             :  * USA.
      19             :  */
      20             : 
      21             : #include <stdlib.h>
      22             : #include <string.h>
      23             : 
      24             : #include "lwan-private.h"
      25             : 
      26             : struct lwan_trie_node {
      27             :     struct lwan_trie_node *next[8];
      28             :     struct lwan_trie_leaf *leaf;
      29             :     int ref_count;
      30             : };
      31             : 
      32             : struct lwan_trie_leaf {
      33             :     char *key;
      34             :     void *data;
      35             :     struct lwan_trie_leaf *next;
      36             : };
      37             : 
      38          92 : bool lwan_trie_init(struct lwan_trie *trie, void (*free_node)(void *data))
      39             : {
      40          92 :     if (!trie)
      41           0 :         return false;
      42          92 :     trie->root = NULL;
      43          92 :     trie->free_node = free_node;
      44          92 :     return true;
      45             : }
      46             : 
      47             : static ALWAYS_INLINE struct lwan_trie_leaf *
      48             : find_leaf_with_key(struct lwan_trie_node *node, const char *key, size_t len)
      49             : {
      50        2563 :     struct lwan_trie_leaf *leaf = node->leaf;
      51             : 
      52        2563 :     if (!leaf)
      53        1959 :         return NULL;
      54             : 
      55         604 :     if (!leaf->next) /* No collisions -- no need to strncmp() */
      56         604 :         return leaf;
      57             : 
      58           0 :     for (; leaf; leaf = leaf->next) {
      59           0 :         if (!strncmp(leaf->key, key, len - 1))
      60           0 :             return leaf;
      61             :     }
      62             : 
      63           0 :     return NULL;
      64             : }
      65             : 
      66             : #define GET_NODE()                                                             \
      67             :     do {                                                                       \
      68             :         if (!(node = *knode)) {                                                \
      69             :             *knode = node = lwan_aligned_alloc(sizeof(*node), 64);             \
      70             :             if (!node)                                                         \
      71             :                 goto oom;                                                      \
      72             :             memset(node, 0, sizeof(*node));                                    \
      73             :         }                                                                      \
      74             :         ++node->ref_count;                                                     \
      75             :     } while (0)
      76             : 
      77        1959 : void lwan_trie_add(struct lwan_trie *trie, const char *key, void *data)
      78             : {
      79        1959 :     if (UNLIKELY(!trie || !key || !data))
      80           0 :         return;
      81             : 
      82             :     struct lwan_trie_node **knode, *node;
      83        1959 :     const char *orig_key = key;
      84             : 
      85             :     /* Traverse the trie, allocating nodes if necessary */
      86       17191 :     for (knode = &trie->root; *key; knode = &node->next[(int)(*key++ & 7)])
      87       15232 :         GET_NODE();
      88             : 
      89             :     /* Get the leaf node (allocate it if necessary) */
      90        1959 :     GET_NODE();
      91             : 
      92             :     struct lwan_trie_leaf *leaf =
      93        1959 :         find_leaf_with_key(node, orig_key, (size_t)(key - orig_key));
      94        1959 :     bool had_key = leaf;
      95        1959 :     if (!leaf) {
      96        1959 :         leaf = lwan_aligned_alloc(sizeof(*leaf), 64);
      97        1959 :         if (!leaf)
      98           0 :             lwan_status_critical_perror("malloc");
      99           0 :     } else if (trie->free_node) {
     100           0 :         trie->free_node(leaf->data);
     101             :     }
     102             : 
     103        1959 :     leaf->data = data;
     104        1959 :     if (!had_key) {
     105        1959 :         leaf->key = strdup(orig_key);
     106        1959 :         leaf->next = node->leaf;
     107        1959 :         node->leaf = leaf;
     108             :     }
     109        1959 :     return;
     110             : 
     111           0 : oom:
     112           0 :     lwan_status_critical_perror("calloc");
     113             : }
     114             : 
     115             : #undef GET_NODE
     116             : 
     117             : static ALWAYS_INLINE struct lwan_trie_node *
     118             : lookup_node(struct lwan_trie_node *root, const char *key, size_t *prefix_len)
     119             : {
     120         604 :     struct lwan_trie_node *node, *previous_node = NULL;
     121         604 :     const char *orig_key = key;
     122             : 
     123        4533 :     for (node = root; node && *key; node = node->next[(int)(*key++ & 7)]) {
     124        3929 :         if (node->leaf)
     125         603 :             previous_node = node;
     126             :     }
     127             : 
     128         604 :     *prefix_len = (size_t)(key - orig_key);
     129             : 
     130         604 :     if (node && node->leaf)
     131         530 :         return node;
     132             : 
     133          74 :     return previous_node;
     134             : }
     135             : 
     136         604 : ALWAYS_INLINE void *lwan_trie_lookup_prefix(struct lwan_trie *trie,
     137             :                                             const char *key)
     138             : {
     139         604 :     assert(trie);
     140         604 :     assert(key);
     141             : 
     142             :     size_t prefix_len;
     143         604 :     struct lwan_trie_node *node = lookup_node(trie->root, key, &prefix_len);
     144             : 
     145         604 :     if (node) {
     146         604 :         struct lwan_trie_leaf *leaf = find_leaf_with_key(node, key, prefix_len);
     147             : 
     148         604 :         if (leaf)
     149         604 :             return leaf->data;
     150             :     }
     151             : 
     152           0 :     return NULL;
     153             : }
     154             : 
     155           0 : static void lwan_trie_node_destroy(struct lwan_trie *trie,
     156             :                                    struct lwan_trie_node *node)
     157             : {
     158           0 :     if (!node)
     159           0 :         return;
     160             : 
     161           0 :     int32_t nodes_destroyed = node->ref_count;
     162             : 
     163           0 :     for (struct lwan_trie_leaf *leaf = node->leaf; leaf;) {
     164           0 :         struct lwan_trie_leaf *tmp = leaf->next;
     165             : 
     166           0 :         if (trie->free_node)
     167           0 :             trie->free_node(leaf->data);
     168             : 
     169           0 :         free(leaf->key);
     170           0 :         free(leaf);
     171           0 :         leaf = tmp;
     172             :     }
     173             : 
     174           0 :     for (int32_t i = 0; nodes_destroyed > 0 && i < 8; i++) {
     175           0 :         if (node->next[i]) {
     176           0 :             lwan_trie_node_destroy(trie, node->next[i]);
     177           0 :             --nodes_destroyed;
     178             :         }
     179             :     }
     180             : 
     181           0 :     free(node);
     182             : }
     183             : 
     184           0 : void lwan_trie_destroy(struct lwan_trie *trie)
     185             : {
     186           0 :     if (!trie || !trie->root)
     187           0 :         return;
     188           0 :     lwan_trie_node_destroy(trie, trie->root);
     189             : }