[src/netbsd-7]: src/lib/libc/db/hash Pull up following revision(s) (requested...

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

details:   https://anonhg.NetBSD.org/src/rev/0154d9f6072a
branches:  netbsd-7
changeset: 799543:0154d9f6072a
user:      snj <snj%NetBSD.org@localhost>
date:      Thu Aug 06 21:50:36 2015 +0000

description:
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.

diffstat:

 lib/libc/db/hash/hash.c |  57 +++++++++++++++++++++++++++++++++++++++---------
 1 files changed, 46 insertions(+), 11 deletions(-)

diffs (105 lines):

diff -r e15ef8e6c989 -r 0154d9f6072a lib/libc/db/hash/hash.c
--- a/lib/libc/db/hash/hash.c   Thu Aug 06 21:47:11 2015 +0000
+++ b/lib/libc/db/hash/hash.c   Thu Aug 06 21:50:36 2015 +0000
@@ -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 @@
        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 @@
                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 @@
                                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 @@
                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);
 }