 @@ -1,17 +1,17 @@
-/*	$NetBSD: radixtree.c,v 1.17.2.4 2012/08/01 21:09:27 yamt Exp $	*/
+/*	$NetBSD: radixtree.c,v 1.17.2.5 2014/03/25 16:21:08 yamt Exp $	*/
 /*-
- * Copyright (c)2011,2012 YAMAMOTO Takashi,
+ * Copyright (c)2011,2012,2013 YAMAMOTO Takashi,
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 @@ -34,78 +34,105 @@
  * This is an implementation of radix tree, whose keys are uint64_t and leafs
  * are user provided pointers.
+ *
  * Leaf nodes are just void * and this implementation doesn't care about
  * what they actually point to.  However, this implementation has an assumption
  * about their alignment.  Specifically, this implementation assumes that their
  * 2 LSBs are always zero and uses them for internal accounting.
+ *
  * Intermediate nodes and memory allocation:
+ *
  * Intermediate nodes are automatically allocated and freed internally and
  * basically users don't need to care about them.  The allocation is done via
  * pool_cache_get(9) for _KERNEL, malloc(3) for userland, and alloc() for
- * _STANDALONE environment.  Only radix_tree_insert_node function can allocatei
+ * _STANDALONE environment.  Only radix_tree_insert_node function can allocate
  * memory for intermediate nodes and thus can fail for ENOMEM.
+ *
- * Efficiency:
+ * Memory Efficiency:
+ *
  * It's designed to work efficiently with dense index distribution.
  * The memory consumption (number of necessary intermediate nodes) heavily
  * depends on the index distribution.  Basically, more dense index distribution
  * consumes less nodes per item.  Approximately,
+ *
  *  - the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node.
  *    it would look like the following.
+ *
  *     root (t_height=1)
  *      |
  *      v
  *      [ | | | ]   (intermediate node.  RADIX_TREE_PTR_PER_NODE=4 in this fig)
  *       | | | |
  *       v v v v
  *       p p p p    (items)
+ *
  *  - the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item.
  *    it would look like the following if RADIX_TREE_MAX_HEIGHT=3.
+ *
- * The height of tree is dynamic.  It's smaller if only small index values are
+ *     root (t_height=3)
- * used.  As an extreme case, if only index 0 is used, the corresponding value
+ *      |
- * is directly stored in the root of the tree (struct radix_tree) without
+ *      v
- * allocating any intermediate nodes.
+ *      [ | | | ]
  *           |
  *           v
  *           [ | | | ]
  *                |
  *                v
  *                [ | | | ]
  *                   |
  *                   v
  *                   p
+ *
  * The height of tree (t_height) is dynamic.  It's smaller if only small
  * index values are used.  As an extreme case, if only index 0 is used,
  * the corresponding value is directly stored in the root of the tree
  * (struct radix_tree) without allocating any intermediate nodes.  In that
  * case, t_height=0.
+ *
  * Gang lookup:
+ *
  * This implementation provides a way to scan many nodes quickly via
  * radix_tree_gang_lookup_node function and its varients.
+ *
  * Tags:
+ *
  * This implementation provides tagging functionality, which allows quick
  * scanning of a subset of leaf nodes.  Leaf nodes are untagged when inserted
  * into the tree and can be tagged by radix_tree_set_tag function.
  * radix_tree_gang_lookup_tagged_node function and its variants returns only
  * leaf nodes with the given tag.  To reduce amount of nodes to visit for
  * these functions, this implementation keeps tagging information in internal
  * intermediate nodes and quickly skips uninterested parts of a tree.
+ *
  * A tree has RADIX_TREE_TAG_ID_MAX independent tag spaces, each of which are
  * identified by an zero-origin numbers, tagid.  For the current implementation,
  * RADIX_TREE_TAG_ID_MAX is 2.  A set of tags is described as a bitmask tagmask,
  * which is a bitwise OR of (1 << tagid).
  */
 #include <sys/cdefs.h>
 #if defined(_KERNEL) || defined(_STANDALONE)
-__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17.2.4 2012/08/01 21:09:27 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17.2.5 2014/03/25 16:21:08 yamt Exp $");
 #include <sys/param.h>
 #include <sys/errno.h>
 #include <sys/pool.h>
 #include <sys/radixtree.h>
 #include <lib/libkern/libkern.h>
 #if defined(_STANDALONE)
 #include <lib/libsa/stand.h>
 #endif /* defined(_STANDALONE) */
 #else /* defined(_KERNEL) || defined(_STANDALONE) */
-__RCSID("$NetBSD: radixtree.c,v 1.17.2.4 2012/08/01 21:09:27 yamt Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.17.2.5 2014/03/25 16:21:08 yamt Exp $");
 #include <assert.h>
 #include <errno.h>
 #include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #if 1
 #define KASSERT assert
 #else
 #define KASSERT(a)	/* nothing */
 #endif
 #endif /* defined(_KERNEL) || defined(_STANDALONE) */
 #include <sys/radixtree.h>