Module Name: src
Committed By: christos
Date: Mon Jun 22 21:16:02 UTC 2015
Modified Files:
src/lib/libc/db/hash: hash.c
Log Message:
Fix hash iteration that deletes the current element under the cursor by
adjusting the position of the iterator appropriately.
XXX: pullup 7
To generate a diff of this commit:
cvs rdiff -u -r1.34 -r1.35 src/lib/libc/db/hash/hash.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/lib/libc/db/hash/hash.c
diff -u src/lib/libc/db/hash/hash.c:1.34 src/lib/libc/db/hash/hash.c:1.35
--- src/lib/libc/db/hash/hash.c:1.34 Mon Jun 22 14:50:06 2015
+++ src/lib/libc/db/hash/hash.c Mon Jun 22 17:16:02 2015
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.34 2015/06/22 18:50:06 christos Exp $ */
+/* $NetBSD: hash.c,v 1.35 2015/06/22 21:16:02 christos Exp $ */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -37,7 +37,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: hash.c,v 1.34 2015/06/22 18:50:06 christos Exp $");
+__RCSID("$NetBSD: hash.c,v 1.35 2015/06/22 21:16:02 christos Exp $");
#include "namespace.h"
#include <sys/param.h>
@@ -690,6 +690,27 @@ found:
case HASH_DELETE:
if (__delpair(hashp, rbufp, ndx))
return (ERROR);
+ /*
+ * Our index lags 2 behind on the same page when we are
+ * deleting the element pointed to by the index; otherwise
+ * deleting randomly from an iterated hash produces undefined
+ * results.
+ */
+ if (ndx != hashp->cndx - 2 || rbufp != hashp->cpage)
+ break;
+
+ if (hashp->cndx > 1) {
+ /* Move back one element */
+ hashp->cndx -= 2;
+ } else {
+ /*
+ * Move back one page, and indicate to go to the last
+ * element of the previous page by setting cndx to -1
+ */
+ hashp->cbucket--;
+ hashp->cpage = NULL;
+ hashp->cndx = -1;
+ }
break;
default:
abort();
@@ -725,7 +746,7 @@ next_bucket:
if (!(bufp = hashp->cpage)) {
for (bucket = hashp->cbucket;
bucket <= (uint32_t)hashp->MAX_BUCKET;
- bucket++, hashp->cndx = 1) {
+ bucket++) {
bufp = __get_buf(hashp, bucket, NULL, 0);
if (!bufp)
return (ERROR);
@@ -739,10 +760,18 @@ next_bucket:
hashp->cbucket = -1;
return (ABNORMAL);
}
+ if (hashp->cndx == -1) {
+ /* move to the last element of the page */
+ hashp->cndx = 1;
+ while (bp[hashp->cndx - 1] != 0)
+ hashp->cndx += 2;
+ } else {
+ /* start on the first element */
+ hashp->cndx = 1;
+ }
} else {
bp = (uint16_t *)(void *)hashp->cpage->page;
if (flag == R_NEXT || flag == 0) {
- hashp->cndx += 2;
if (hashp->cndx > bp[0]) {
hashp->cpage = NULL;
hashp->cbucket++;
@@ -781,6 +810,7 @@ next_bucket:
data->data = (uint8_t *)hashp->cpage->page + bp[ndx + 1];
data->size = bp[ndx] - bp[ndx + 1];
}
+ hashp->cndx += 2;
return (SUCCESS);
}
