Fri May 22 11:38:05 2009 UTC ()
rpst_insert_node1: fix an inverted condition.


(yamt)
diff -r1.2 -r1.3 src/common/lib/libc/gen/rpst.c
cvs diff -r1.2 -r1.3 src/common/lib/libc/gen/rpst.c (expand / switch to unified diff)

--- src/common/lib/libc/gen/rpst.c 2009/05/20 10:56:29 1.2
+++ src/common/lib/libc/gen/rpst.c 2009/05/22 11:38:05 1.3
@@ -1,14 +1,14 @@ @@ -1,14 +1,14 @@
1/* $NetBSD: rpst.c,v 1.2 2009/05/20 10:56:29 yamt Exp $ */ 1/* $NetBSD: rpst.c,v 1.3 2009/05/22 11:38:05 yamt Exp $ */
2 2
3/*- 3/*-
4 * Copyright (c)2009 YAMAMOTO Takashi, 4 * Copyright (c)2009 YAMAMOTO Takashi,
5 * All rights reserved. 5 * All rights reserved.
6 * 6 *
7 * Redistribution and use in source and binary forms, with or without 7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions 8 * modification, are permitted provided that the following conditions
9 * are met: 9 * are met:
10 * 1. Redistributions of source code must retain the above copyright 10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer. 11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright 12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the 13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution. 14 * documentation and/or other materials provided with the distribution.
@@ -33,30 +33,30 @@ @@ -33,30 +33,30 @@
33 * SIAM J. COMPUT. 33 * SIAM J. COMPUT.
34 * Vol. 14, No. 2, May 1985 34 * Vol. 14, No. 2, May 1985
35 * PRIORITY SEARCH TREES 35 * PRIORITY SEARCH TREES
36 * EDWARD M. McCREIGHT 36 * EDWARD M. McCREIGHT
37 * 37 *
38 * ideas from linux: 38 * ideas from linux:
39 * - grow tree height on-demand. 39 * - grow tree height on-demand.
40 * - allow duplicated X values. in that case, we act as a heap. 40 * - allow duplicated X values. in that case, we act as a heap.
41 */ 41 */
42 42
43#include <sys/cdefs.h> 43#include <sys/cdefs.h>
44 44
45#if defined(_KERNEL) 45#if defined(_KERNEL)
46__KERNEL_RCSID(0, "$NetBSD: rpst.c,v 1.2 2009/05/20 10:56:29 yamt Exp $"); 46__KERNEL_RCSID(0, "$NetBSD: rpst.c,v 1.3 2009/05/22 11:38:05 yamt Exp $");
47#include <sys/param.h> 47#include <sys/param.h>
48#else /* defined(_KERNEL) */ 48#else /* defined(_KERNEL) */
49__RCSID("$NetBSD: rpst.c,v 1.2 2009/05/20 10:56:29 yamt Exp $"); 49__RCSID("$NetBSD: rpst.c,v 1.3 2009/05/22 11:38:05 yamt Exp $");
50#include <assert.h> 50#include <assert.h>
51#include <stdbool.h> 51#include <stdbool.h>
52#include <string.h> 52#include <string.h>
53#if 1 53#if 1
54#define KASSERT assert 54#define KASSERT assert
55#else 55#else
56#define KASSERT(a) 56#define KASSERT(a)
57#endif 57#endif
58#endif /* defined(_KERNEL) */ 58#endif /* defined(_KERNEL) */
59 59
60#include <sys/rpst.h> 60#include <sys/rpst.h>
61 61
62/* 62/*
@@ -158,27 +158,27 @@ static struct rpst_node * @@ -158,27 +158,27 @@ static struct rpst_node *
158rpst_insert_node1(struct rpst_node **where, struct rpst_node *n, uint64_t mask) 158rpst_insert_node1(struct rpst_node **where, struct rpst_node *n, uint64_t mask)
159{ 159{
160 struct rpst_node *cur; 160 struct rpst_node *cur;
161 unsigned int idx; 161 unsigned int idx;
162 162
163 KASSERT((n->n_x & ((-mask) << 1)) == 0); 163 KASSERT((n->n_x & ((-mask) << 1)) == 0);
164next: 164next:
165 cur = *where; 165 cur = *where;
166 if (cur == NULL) { 166 if (cur == NULL) {
167 memset(&n->n_children, 0, sizeof(n->n_children)); 167 memset(&n->n_children, 0, sizeof(n->n_children));
168 *where = n; 168 *where = n;
169 return NULL; 169 return NULL;
170 } 170 }
171 if (n->n_y == cur->n_y && n->n_x != cur->n_x) { 171 if (n->n_y == cur->n_y && n->n_x == cur->n_x) {
172 return cur; 172 return cur;
173 } 173 }
174 if (n->n_y < cur->n_y) { 174 if (n->n_y < cur->n_y) {
175 /* swap cur and n */ 175 /* swap cur and n */
176 memcpy(n->n_children, cur->n_children, sizeof(n->n_children)); 176 memcpy(n->n_children, cur->n_children, sizeof(n->n_children));
177 *where = n; 177 *where = n;
178 n = cur; 178 n = cur;
179 cur = *where; 179 cur = *where;
180 } 180 }
181 KASSERT(*where == cur); 181 KASSERT(*where == cur);
182 idx = (n->n_x & mask) != 0; 182 idx = (n->n_x & mask) != 0;
183 where = &cur->n_children[idx]; 183 where = &cur->n_children[idx];
184 KASSERT((*where) == NULL || ((((*where)->n_x & mask) != 0) == idx)); 184 KASSERT((*where) == NULL || ((((*where)->n_x & mask) != 0) == idx));