 @@ -1,14 +1,14 @@
-/* $NetBSD: ptree.c,v 1.4 2009/01/18 12:06:14 lukem Exp $ */
+/* $NetBSD: ptree.c,v 1.5 2009/06/07 03:12:40 yamt Exp $ */
 /*-
  * Copyright (c) 2008 The NetBSD Foundation, Inc.
  * All rights reserved.
+ *
  * This code is derived from software contributed to The NetBSD Foundation
  * by Matt Thomas <matt@3am-software.com>.
+ *
  * 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.
 @@ -30,40 +30,40 @@
  */
 #define _PT_PRIVATE
 #if defined(PTCHECK) && !defined(PTDEBUG)
 #define PTDEBUG
 #endif
 #if defined(_KERNEL) || defined(_STANDALONE)
 #include <sys/param.h>
 #include <sys/types.h>
 #include <sys/systm.h>
 #include <lib/libkern/libkern.h>
-__KERNEL_RCSID(0, "$NetBSD: ptree.c,v 1.4 2009/01/18 12:06:14 lukem Exp $");
+__KERNEL_RCSID(0, "$NetBSD: ptree.c,v 1.5 2009/06/07 03:12:40 yamt Exp $");
 #else
 #include <stddef.h>
 #include <stdint.h>
 #include <limits.h>
 #include <stdbool.h>
 #include <string.h>
 #ifdef PTDEBUG
 #include <assert.h>
 #define	KASSERT(e)	assert(e)
 #else
 #define	KASSERT(e)	do { } while (/*CONSTCOND*/ 0)
 #endif
-__RCSID("$NetBSD: ptree.c,v 1.4 2009/01/18 12:06:14 lukem Exp $");
+__RCSID("$NetBSD: ptree.c,v 1.5 2009/06/07 03:12:40 yamt Exp $");
 #endif /* _KERNEL || _STANDALONE */
 #ifdef _LIBC
 #include "namespace.h"
 #endif
 #ifdef PTTEST
 #include "ptree.h"
 #else
 #include <sys/ptree.h>
 #endif
 /*
 @@ -72,45 +72,45 @@ __RCSID("$NetBSD: ptree.c,v 1.4 2009/01/
  * tree would have N leaves, N-1 branching nodes, and a root pointer.  Each
  * branching node would have left(0) and right(1) pointers that either point
  * to another branching node or a leaf node.  The root pointer would also
  * point to either the first branching node or a leaf node.  Leaf nodes
  * have no need for pointers.
+ *
  * However, allocation for these branching nodes is problematic since the
  * allocation could fail.  This would cause insertions to fail for reasons
  * beyond the users control.  So to prevent this, in this implementation
  * each node has two identities: its leaf identity and its branch identity.
  * Each is separate from the other.  Every branch is tagged as to whether
  * it points to a leaf or a branch.  This is not an attribute of the object
  * but of the pointer to the object.  The low bit of the pointer is used as
- * the tag to determine wether it points to a leaf or branch identity, with
+ * the tag to determine whether it points to a leaf or branch identity, with
  * branch identities having the low bit set.
+ *
  * A node's branch identity has one rule: when traversing the tree from the
  * root to the node's leaf identity, one of the branches traversed will be via
  * the node's branch identity.  Of course, that has an exception: since to
  * store N leaves, you need N-1 branches.  That one node whose branch identity
  * isn't used is stored as "oddman"-out in the root.
+ *
  * Branching nodes also has a bit offset and a bit length which determines
  * which branch slot is used.  The bit length can be zero resulting in a
  * one-way branch.  This is happens in two special cases: the root and
  * interior mask nodes.
+ *
  * To support longest match first lookups, when a mask node (one that only
  * match the first N bits) has children who first N bits match the mask nodes,
  * that mask node is converted from being a leaf node to being a one-way
  * branch-node.  The mask becomes fixed in position in the tree.  The mask
- * will alaways be the longest mask match for its descendants (unless they
+ * will always be the longest mask match for its descendants (unless they
  * traverse an even longer match).
  */
 #define	NODETOITEM(pt, ptn)	\
 	((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset))
 #define	NODETOKEY(pt, ptn)	\
 	((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset + pt->pt_key_offset))
 #define	ITEMTONODE(pt, ptn)	\
 	((pt_node_t *)((uintptr_t)(ptn) + (pt)->pt_node_offset))
 bool ptree_check(const pt_tree_t *);
 #if PTCHECK > 1
 #define	PTREE_CHECK(pt)		ptree_check(pt)