[src/trunk]: src/lib/libc/db/hash Fix hash iteration that deletes the current...

[christos <christos%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/2af452477a8b
branches:  trunk
changeset: 339027:2af452477a8b
user:      christos <christos%NetBSD.org@localhost>
date:      Mon Jun 22 21:16:02 2015 +0000

description:
Fix hash iteration that deletes the current element under the cursor by
adjusting the position of the iterator appropriately.
XXX: pullup 7

diffstat:

 lib/libc/db/hash/hash.c |  38 ++++++++++++++++++++++++++++++++++----
 1 files changed, 34 insertions(+), 4 deletions(-)

diffs (83 lines):

diff -r 63ee145d26bc -r 2af452477a8b lib/libc/db/hash/hash.c
--- a/lib/libc/db/hash/hash.c   Mon Jun 22 19:11:00 2015 +0000
+++ b/lib/libc/db/hash/hash.c   Mon Jun 22 21:16:02 2015 +0000
@@ -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 @@
        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 @@
                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 @@
                                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 @@
                data->data = (uint8_t *)hashp->cpage->page + bp[ndx + 1];
                data->size = bp[ndx] - bp[ndx + 1];
        }
+       hashp->cndx += 2;
        return (SUCCESS);
 }