/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 1996, 1997, 1998
* Sleepycat Software. All rights reserved.
*/
/*
* Copyright (c) 1990, 1993, 1994
* The Regents of the University of California. All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Margo Seltzer.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include "config.h"
#ifndef lint
#endif /* not lint */
/*
* PACKAGE: hashing
*
* DESCRIPTION:
* Manipulation of duplicates for the hash package.
*
* ROUTINES:
*
* External
* __add_dup
* Internal
*/
#ifndef NO_SYSTEM_INCLUDES
#include <errno.h>
#include <string.h>
#endif
#include "db_int.h"
#include "db_page.h"
#include "hash.h"
#include "btree.h"
/*
* Called from hash_access to add a duplicate key. nval is the new
* value that we want to add. The flags correspond to the flag values
* to cursor_put indicating where to add the new element.
* There are 4 cases.
* Case 1: The existing duplicate set already resides on a separate page.
* We can use common code for this.
* Case 2: The element is small enough to just be added to the existing set.
* Case 3: The element is large enough to be a big item, so we're going to
* have to push the set onto a new page.
* Case 4: The element is large enough to push the duplicate set onto a
* separate page.
*
* PUBLIC: int __ham_add_dup __P((DBC *, DBT *, u_int32_t));
*/
int
{
else
del_len = 0;
return (ret);
/*
* Check if resulting duplicate set is going to need to go
* onto a separate duplicate page. If so, convert the
* duplicate set and add the new one. After conversion,
* hcp->dndx is the first free ndx or the index of the
* current pointer into the duplicate set.
*/
/*
* We convert to off-page duplicates if the item is a big item,
* the addition of the new item will make the set large, or
* if there isn't enough room on this page to add the next item.
*/
return (ret);
else
}
/* There are two separate cases here: on page and off page. */
if ((ret =
return (ret);
}
/* Now make the new entry a duplicate. */
return (ret);
switch (flags) { /* On page. */
case DB_KEYFIRST:
case DB_KEYLAST:
else if (flags == DB_KEYFIRST)
else
break;
case DB_CURRENT:
/*
* If we have a sort function, we need to verify that
* the new item sorts identically to the old item.
*/
return (EINVAL);
}
break;
case DB_BEFORE:
break;
case DB_AFTER:
break;
}
/* Add the duplicate. */
if (ret == 0)
return (ret);
}
/* If we get here, then we're on duplicate pages. */
}
switch (flags) {
case DB_KEYFIRST:
goto sorted_dups;
/*
* The only way that we are already on a dup page is
* if we just converted the on-page representation.
* In that case, we've only got one page of duplicates.
*/
return (ret);
break;
case DB_KEYLAST:
return (ret);
if (cmp == 0)
} else {
return (ret);
}
break;
case DB_CURRENT:
return (EINVAL);
case B_KEYDATA:
break;
case B_OVERFLOW:
break;
}
if ((ret =
return (ret);
break;
case DB_BEFORE: /* The default behavior is correct. */
break;
case DB_AFTER:
break;
}
return (ret);
}
/*
* Convert an on-page set of duplicates to an offpage set of duplicates.
*/
static int
{
int ret;
/*
* Create a new page for the duplicates.
*/
if ((ret =
return (ret);
/*
* Now put the duplicates onto the new page.
*/
dndx = 0;
case H_KEYDATA:
/* Simple case, one key on page; move it to dup page. */
if (ret == 0)
break;
case H_OFFPAGE:
/* Simple case, one key on page; move it to dup page. */
if (ret == 0)
break;
case H_DUPLICATE:
pend = p +
/*
* We need to maintain the duplicate cursor position.
* Keep track of where we are in the duplicate set via
* the offset, and when it matches the one in the cursor,
* set the off-page duplicate cursor index to the current
* index.
*/
dndx = i;
p += sizeof(db_indx_t);
if (ret != 0)
break;
}
break;
default:
break;
}
if (ret == 0) {
/*
* Now attach this to the source page in place of
* the old duplicate item.
*/
/* Can probably just do a "put" here. */
} else {
}
return (ret);
}
static int
void **bufp;
{
int ret;
u_int8_t *p;
return (ret);
p += sizeof(db_indx_t);
return (0);
}
static int
{
DBT k, d;
int ret;
/*
* Check if we can do whatever we need to on this page. If not,
* then we'll have to move the current element to a new page.
*/
/*
* If the item is already off page duplicates or an offpage item,
* then we know we can do whatever we need to do in-place
*/
return (0);
old_len =
/*
* We need to add a new page under two conditions:
* 1. The addition makes the total data length cross the BIG
* threshold and the OFFDUP structure won't fit on this page.
* 2. The addition does not make the total data cross the
* threshold, but the new data won't fit on the page.
* If neither of these is true, then we can return.
*/
return (0);
return (0);
/*
* If we get here, then we need to move the item to a new page.
* Check if there are more pages in the chain.
*/
next_pagep = NULL;
if (next_pagep != NULL &&
return (ret);
if ((ret =
return (ret);
break;
}
/* No more pages, add one. */
return (ret);
/* Add new page at the end of the chain. */
return (ret);
/* Copy the item to the new page. */
k.flags = 0;
d.flags = 0;
if (HPAGE_PTYPE(
rectype |= PAIR_KEYMASK;
k.size = HOFFPAGE_SIZE;
} else {
k.data =
}
rectype |= PAIR_DATAMASK;
d.size = HOFFPAGE_SIZE;
} else {
d.data =
}
&k, &d)) != 0)
return (ret);
/* Move lsn onto page. */
}
/* Now delete the pair from the current page. */
return (ret);
}
/*
* __ham_move_offpage --
* Replace an onpage set of duplicates with the OFFDUP structure
* that references the duplicate page.
*
* XXX
* This is really just a special case of __onpage_replace; we should
* probably combine them.
*
* PUBLIC: void __ham_move_offpage __P((DBC *, PAGE *, u_int32_t, db_pgno_t));
*/
void
{
db_indx_t i;
if (DB_LOGGING(dbc)) {
}
shrink =
if (shrink != 0) {
/* Copy data. */
/* Update index table. */
}
/* Now copy the offdup entry onto the page. */
}
/*
* __ham_dsearch:
* Locate a particular duplicate in a duplicate set.
*
* PUBLIC: void __ham_dsearch __P((DBC *, DBT *, u_int32_t *, int *));
*/
void
int *cmpp;
{
func = __bam_defcmp;
else
break;
}
*offp = i;
}