开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
hash_dup.c
资源名称：mysql-3.23.35.tar.gz　[点击查看]
上传用户：tsgydb
上传日期：2007-04-14
资源大小：10674k
文件大小：21k
源码类别：

MySQL数据库

开发平台：

Visual C++

hash_dup.c：源码内容
  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996, 1997, 1998, 1999, 2000
  5.  * Sleepycat Software.  All rights reserved.
  6.  */
  7. /*
  8.  * Copyright (c) 1990, 1993, 1994
  9.  * The Regents of the University of California.  All rights reserved.
  10.  *
  11.  * This code is derived from software contributed to Berkeley by
  12.  * Margo Seltzer.
  13.  *
  14.  * Redistribution and use in source and binary forms, with or without
  15.  * modification, are permitted provided that the following conditions
  16.  * are met:
  17.  * 1. Redistributions of source code must retain the above copyright
  18.  *    notice, this list of conditions and the following disclaimer.
  19.  * 2. Redistributions in binary form must reproduce the above copyright
  20.  *    notice, this list of conditions and the following disclaimer in the
  21.  *    documentation and/or other materials provided with the distribution.
  22.  * 3. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38. #include "db_config.h"
  40. #ifndef lint
  41. static const char revid[] = "$Id: hash_dup.c,v 11.49 2000/12/21 21:54:35 margo Exp $";
  42. #endif /* not lint */
  44. /*
  45.  * PACKAGE:  hashing
  46.  *
  47.  * DESCRIPTION:
  48.  *      Manipulation of duplicates for the hash package.
  49.  *
  50.  * ROUTINES:
  51.  *
  52.  * External
  53.  *      __add_dup
  54.  * Internal
  55.  */
  57. #ifndef NO_SYSTEM_INCLUDES
  58. #include <sys/types.h>
  60. #include <string.h>
  61. #endif
  63. #include "db_int.h"
  64. #include "db_page.h"
  65. #include "hash.h"
  66. #include "btree.h"
  67. #include "txn.h"
  69. static int __ham_check_move __P((DBC *, u_int32_t));
  70. static int __ham_dcursor __P((DBC *, db_pgno_t, u_int32_t));
  72. /*
  73.  * Called from hash_access to add a duplicate key. nval is the new
  74.  * value that we want to add.  The flags correspond to the flag values
  75.  * to cursor_put indicating where to add the new element.
  76.  * There are 4 cases.
  77.  * Case 1: The existing duplicate set already resides on a separate page.
  78.  *    We return and let the common code handle this.
  79.  * Case 2: The element is small enough to just be added to the existing set.
  80.  * Case 3: The element is large enough to be a big item, so we're going to
  81.  *    have to push the set onto a new page.
  82.  * Case 4: The element is large enough to push the duplicate set onto a
  83.  *    separate page.
  84.  *
  85.  * PUBLIC: int __ham_add_dup __P((DBC *, DBT *, u_int32_t, db_pgno_t *));
  86.  */
  87. int
  88. __ham_add_dup(dbc, nval, flags, pgnop)
  89. DBC *dbc;
  90. DBT *nval;
  91. u_int32_t flags;
  92. db_pgno_t *pgnop;
  93. {
  94. DB *dbp;
  95. HASH_CURSOR *hcp;
  96. DBT pval, tmp_val;
  97. u_int32_t add_bytes, new_size;
  98. int cmp, ret;
  99. u_int8_t *hk;
  101. dbp = dbc->dbp;
  102. hcp = (HASH_CURSOR *)dbc->internal;
  104. DB_ASSERT(flags != DB_CURRENT);
  106. add_bytes = nval->size +
  107.     (F_ISSET(nval, DB_DBT_PARTIAL) ? nval->doff : 0);
  108. add_bytes = DUP_SIZE(add_bytes);
  110. if ((ret = __ham_check_move(dbc, add_bytes)) != 0)
  111. return (ret);
  113. /*
  114.  * Check if resulting duplicate set is going to need to go
  115.  * onto a separate duplicate page.  If so, convert the
  116.  * duplicate set and add the new one.  After conversion,
  117.  * hcp->dndx is the first free ndx or the index of the
  118.  * current pointer into the duplicate set.
  119.  */
  120. hk = H_PAIRDATA(hcp->page, hcp->indx);
  121. /* Add the len bytes to the current singleton. */
  122. if (HPAGE_PTYPE(hk) != H_DUPLICATE)
  123. add_bytes += DUP_SIZE(0);
  124. new_size =
  125.     LEN_HKEYDATA(hcp->page, dbp->pgsize, H_DATAINDEX(hcp->indx)) +
  126.     add_bytes;
  128. /*
  129.  * We convert to off-page duplicates if the item is a big item,
  130.  * the addition of the new item will make the set large, or
  131.  * if there isn't enough room on this page to add the next item.
  132.  */
  133. if (HPAGE_PTYPE(hk) != H_OFFDUP &&
  134.     (HPAGE_PTYPE(hk) == H_OFFPAGE || ISBIG(hcp, new_size) ||
  135.     add_bytes > P_FREESPACE(hcp->page))) {
  137. if ((ret = __ham_dup_convert(dbc)) != 0)
  138. return (ret);
  139. return (hcp->opd->c_am_put(hcp->opd,
  140.     NULL, nval, flags, NULL));
  141. }
  143. /* There are two separate cases here: on page and off page. */
  144. if (HPAGE_PTYPE(hk) != H_OFFDUP) {
  145. if (HPAGE_PTYPE(hk) != H_DUPLICATE) {
  146. pval.flags = 0;
  147. pval.data = HKEYDATA_DATA(hk);
  148. pval.size = LEN_HDATA(hcp->page, dbp->pgsize,
  149.     hcp->indx);
  150. if ((ret = __ham_make_dup(dbp->dbenv,
  151.     &pval, &tmp_val, &dbc->rdata.data,
  152.     &dbc->rdata.ulen)) != 0 || (ret =
  153.     __ham_replpair(dbc, &tmp_val, 1)) != 0)
  154. return (ret);
  155. hk = H_PAIRDATA(hcp->page, hcp->indx);
  156. HPAGE_PTYPE(hk) = H_DUPLICATE;
  158. /*
  159.  * Update the cursor position since we now are in
  160.  * duplicates.
  161.  */
  162. F_SET(hcp, H_ISDUP);
  163. hcp->dup_off = 0;
  164. hcp->dup_len = pval.size;
  165. hcp->dup_tlen = DUP_SIZE(hcp->dup_len);
  166. }
  168. /* Now make the new entry a duplicate. */
  169. if ((ret = __ham_make_dup(dbp->dbenv, nval,
  170.     &tmp_val, &dbc->rdata.data, &dbc->rdata.ulen)) != 0)
  171. return (ret);
  173. tmp_val.dlen = 0;
  174. switch (flags) { /* On page. */
  175. case DB_KEYFIRST:
  176. case DB_KEYLAST:
  177. case DB_NODUPDATA:
  178. if (dbp->dup_compare != NULL) {
  179. __ham_dsearch(dbc, nval, &tmp_val.doff, &cmp);
  181. /* dup dups are not supported w/ sorted dups */
  182. if (cmp == 0)
  183. return (__db_duperr(dbp, flags));
  184. } else {
  185. hcp->dup_tlen = LEN_HDATA(hcp->page,
  186.     dbp->pgsize, hcp->indx);
  187. hcp->dup_len = nval->size;
  188. F_SET(hcp, H_ISDUP);
  189. if (flags == DB_KEYFIRST)
  190. hcp->dup_off = tmp_val.doff = 0;
  191. else
  192. hcp->dup_off =
  193.     tmp_val.doff = hcp->dup_tlen;
  194. }
  195. break;
  196. case DB_BEFORE:
  197. tmp_val.doff = hcp->dup_off;
  198. break;
  199. case DB_AFTER:
  200. tmp_val.doff = hcp->dup_off + DUP_SIZE(hcp->dup_len);
  201. break;
  202. }
  203. /* Add the duplicate. */
  204. ret = __ham_replpair(dbc, &tmp_val, 0);
  205. if (ret == 0)
  206. ret = memp_fset(dbp->mpf, hcp->page, DB_MPOOL_DIRTY);
  208. if (ret != 0)
  209. return (ret);
  211. /* Now, update the cursor if necessary. */
  212. switch (flags) {
  213. case DB_AFTER:
  214. hcp->dup_off += DUP_SIZE(hcp->dup_len);
  215. hcp->dup_len = nval->size;
  216. hcp->dup_tlen += DUP_SIZE(nval->size);
  217. break;
  218. case DB_KEYFIRST:
  219. case DB_KEYLAST:
  220. case DB_BEFORE:
  221. hcp->dup_tlen += DUP_SIZE(nval->size);
  222. hcp->dup_len = nval->size;
  223. break;
  224. }
  225. ret = __ham_c_update(dbc, tmp_val.size, 1, 1);
  226. return (ret);
  227. }
  229. /*
  230.  * If we get here, then we're on duplicate pages; set pgnop and
  231.  * return so the common code can handle it.
  232.  */
  233. memcpy(pgnop,
  234.     HOFFDUP_PGNO(H_PAIRDATA(hcp->page, hcp->indx)), sizeof(db_pgno_t));
  236. return (ret);
  237. }
  239. /*
  240.  * Convert an on-page set of duplicates to an offpage set of duplicates.
  241.  *
  242.  * PUBLIC: int __ham_dup_convert __P((DBC *));
  243.  */
  244. int
  245. __ham_dup_convert(dbc)
  246. DBC *dbc;
  247. {
  248. DB *dbp;
  249. DBC **hcs;
  250. DB_LSN lsn;
  251. PAGE *dp;
  252. HASH_CURSOR *hcp;
  253. BOVERFLOW bo;
  254. DBT dbt;
  255. HOFFPAGE ho;
  256. db_indx_t i, len, off;
  257. int c, ret, t_ret;
  258. u_int8_t *p, *pend;
  260. dbp = dbc->dbp;
  261. hcp = (HASH_CURSOR *)dbc->internal;
  263. /*
  264.  * Create a new page for the duplicates.
  265.  */
  266. if ((ret = __db_new(dbc,
  267.     dbp->dup_compare == NULL ? P_LRECNO : P_LDUP, &dp)) != 0)
  268. return (ret);
  269. P_INIT(dp, dbp->pgsize,
  270.     dp->pgno, PGNO_INVALID, PGNO_INVALID, LEAFLEVEL, TYPE(dp));
  272. /*
  273.  * Get the list of cursors that may need to be updated.
  274.  */
  275. if ((ret = __ham_get_clist(dbp,
  276.     PGNO(hcp->page), (u_int32_t)hcp->indx, &hcs)) != 0)
  277. return (ret);
  279. /*
  280.  * Now put the duplicates onto the new page.
  281.  */
  282. dbt.flags = 0;
  283. switch (HPAGE_PTYPE(H_PAIRDATA(hcp->page, hcp->indx))) {
  284. case H_KEYDATA:
  285. /* Simple case, one key on page; move it to dup page. */
  286. dbt.size = LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx);
  287. dbt.data = HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx));
  288. ret = __db_pitem(dbc,
  289.     dp, 0, BKEYDATA_SIZE(dbt.size), NULL, &dbt);
  290. goto finish;
  291. case H_OFFPAGE:
  292. /* Simple case, one key on page; move it to dup page. */
  293. memcpy(&ho,
  294.     P_ENTRY(hcp->page, H_DATAINDEX(hcp->indx)), HOFFPAGE_SIZE);
  295. UMRW_SET(bo.unused1);
  296. B_TSET(bo.type, ho.type, 0);
  297. UMRW_SET(bo.unused2);
  298. bo.pgno = ho.pgno;
  299. bo.tlen = ho.tlen;
  300. dbt.size = BOVERFLOW_SIZE;
  301. dbt.data = &bo;
  303. ret = __db_pitem(dbc, dp, 0, dbt.size, &dbt, NULL);
  305. finish: if (ret == 0) {
  306. memp_fset(dbp->mpf, dp, DB_MPOOL_DIRTY);
  307. /*
  308.  * Update any other cursors
  309.  */
  310. if (hcs != NULL && DB_LOGGING(dbc)
  311.      && IS_SUBTRANSACTION(dbc->txn)) {
  312. if ((ret = __ham_chgpg_log(dbp->dbenv,
  313.     dbc->txn, &lsn, 0, dbp->log_fileid,
  314.     DB_HAM_DUP, PGNO(hcp->page),
  315.     PGNO(dp), hcp->indx, 0)) != 0)
  316. break;
  317. }
  318. for (c = 0; hcs != NULL && hcs[c] != NULL; c++)
  319. if ((ret = __ham_dcursor(hcs[c],
  320.     PGNO(dp), 0)) != 0)
  321. break;
  323. }
  324. break;
  326. case H_DUPLICATE:
  327. p = HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx));
  328. pend = p +
  329.     LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx);
  331. /*
  332.  * We need to maintain the duplicate cursor position.
  333.  * Keep track of where we are in the duplicate set via
  334.  * the offset, and when it matches the one in the cursor,
  335.  * set the off-page duplicate cursor index to the current
  336.  * index.
  337.  */
  338. for (off = 0, i = 0; p < pend; i++) {
  339. memcpy(&len, p, sizeof(db_indx_t));
  340. dbt.size = len;
  341. p += sizeof(db_indx_t);
  342. dbt.data = p;
  343. p += len + sizeof(db_indx_t);
  344. if ((ret = __db_pitem(dbc, dp,
  345.     i, BKEYDATA_SIZE(dbt.size), NULL, &dbt)) != 0)
  346. break;
  347. /*
  348.  * Update any other cursors
  349.  */
  350. for (c = 0; hcs != NULL && hcs[c] != NULL; c++)
  351. if (((HASH_CURSOR *)(hcs[c]->internal))->dup_off
  352.     == off && (ret = __ham_dcursor(hcs[c],
  353.     PGNO(dp), i)) != 0)
  354. goto out;
  355. off += len + 2 * sizeof(db_indx_t);
  356. }
  357. out: break;
  359. default:
  360. ret = __db_pgfmt(dbp, (u_long)hcp->pgno);
  361. break;
  362. }
  363. if (ret == 0) {
  364. /*
  365.  * Now attach this to the source page in place of
  366.  * the old duplicate item.
  367.  */
  368. __ham_move_offpage(dbc, hcp->page,
  369.     (u_int32_t)H_DATAINDEX(hcp->indx), PGNO(dp));
  371. ret = memp_fset(dbp->mpf, hcp->page, DB_MPOOL_DIRTY);
  372. if ((t_ret = memp_fput(dbp->mpf, dp, DB_MPOOL_DIRTY)) != 0)
  373. ret = t_ret;
  374. hcp->dup_tlen = hcp->dup_off = hcp->dup_len = 0;
  375. } else
  376. (void)__db_free(dbc, dp);
  378. if (hcs != NULL)
  379. __os_free(hcs, 0);
  381. return (ret);
  382. }
  384. /*
  385.  * __ham_make_dup
  386.  *
  387.  * Take a regular dbt and make it into a duplicate item with all the partial
  388.  * information set appropriately. If the incoming dbt is a partial, assume
  389.  * we are creating a new entry and make sure that we do any initial padding.
  390.  *
  391.  * PUBLIC: int __ham_make_dup __P((DB_ENV *,
  392.  * PUBLIC:     const DBT *, DBT *d, void **, u_int32_t *));
  393.  */
  394. int
  395. __ham_make_dup(dbenv, notdup, duplicate, bufp, sizep)
  396. DB_ENV *dbenv;
  397. const DBT *notdup;
  398. DBT *duplicate;
  399. void **bufp;
  400. u_int32_t *sizep;
  401. {
  402. db_indx_t tsize, item_size;
  403. int ret;
  404. u_int8_t *p;
  406. item_size = (db_indx_t)notdup->size;
  407. if (F_ISSET(notdup, DB_DBT_PARTIAL))
  408. item_size += notdup->doff;
  410. tsize = DUP_SIZE(item_size);
  411. if ((ret = __ham_init_dbt(dbenv, duplicate, tsize, bufp, sizep)) != 0)
  412. return (ret);
  414. duplicate->dlen = 0;
  415. duplicate->flags = notdup->flags;
  416. F_SET(duplicate, DB_DBT_PARTIAL);
  418. p = duplicate->data;
  419. memcpy(p, &item_size, sizeof(db_indx_t));
  420. p += sizeof(db_indx_t);
  421. if (F_ISSET(notdup, DB_DBT_PARTIAL)) {
  422. memset(p, 0, notdup->doff);
  423. p += notdup->doff;
  424. }
  425. memcpy(p, notdup->data, notdup->size);
  426. p += notdup->size;
  427. memcpy(p, &item_size, sizeof(db_indx_t));
  429. duplicate->doff = 0;
  430. duplicate->dlen = notdup->size;
  432. return (0);
  433. }
  435. /*
  436.  * __ham_check_move --
  437.  *
  438.  * Check if we can do whatever we need to on this page.  If not,
  439.  * then we'll have to move the current element to a new page.
  440.  */
  441. static int
  442. __ham_check_move(dbc, add_len)
  443. DBC *dbc;
  444. u_int32_t add_len;
  445. {
  446. DB *dbp;
  447. HASH_CURSOR *hcp;
  448. DBT k, d;
  449. DB_LSN new_lsn;
  450. PAGE *next_pagep;
  451. db_pgno_t next_pgno;
  452. u_int32_t new_datalen, old_len, rectype;
  453. u_int8_t *hk;
  454. int ret;
  456. dbp = dbc->dbp;
  457. hcp = (HASH_CURSOR *)dbc->internal;
  459. hk = H_PAIRDATA(hcp->page, hcp->indx);
  461. /*
  462.  * If the item is already off page duplicates or an offpage item,
  463.  * then we know we can do whatever we need to do in-place
  464.  */
  465. if (HPAGE_PTYPE(hk) == H_OFFDUP || HPAGE_PTYPE(hk) == H_OFFPAGE)
  466. return (0);
  468. old_len = LEN_HITEM(hcp->page, dbp->pgsize, H_DATAINDEX(hcp->indx));
  469. new_datalen = old_len - HKEYDATA_SIZE(0) + add_len;
  470. if (HPAGE_PTYPE(hk) != H_DUPLICATE)
  471. new_datalen += DUP_SIZE(0);
  473. /*
  474.  * We need to add a new page under two conditions:
  475.  * 1. The addition makes the total data length cross the BIG
  476.  *    threshold and the OFFDUP structure won't fit on this page.
  477.  * 2. The addition does not make the total data cross the
  478.  *    threshold, but the new data won't fit on the page.
  479.  * If neither of these is true, then we can return.
  480.  */
  481. if (ISBIG(hcp, new_datalen) && (old_len > HOFFDUP_SIZE ||
  482.     HOFFDUP_SIZE - old_len <= P_FREESPACE(hcp->page)))
  483. return (0);
  485. if (!ISBIG(hcp, new_datalen) && add_len <= P_FREESPACE(hcp->page))
  486. return (0);
  488. /*
  489.  * If we get here, then we need to move the item to a new page.
  490.  * Check if there are more pages in the chain.  We now need to
  491.  * update new_datalen to include the size of both the key and
  492.  * the data that we need to move.
  493.  */
  495. new_datalen = ISBIG(hcp, new_datalen) ?
  496.     HOFFDUP_SIZE : HKEYDATA_SIZE(new_datalen);
  497. new_datalen += LEN_HITEM(hcp->page, dbp->pgsize, H_KEYINDEX(hcp->indx));
  499. next_pagep = NULL;
  500. for (next_pgno = NEXT_PGNO(hcp->page); next_pgno != PGNO_INVALID;
  501.     next_pgno = NEXT_PGNO(next_pagep)) {
  502. if (next_pagep != NULL &&
  503.     (ret = memp_fput(dbp->mpf, next_pagep, 0)) != 0)
  504. return (ret);
  506. if ((ret = memp_fget(dbp->mpf,
  507.     &next_pgno, DB_MPOOL_CREATE, &next_pagep)) != 0)
  508. return (ret);
  510. if (P_FREESPACE(next_pagep) >= new_datalen)
  511. break;
  512. }
  514. /* No more pages, add one. */
  515. if (next_pagep == NULL && (ret = __ham_add_ovflpage(dbc,
  516.     hcp->page, 0, &next_pagep)) != 0)
  517. return (ret);
  519. /* Add new page at the end of the chain. */
  520. if (P_FREESPACE(next_pagep) < new_datalen && (ret =
  521.     __ham_add_ovflpage(dbc, next_pagep, 1, &next_pagep)) != 0) {
  522. (void)memp_fput(dbp->mpf, next_pagep, 0);
  523. return (ret);
  524. }
  526. /* Copy the item to the new page. */
  527. if (DB_LOGGING(dbc)) {
  528. rectype = PUTPAIR;
  529. k.flags = 0;
  530. d.flags = 0;
  531. if (HPAGE_PTYPE(
  532.     H_PAIRKEY(hcp->page, hcp->indx)) == H_OFFPAGE) {
  533. rectype |= PAIR_KEYMASK;
  534. k.data = H_PAIRKEY(hcp->page, hcp->indx);
  535. k.size = HOFFPAGE_SIZE;
  536. } else {
  537. k.data =
  538.     HKEYDATA_DATA(H_PAIRKEY(hcp->page, hcp->indx));
  539. k.size = LEN_HKEY(hcp->page, dbp->pgsize, hcp->indx);
  540. }
  542. if (HPAGE_PTYPE(hk) == H_OFFPAGE) {
  543. rectype |= PAIR_DATAMASK;
  544. d.data = H_PAIRDATA(hcp->page, hcp->indx);
  545. d.size = HOFFPAGE_SIZE;
  546. } else {
  547. if (HPAGE_PTYPE(H_PAIRDATA(hcp->page, hcp->indx))
  548.     == H_DUPLICATE)
  549. rectype |= PAIR_DUPMASK;
  550. d.data =
  551.     HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx));
  552. d.size = LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx);
  553. }
  555. if ((ret = __ham_insdel_log(dbp->dbenv,
  556.     dbc->txn, &new_lsn, 0, rectype,
  557.     dbp->log_fileid, PGNO(next_pagep),
  558.     (u_int32_t)NUM_ENT(next_pagep), &LSN(next_pagep),
  559.     &k, &d)) != 0) {
  560. (void)memp_fput(dbp->mpf, next_pagep, 0);
  561. return (ret);
  562. }
  564. /* Move lsn onto page. */
  565. LSN(next_pagep) = new_lsn; /* Structure assignment. */
  566. }
  568. __ham_copy_item(dbp->pgsize,
  569.     hcp->page, H_KEYINDEX(hcp->indx), next_pagep);
  570. __ham_copy_item(dbp->pgsize,
  571.     hcp->page, H_DATAINDEX(hcp->indx), next_pagep);
  573. /*
  574.  * We've just manually inserted a key and set of data onto
  575.  * next_pagep;  however, it's possible that our caller will
  576.  * return without further modifying the new page, for instance
  577.  * if DB_NODUPDATA is set and our new item is a duplicate duplicate.
  578.  * Thus, to be on the safe side, we need to mark the page dirty
  579.  * here. [#2996]
  580.  *
  581.  * Note that __ham_del_pair should dirty the page we're moving
  582.  * the items from, so we need only dirty the new page ourselves.
  583.  */
  584. if ((ret = memp_fset(dbp->mpf, next_pagep, DB_MPOOL_DIRTY)) != 0)
  585. goto out;
  587. /* Update all cursors that used to point to this item. */
  588. if ((ret = __ham_c_chgpg(dbc, PGNO(hcp->page), H_KEYINDEX(hcp->indx),
  589.     PGNO(next_pagep), NUM_ENT(next_pagep) - 2)) != 0)
  590. goto out;
  592. /* Now delete the pair from the current page. */
  593. ret = __ham_del_pair(dbc, 0);
  595. /*
  596.  * __ham_del_pair decremented nelem.  This is incorrect;  we
  597.  * manually copied the element elsewhere, so the total number
  598.  * of elements hasn't changed.  Increment it again.
  599.  */
  600. if (!STD_LOCKING(dbc))
  601. hcp->hdr->nelem++;
  603. out:
  604. (void)memp_fput(dbp->mpf, hcp->page, DB_MPOOL_DIRTY);
  605. hcp->page = next_pagep;
  606. hcp->pgno = PGNO(hcp->page);
  607. hcp->indx = NUM_ENT(hcp->page) - 2;
  608. F_SET(hcp, H_EXPAND);
  609. F_CLR(hcp, H_DELETED);
  611. return (ret);
  612. }
  614. /*
  615.  * __ham_move_offpage --
  616.  * Replace an onpage set of duplicates with the OFFDUP structure
  617.  * that references the duplicate page.
  618.  *
  619.  * XXX
  620.  * This is really just a special case of __onpage_replace; we should
  621.  * probably combine them.
  622.  *
  623.  * PUBLIC: void __ham_move_offpage __P((DBC *, PAGE *, u_int32_t, db_pgno_t));
  624.  */
  625. void
  626. __ham_move_offpage(dbc, pagep, ndx, pgno)
  627. DBC *dbc;
  628. PAGE *pagep;
  629. u_int32_t ndx;
  630. db_pgno_t pgno;
  631. {
  632. DB *dbp;
  633. HASH_CURSOR *hcp;
  634. DBT new_dbt;
  635. DBT old_dbt;
  636. HOFFDUP od;
  637. db_indx_t i;
  638. int32_t shrink;
  639. u_int8_t *src;
  641. dbp = dbc->dbp;
  642. hcp = (HASH_CURSOR *)dbc->internal;
  643. od.type = H_OFFDUP;
  644. UMRW_SET(od.unused[0]);
  645. UMRW_SET(od.unused[1]);
  646. UMRW_SET(od.unused[2]);
  647. od.pgno = pgno;
  649. if (DB_LOGGING(dbc)) {
  650. new_dbt.data = &od;
  651. new_dbt.size = HOFFDUP_SIZE;
  652. old_dbt.data = P_ENTRY(pagep, ndx);
  653. old_dbt.size = LEN_HITEM(pagep, dbp->pgsize, ndx);
  654. (void)__ham_replace_log(dbp->dbenv,
  655.     dbc->txn, &LSN(pagep), 0, dbp->log_fileid,
  656.     PGNO(pagep), (u_int32_t)ndx, &LSN(pagep), -1,
  657.     &old_dbt, &new_dbt, 0);
  658. }
  660. shrink = LEN_HITEM(pagep, dbp->pgsize, ndx) - HOFFDUP_SIZE;
  662. if (shrink != 0) {
  663. /* Copy data. */
  664. src = (u_int8_t *)(pagep) + HOFFSET(pagep);
  665. memmove(src + shrink, src, pagep->inp[ndx] - HOFFSET(pagep));
  666. HOFFSET(pagep) += shrink;
  668. /* Update index table. */
  669. for (i = ndx; i < NUM_ENT(pagep); i++)
  670. pagep->inp[i] += shrink;
  671. }
  673. /* Now copy the offdup entry onto the page. */
  674. memcpy(P_ENTRY(pagep, ndx), &od, HOFFDUP_SIZE);
  675. }
  677. /*
  678.  * __ham_dsearch:
  679.  * Locate a particular duplicate in a duplicate set.  Make sure that
  680.  * we exit with the cursor set appropriately.
  681.  *
  682.  * PUBLIC: void __ham_dsearch __P((DBC *, DBT *, u_int32_t *, int *));
  683.  */
  684. void
  685. __ham_dsearch(dbc, dbt, offp, cmpp)
  686. DBC *dbc;
  687. DBT *dbt;
  688. u_int32_t *offp;
  689. int *cmpp;
  690. {
  691. DB *dbp;
  692. HASH_CURSOR *hcp;
  693. DBT cur;
  694. db_indx_t i, len;
  695. int (*func) __P((DB *, const DBT *, const DBT *));
  696. u_int8_t *data;
  698. dbp = dbc->dbp;
  699. hcp = (HASH_CURSOR *)dbc->internal;
  700. if (dbp->dup_compare == NULL)
  701. func = __bam_defcmp;
  702. else
  703. func = dbp->dup_compare;
  705. i = F_ISSET(hcp, H_CONTINUE) ? hcp->dup_off: 0;
  706. data = HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx)) + i;
  707. hcp->dup_tlen = LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx);
  708. while (i < hcp->dup_tlen) {
  709. memcpy(&len, data, sizeof(db_indx_t));
  710. data += sizeof(db_indx_t);
  711. cur.data = data;
  712. cur.size = (u_int32_t)len;
  713. *cmpp = func(dbp, dbt, &cur);
  714. if (*cmpp == 0 || (*cmpp < 0 && dbp->dup_compare != NULL))
  715. break;
  716. i += len + 2 * sizeof(db_indx_t);
  717. data += len + sizeof(db_indx_t);
  718. }
  719. *offp = i;
  720. hcp->dup_off = i;
  721. hcp->dup_len = len;
  722. F_SET(hcp, H_ISDUP);
  723. }
  725. #ifdef DEBUG
  726. /*
  727.  * __ham_cprint --
  728.  * Display the current cursor list.
  729.  *
  730.  * PUBLIC: int __ham_cprint __P((DB *));
  731.  */
  732. int
  733. __ham_cprint(dbp)
  734. DB *dbp;
  735. {
  736. HASH_CURSOR *cp;
  737. DBC *dbc;
  739. MUTEX_THREAD_LOCK(dbp->dbenv, dbp->mutexp);
  740. for (dbc = TAILQ_FIRST(&dbp->active_queue);
  741.     dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
  742. cp = (HASH_CURSOR *)dbc->internal;
  743. fprintf(stderr, "%#0lx->%#0lx: page: %lu index: %lu",
  744.     P_TO_ULONG(dbc), P_TO_ULONG(cp), (u_long)cp->pgno,
  745.     (u_long)cp->indx);
  746. if (F_ISSET(cp, H_DELETED))
  747. fprintf(stderr, " (deleted)");
  748. fprintf(stderr, "n");
  749. }
  750. MUTEX_THREAD_UNLOCK(dbp->dbenv, dbp->mutexp);
  752. return (0);
  753. }
  754. #endif /* DEBUG */
  756. /*
  757.  * __ham_dcursor --
  758.  *
  759.  * Create an off page duplicate cursor for this cursor.
  760.  */
  761. static int
  762. __ham_dcursor(dbc, pgno, indx)
  763. DBC *dbc;
  764. db_pgno_t pgno;
  765. u_int32_t indx;
  766. {
  767. DB *dbp;
  768. DBC *dbc_nopd;
  769. HASH_CURSOR *hcp;
  770. BTREE_CURSOR *dcp;
  771. int ret;
  773. dbp = dbc->dbp;
  775. if ((ret = __db_c_newopd(dbc, pgno, &dbc_nopd)) != 0)
  776. return (ret);
  778. dcp = (BTREE_CURSOR *)dbc_nopd->internal;
  779. dcp->pgno = pgno;
  780. dcp->indx = indx;
  782. if (dbp->dup_compare == NULL) {
  783. /*
  784.  * Converting to off-page Recno trees is tricky.  The
  785.  * record number for the cursor is the index + 1 (to
  786.  * convert to 1-based record numbers).
  787.  */
  788. dcp->recno = indx + 1;
  789. }
  791. /*
  792.  * Transfer the deleted flag from the top-level cursor to the
  793.  * created one.
  794.  */
  795. hcp = (HASH_CURSOR *)dbc->internal;
  796. if (F_ISSET(hcp, H_DELETED)) {
  797. F_SET(dcp, C_DELETED);
  798. F_CLR(hcp, H_DELETED);
  799. }
  801. /* Stack the cursors and reset the initial cursor's index. */
  802. hcp->opd = dbc_nopd;
  804. return (0);
  805. }