Module Name: src
Committed By: snj
Date: Thu Aug 6 21:50:36 UTC 2015
Modified Files:
src/lib/libc/db/hash [netbsd-7]: hash.c
Log Message:
Pull up following revision(s) (requested by christos in ticket #921):
lib/libc/db/hash/hash.c: revision 1.34
lib/libc/db/hash/hash.c: revision 1.35
Delay moving to the next key until the next iteration. This avoids returning
invalid data to the user if the user deletes the current key, but it also
fails to iterate over some keys as will be shown by a unit test. From FreeBSD.
--
Fix hash iteration that deletes the current element under the cursor by
adjusting the position of the iterator appropriately.
To generate a diff of this commit:
cvs rdiff -u -r1.33 -r1.33.4.1 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.33 src/lib/libc/db/hash/hash.c:1.33.4.1
--- src/lib/libc/db/hash/hash.c:1.33 Sun Dec 1 00:22:48 2013
+++ src/lib/libc/db/hash/hash.c Thu Aug 6 21:50:36 2015
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.33 2013/12/01 00:22:48 christos Exp $ */
+/* $NetBSD: hash.c,v 1.33.4.1 2015/08/06 21:50:36 snj Exp $ */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -37,7 +37,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: hash.c,v 1.33 2013/12/01 00:22:48 christos Exp $");
+__RCSID("$NetBSD: hash.c,v 1.33.4.1 2015/08/06 21:50:36 snj 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();
@@ -720,11 +741,12 @@ hash_seq(const DB *dbp, DBT *key, DBT *d
hashp->cpage = NULL;
}
+next_bucket:
for (bp = NULL; !bp || !bp[0]; ) {
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);
@@ -738,8 +760,27 @@ hash_seq(const DB *dbp, DBT *key, DBT *d
hashp->cbucket = -1;
return (ABNORMAL);
}
- } else
+ 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) {
+ if (hashp->cndx > bp[0]) {
+ hashp->cpage = NULL;
+ hashp->cbucket++;
+ hashp->cndx = 1;
+ goto next_bucket;
+ }
+ }
+ }
+
_DIAGASSERT(bp != NULL);
_DIAGASSERT(bufp != NULL);
@@ -768,14 +809,8 @@ hash_seq(const DB *dbp, DBT *key, DBT *d
key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
data->data = (uint8_t *)hashp->cpage->page + bp[ndx + 1];
data->size = bp[ndx] - bp[ndx + 1];
- ndx += 2;
- if (ndx > bp[0]) {
- hashp->cpage = NULL;
- hashp->cbucket++;
- hashp->cndx = 1;
- } else
- hashp->cndx = ndx;
}
+ hashp->cndx += 2;
return (SUCCESS);
}
