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

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
hash_dup.c
资源名称：mysql-4.1.16-win-src.zip　[点击查看]
上传用户：romrleung
上传日期：2022-05-23
资源大小：18897k
文件大小：24k
源码类别：

MySQL数据库

开发平台：

Visual C++

hash_dup.c：源码内容
  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996-2002
  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.76 2002/08/06 05:34:40 bostic Exp $";
  42. #endif /* not lint */
  44. /*
  45.  * PACKAGE:  hashing
  46.  *
  47.  * DESCRIPTION:
  48.  * Manipulation of duplicates for the hash package.
  49.  */
  51. #ifndef NO_SYSTEM_INCLUDES
  52. #include <sys/types.h>
  54. #include <string.h>
  55. #endif
  57. #include "db_int.h"
  58. #include "dbinc/db_page.h"
  59. #include "dbinc/hash.h"
  60. #include "dbinc/btree.h"
  62. static int __ham_c_chgpg __P((DBC *,
  63.     db_pgno_t, u_int32_t, db_pgno_t, u_int32_t));
  64. static int __ham_check_move __P((DBC *, u_int32_t));
  65. static int __ham_dcursor __P((DBC *, db_pgno_t, u_int32_t));
  66. static int __ham_move_offpage __P((DBC *, PAGE *, u_int32_t, db_pgno_t));
  68. /*
  69.  * Called from hash_access to add a duplicate key. nval is the new
  70.  * value that we want to add.  The flags correspond to the flag values
  71.  * to cursor_put indicating where to add the new element.
  72.  * There are 4 cases.
  73.  * Case 1: The existing duplicate set already resides on a separate page.
  74.  *    We return and let the common code handle this.
  75.  * Case 2: The element is small enough to just be added to the existing set.
  76.  * Case 3: The element is large enough to be a big item, so we're going to
  77.  *    have to push the set onto a new page.
  78.  * Case 4: The element is large enough to push the duplicate set onto a
  79.  *    separate page.
  80.  *
  81.  * PUBLIC: int __ham_add_dup __P((DBC *, DBT *, u_int32_t, db_pgno_t *));
  82.  */
  83. int
  84. __ham_add_dup(dbc, nval, flags, pgnop)
  85. DBC *dbc;
  86. DBT *nval;
  87. u_int32_t flags;
  88. db_pgno_t *pgnop;
  89. {
  90. DB *dbp;
  91. DBT pval, tmp_val;
  92. DB_MPOOLFILE *mpf;
  93. HASH_CURSOR *hcp;
  94. u_int32_t add_bytes, new_size;
  95. int cmp, ret;
  96. u_int8_t *hk;
  98. dbp = dbc->dbp;
  99. mpf = dbp->mpf;
  100. hcp = (HASH_CURSOR *)dbc->internal;
  102. DB_ASSERT(flags != DB_CURRENT);
  104. add_bytes = nval->size +
  105.     (F_ISSET(nval, DB_DBT_PARTIAL) ? nval->doff : 0);
  106. add_bytes = DUP_SIZE(add_bytes);
  108. if ((ret = __ham_check_move(dbc, add_bytes)) != 0)
  109. return (ret);
  111. /*
  112.  * Check if resulting duplicate set is going to need to go
  113.  * onto a separate duplicate page.  If so, convert the
  114.  * duplicate set and add the new one.  After conversion,
  115.  * hcp->dndx is the first free ndx or the index of the
  116.  * current pointer into the duplicate set.
  117.  */
  118. hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  119. /* Add the len bytes to the current singleton. */
  120. if (HPAGE_PTYPE(hk) != H_DUPLICATE)
  121. add_bytes += DUP_SIZE(0);
  122. new_size =
  123.     LEN_HKEYDATA(dbp, hcp->page, dbp->pgsize, H_DATAINDEX(hcp->indx)) +
  124.     add_bytes;
  126. /*
  127.  * We convert to off-page duplicates if the item is a big item,
  128.  * the addition of the new item will make the set large, or
  129.  * if there isn't enough room on this page to add the next item.
  130.  */
  131. if (HPAGE_PTYPE(hk) != H_OFFDUP &&
  132.     (HPAGE_PTYPE(hk) == H_OFFPAGE || ISBIG(hcp, new_size) ||
  133.     add_bytes > P_FREESPACE(dbp, hcp->page))) {
  135. if ((ret = __ham_dup_convert(dbc)) != 0)
  136. return (ret);
  137. return (hcp->opd->c_am_put(hcp->opd,
  138.     NULL, nval, flags, NULL));
  139. }
  141. /* There are two separate cases here: on page and off page. */
  142. if (HPAGE_PTYPE(hk) != H_OFFDUP) {
  143. if (HPAGE_PTYPE(hk) != H_DUPLICATE) {
  144. pval.flags = 0;
  145. pval.data = HKEYDATA_DATA(hk);
  146. pval.size = LEN_HDATA(dbp, hcp->page, dbp->pgsize,
  147.     hcp->indx);
  148. if ((ret = __ham_make_dup(dbp->dbenv,
  149.     &pval, &tmp_val, &dbc->my_rdata.data,
  150.     &dbc->my_rdata.ulen)) != 0 || (ret =
  151.     __ham_replpair(dbc, &tmp_val, 1)) != 0)
  152. return (ret);
  153. hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  154. HPAGE_PTYPE(hk) = H_DUPLICATE;
  156. /*
  157.  * Update the cursor position since we now are in
  158.  * duplicates.
  159.  */
  160. F_SET(hcp, H_ISDUP);
  161. hcp->dup_off = 0;
  162. hcp->dup_len = pval.size;
  163. hcp->dup_tlen = DUP_SIZE(hcp->dup_len);
  164. }
  166. /* Now make the new entry a duplicate. */
  167. if ((ret = __ham_make_dup(dbp->dbenv, nval,
  168.     &tmp_val, &dbc->my_rdata.data, &dbc->my_rdata.ulen)) != 0)
  169. return (ret);
  171. tmp_val.dlen = 0;
  172. switch (flags) { /* On page. */
  173. case DB_KEYFIRST:
  174. case DB_KEYLAST:
  175. case DB_NODUPDATA:
  176. if (dbp->dup_compare != NULL) {
  177. __ham_dsearch(dbc,
  178.     nval, &tmp_val.doff, &cmp, flags);
  180. /* dup dups are not supported w/ sorted dups */
  181. if (cmp == 0)
  182. return (__db_duperr(dbp, flags));
  183. } else {
  184. hcp->dup_tlen = LEN_HDATA(dbp, hcp->page,
  185.     dbp->pgsize, hcp->indx);
  186. hcp->dup_len = nval->size;
  187. F_SET(hcp, H_ISDUP);
  188. if (flags == DB_KEYFIRST)
  189. hcp->dup_off = tmp_val.doff = 0;
  190. else
  191. hcp->dup_off =
  192.     tmp_val.doff = hcp->dup_tlen;
  193. }
  194. break;
  195. case DB_BEFORE:
  196. tmp_val.doff = hcp->dup_off;
  197. break;
  198. case DB_AFTER:
  199. tmp_val.doff = hcp->dup_off + DUP_SIZE(hcp->dup_len);
  200. break;
  201. }
  202. /* Add the duplicate. */
  203. ret = __ham_replpair(dbc, &tmp_val, 0);
  204. if (ret == 0)
  205. ret = mpf->set(mpf, hcp->page, DB_MPOOL_DIRTY);
  206. if (ret != 0)
  207. return (ret);
  209. /* Now, update the cursor if necessary. */
  210. switch (flags) {
  211. case DB_AFTER:
  212. hcp->dup_off += DUP_SIZE(hcp->dup_len);
  213. hcp->dup_len = nval->size;
  214. hcp->dup_tlen += (db_indx_t)DUP_SIZE(nval->size);
  215. break;
  216. case DB_KEYFIRST:
  217. case DB_KEYLAST:
  218. case DB_BEFORE:
  219. hcp->dup_tlen += (db_indx_t)DUP_SIZE(nval->size);
  220. hcp->dup_len = nval->size;
  221. break;
  222. }
  223. ret = __ham_c_update(dbc, tmp_val.size, 1, 1);
  224. return (ret);
  225. }
  227. /*
  228.  * If we get here, then we're on duplicate pages; set pgnop and
  229.  * return so the common code can handle it.
  230.  */
  231. memcpy(pgnop, HOFFDUP_PGNO(H_PAIRDATA(dbp, hcp->page, hcp->indx)),
  232.     sizeof(db_pgno_t));
  234. return (ret);
  235. }
  237. /*
  238.  * Convert an on-page set of duplicates to an offpage set of duplicates.
  239.  *
  240.  * PUBLIC: int __ham_dup_convert __P((DBC *));
  241.  */
  242. int
  243. __ham_dup_convert(dbc)
  244. DBC *dbc;
  245. {
  246. BOVERFLOW bo;
  247. DB *dbp;
  248. DBC **hcs;
  249. DBT dbt;
  250. DB_LSN lsn;
  251. DB_MPOOLFILE *mpf;
  252. HASH_CURSOR *hcp;
  253. HOFFPAGE ho;
  254. PAGE *dp;
  255. db_indx_t i, len, off;
  256. int c, ret, t_ret;
  257. u_int8_t *p, *pend;
  259. dbp = dbc->dbp;
  260. mpf = dbp->mpf;
  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. goto err;
  279. /*
  280.  * Now put the duplicates onto the new page.
  281.  */
  282. dbt.flags = 0;
  283. switch (HPAGE_PTYPE(H_PAIRDATA(dbp, 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(dbp, hcp->page, dbp->pgsize, hcp->indx);
  287. dbt.data = HKEYDATA_DATA(H_PAIRDATA(dbp, 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, P_ENTRY(dbp, hcp->page, H_DATAINDEX(hcp->indx)),
  294.     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);
  304. finish: if (ret == 0) {
  305. if ((ret = mpf->set(mpf, dp, DB_MPOOL_DIRTY)) != 0)
  306. break;
  308. /* Update any other cursors. */
  309. if (hcs != NULL && DBC_LOGGING(dbc) &&
  310.     IS_SUBTRANSACTION(dbc->txn)) {
  311. if ((ret = __ham_chgpg_log(dbp, dbc->txn,
  312.     &lsn, 0, DB_HAM_DUP, PGNO(hcp->page),
  313.     PGNO(dp), hcp->indx, 0)) != 0)
  314. break;
  315. }
  316. for (c = 0; hcs != NULL && hcs[c] != NULL; c++)
  317. if ((ret = __ham_dcursor(hcs[c],
  318.     PGNO(dp), 0)) != 0)
  319. break;
  320. }
  321. break;
  322. case H_DUPLICATE:
  323. p = HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page, hcp->indx));
  324. pend = p +
  325.     LEN_HDATA(dbp, hcp->page, dbp->pgsize, hcp->indx);
  327. /*
  328.  * We need to maintain the duplicate cursor position.
  329.  * Keep track of where we are in the duplicate set via
  330.  * the offset, and when it matches the one in the cursor,
  331.  * set the off-page duplicate cursor index to the current
  332.  * index.
  333.  */
  334. for (off = 0, i = 0; p < pend; i++) {
  335. memcpy(&len, p, sizeof(db_indx_t));
  336. dbt.size = len;
  337. p += sizeof(db_indx_t);
  338. dbt.data = p;
  339. p += len + sizeof(db_indx_t);
  340. if ((ret = __db_pitem(dbc, dp,
  341.     i, BKEYDATA_SIZE(dbt.size), NULL, &dbt)) != 0)
  342. break;
  344. /* Update any other cursors */
  345. if (hcs != NULL && DBC_LOGGING(dbc) &&
  346.     IS_SUBTRANSACTION(dbc->txn)) {
  347. if ((ret = __ham_chgpg_log(dbp, dbc->txn,
  348.     &lsn, 0, DB_HAM_DUP, PGNO(hcp->page),
  349.     PGNO(dp), hcp->indx, i)) != 0)
  350. break;
  351. }
  352. for (c = 0; hcs != NULL && hcs[c] != NULL; c++)
  353. if (((HASH_CURSOR *)(hcs[c]->internal))->dup_off
  354.     == off && (ret = __ham_dcursor(hcs[c],
  355.     PGNO(dp), i)) != 0)
  356. goto err;
  357. off += len + 2 * sizeof(db_indx_t);
  358. }
  359. break;
  360. default:
  361. ret = __db_pgfmt(dbp->dbenv, (u_long)hcp->pgno);
  362. break;
  363. }
  365. /*
  366.  * Now attach this to the source page in place of the old duplicate
  367.  * item.
  368.  */
  369. if (ret == 0)
  370. ret = __ham_move_offpage(dbc, hcp->page,
  371.     (u_int32_t)H_DATAINDEX(hcp->indx), PGNO(dp));
  373. err: if (ret == 0)
  374. ret = mpf->set(mpf, hcp->page, DB_MPOOL_DIRTY);
  376. if ((t_ret =
  377.     mpf->put(mpf, dp, ret == 0 ? DB_MPOOL_DIRTY : 0)) != 0 && ret == 0)
  378. ret = t_ret;
  380. if (ret == 0)
  381. hcp->dup_tlen = hcp->dup_off = hcp->dup_len = 0;
  383. if (hcs != NULL)
  384. __os_free(dbp->dbenv, hcs);
  386. return (ret);
  387. }
  389. /*
  390.  * __ham_make_dup
  391.  *
  392.  * Take a regular dbt and make it into a duplicate item with all the partial
  393.  * information set appropriately. If the incoming dbt is a partial, assume
  394.  * we are creating a new entry and make sure that we do any initial padding.
  395.  *
  396.  * PUBLIC: int __ham_make_dup __P((DB_ENV *,
  397.  * PUBLIC:     const DBT *, DBT *d, void **, u_int32_t *));
  398.  */
  399. int
  400. __ham_make_dup(dbenv, notdup, duplicate, bufp, sizep)
  401. DB_ENV *dbenv;
  402. const DBT *notdup;
  403. DBT *duplicate;
  404. void **bufp;
  405. u_int32_t *sizep;
  406. {
  407. db_indx_t tsize, item_size;
  408. int ret;
  409. u_int8_t *p;
  411. item_size = (db_indx_t)notdup->size;
  412. if (F_ISSET(notdup, DB_DBT_PARTIAL))
  413. item_size += notdup->doff;
  415. tsize = DUP_SIZE(item_size);
  416. if ((ret = __ham_init_dbt(dbenv, duplicate, tsize, bufp, sizep)) != 0)
  417. return (ret);
  419. duplicate->dlen = 0;
  420. duplicate->flags = notdup->flags;
  421. F_SET(duplicate, DB_DBT_PARTIAL);
  423. p = duplicate->data;
  424. memcpy(p, &item_size, sizeof(db_indx_t));
  425. p += sizeof(db_indx_t);
  426. if (F_ISSET(notdup, DB_DBT_PARTIAL)) {
  427. memset(p, 0, notdup->doff);
  428. p += notdup->doff;
  429. }
  430. memcpy(p, notdup->data, notdup->size);
  431. p += notdup->size;
  432. memcpy(p, &item_size, sizeof(db_indx_t));
  434. duplicate->doff = 0;
  435. duplicate->dlen = notdup->size;
  437. return (0);
  438. }
  440. /*
  441.  * __ham_check_move --
  442.  *
  443.  * Check if we can do whatever we need to on this page.  If not,
  444.  * then we'll have to move the current element to a new page.
  445.  */
  446. static int
  447. __ham_check_move(dbc, add_len)
  448. DBC *dbc;
  449. u_int32_t add_len;
  450. {
  451. DB *dbp;
  452. DBT k, d;
  453. DB_LSN new_lsn;
  454. DB_MPOOLFILE *mpf;
  455. HASH_CURSOR *hcp;
  456. PAGE *next_pagep;
  457. db_pgno_t next_pgno;
  458. u_int32_t new_datalen, old_len, rectype;
  459. u_int8_t *hk;
  460. int ret;
  462. dbp = dbc->dbp;
  463. mpf = dbp->mpf;
  464. hcp = (HASH_CURSOR *)dbc->internal;
  466. hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  468. /*
  469.  * If the item is already off page duplicates or an offpage item,
  470.  * then we know we can do whatever we need to do in-place
  471.  */
  472. if (HPAGE_PTYPE(hk) == H_OFFDUP || HPAGE_PTYPE(hk) == H_OFFPAGE)
  473. return (0);
  475. old_len = LEN_HITEM(dbp, hcp->page, dbp->pgsize, H_DATAINDEX(hcp->indx));
  476. new_datalen = old_len - HKEYDATA_SIZE(0) + add_len;
  477. if (HPAGE_PTYPE(hk) != H_DUPLICATE)
  478. new_datalen += DUP_SIZE(0);
  480. /*
  481.  * We need to add a new page under two conditions:
  482.  * 1. The addition makes the total data length cross the BIG
  483.  *    threshold and the OFFDUP structure won't fit on this page.
  484.  * 2. The addition does not make the total data cross the
  485.  *    threshold, but the new data won't fit on the page.
  486.  * If neither of these is true, then we can return.
  487.  */
  488. if (ISBIG(hcp, new_datalen) && (old_len > HOFFDUP_SIZE ||
  489.     HOFFDUP_SIZE - old_len <= P_FREESPACE(dbp, hcp->page)))
  490. return (0);
  492. if (!ISBIG(hcp, new_datalen) && add_len <= P_FREESPACE(dbp, hcp->page))
  493. return (0);
  495. /*
  496.  * If we get here, then we need to move the item to a new page.
  497.  * Check if there are more pages in the chain.  We now need to
  498.  * update new_datalen to include the size of both the key and
  499.  * the data that we need to move.
  500.  */
  502. new_datalen = ISBIG(hcp, new_datalen) ?
  503.     HOFFDUP_SIZE : HKEYDATA_SIZE(new_datalen);
  504. new_datalen += LEN_HITEM(dbp, hcp->page, dbp->pgsize, H_KEYINDEX(hcp->indx));
  506. next_pagep = NULL;
  507. for (next_pgno = NEXT_PGNO(hcp->page); next_pgno != PGNO_INVALID;
  508.     next_pgno = NEXT_PGNO(next_pagep)) {
  509. if (next_pagep != NULL &&
  510.     (ret = mpf->put(mpf, next_pagep, 0)) != 0)
  511. return (ret);
  513. if ((ret = mpf->get(mpf,
  514.     &next_pgno, DB_MPOOL_CREATE, &next_pagep)) != 0)
  515. return (ret);
  517. if (P_FREESPACE(dbp, next_pagep) >= new_datalen)
  518. break;
  519. }
  521. /* No more pages, add one. */
  522. if (next_pagep == NULL && (ret = __ham_add_ovflpage(dbc,
  523.     hcp->page, 0, &next_pagep)) != 0)
  524. return (ret);
  526. /* Add new page at the end of the chain. */
  527. if (P_FREESPACE(dbp, next_pagep) < new_datalen && (ret =
  528.     __ham_add_ovflpage(dbc, next_pagep, 1, &next_pagep)) != 0) {
  529. (void)mpf->put(mpf, next_pagep, 0);
  530. return (ret);
  531. }
  533. /* Copy the item to the new page. */
  534. if (DBC_LOGGING(dbc)) {
  535. rectype = PUTPAIR;
  536. k.flags = 0;
  537. d.flags = 0;
  538. if (HPAGE_PTYPE(
  539.     H_PAIRKEY(dbp, hcp->page, hcp->indx)) == H_OFFPAGE) {
  540. rectype |= PAIR_KEYMASK;
  541. k.data = H_PAIRKEY(dbp, hcp->page, hcp->indx);
  542. k.size = HOFFPAGE_SIZE;
  543. } else {
  544. k.data =
  545.     HKEYDATA_DATA(H_PAIRKEY(dbp, hcp->page, hcp->indx));
  546. k.size =
  547.     LEN_HKEY(dbp, hcp->page, dbp->pgsize, hcp->indx);
  548. }
  550. if (HPAGE_PTYPE(hk) == H_OFFPAGE) {
  551. rectype |= PAIR_DATAMASK;
  552. d.data = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  553. d.size = HOFFPAGE_SIZE;
  554. } else {
  555. if (HPAGE_PTYPE(H_PAIRDATA(dbp, hcp->page, hcp->indx))
  556.     == H_DUPLICATE)
  557. rectype |= PAIR_DUPMASK;
  558. d.data =
  559.     HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page, hcp->indx));
  560. d.size = LEN_HDATA(dbp, hcp->page,
  561.     dbp->pgsize, hcp->indx);
  562. }
  564. if ((ret = __ham_insdel_log(dbp,
  565.     dbc->txn, &new_lsn, 0, rectype, PGNO(next_pagep),
  566.     (u_int32_t)NUM_ENT(next_pagep), &LSN(next_pagep),
  567.     &k, &d)) != 0) {
  568. (void)mpf->put(mpf, next_pagep, 0);
  569. return (ret);
  570. }
  571. } else
  572. LSN_NOT_LOGGED(new_lsn);
  574. /* Move lsn onto page. */
  575. LSN(next_pagep) = new_lsn; /* Structure assignment. */
  577. __ham_copy_item(dbp, hcp->page, H_KEYINDEX(hcp->indx), next_pagep);
  578. __ham_copy_item(dbp, hcp->page, H_DATAINDEX(hcp->indx), next_pagep);
  580. /*
  581.  * We've just manually inserted a key and set of data onto
  582.  * next_pagep;  however, it's possible that our caller will
  583.  * return without further modifying the new page, for instance
  584.  * if DB_NODUPDATA is set and our new item is a duplicate duplicate.
  585.  * Thus, to be on the safe side, we need to mark the page dirty
  586.  * here. [#2996]
  587.  *
  588.  * Note that __ham_del_pair should dirty the page we're moving
  589.  * the items from, so we need only dirty the new page ourselves.
  590.  */
  591. if ((ret = mpf->set(mpf, next_pagep, DB_MPOOL_DIRTY)) != 0)
  592. goto out;
  594. /* Update all cursors that used to point to this item. */
  595. if ((ret = __ham_c_chgpg(dbc, PGNO(hcp->page), H_KEYINDEX(hcp->indx),
  596.     PGNO(next_pagep), NUM_ENT(next_pagep) - 2)) != 0)
  597. goto out;
  599. /* Now delete the pair from the current page. */
  600. ret = __ham_del_pair(dbc, 0);
  602. /*
  603.  * __ham_del_pair decremented nelem.  This is incorrect;  we
  604.  * manually copied the element elsewhere, so the total number
  605.  * of elements hasn't changed.  Increment it again.
  606.  *
  607.  * !!!
  608.  * Note that we still have the metadata page pinned, and
  609.  * __ham_del_pair dirtied it, so we don't need to set the dirty
  610.  * flag again.
  611.  */
  612. if (!STD_LOCKING(dbc))
  613. hcp->hdr->nelem++;
  615. out:
  616. (void)mpf->put(mpf, hcp->page, DB_MPOOL_DIRTY);
  617. hcp->page = next_pagep;
  618. hcp->pgno = PGNO(hcp->page);
  619. hcp->indx = NUM_ENT(hcp->page) - 2;
  620. F_SET(hcp, H_EXPAND);
  621. F_CLR(hcp, H_DELETED);
  623. return (ret);
  624. }
  626. /*
  627.  * __ham_move_offpage --
  628.  * Replace an onpage set of duplicates with the OFFDUP structure
  629.  * that references the duplicate page.
  630.  *
  631.  * XXX
  632.  * This is really just a special case of __onpage_replace; we should
  633.  * probably combine them.
  634.  *
  635.  */
  636. static int
  637. __ham_move_offpage(dbc, pagep, ndx, pgno)
  638. DBC *dbc;
  639. PAGE *pagep;
  640. u_int32_t ndx;
  641. db_pgno_t pgno;
  642. {
  643. DB *dbp;
  644. DBT new_dbt;
  645. DBT old_dbt;
  646. HOFFDUP od;
  647. db_indx_t i, *inp;
  648. int32_t shrink;
  649. u_int8_t *src;
  650. int ret;
  652. dbp = dbc->dbp;
  653. od.type = H_OFFDUP;
  654. UMRW_SET(od.unused[0]);
  655. UMRW_SET(od.unused[1]);
  656. UMRW_SET(od.unused[2]);
  657. od.pgno = pgno;
  658. ret = 0;
  660. if (DBC_LOGGING(dbc)) {
  661. new_dbt.data = &od;
  662. new_dbt.size = HOFFDUP_SIZE;
  663. old_dbt.data = P_ENTRY(dbp, pagep, ndx);
  664. old_dbt.size = LEN_HITEM(dbp, pagep, dbp->pgsize, ndx);
  665. if ((ret = __ham_replace_log(dbp, dbc->txn, &LSN(pagep), 0,
  666.     PGNO(pagep), (u_int32_t)ndx, &LSN(pagep), -1,
  667.     &old_dbt, &new_dbt, 0)) != 0)
  668. return (ret);
  669. } else
  670. LSN_NOT_LOGGED(LSN(pagep));
  672. shrink = LEN_HITEM(dbp, pagep, dbp->pgsize, ndx) - HOFFDUP_SIZE;
  673. inp = P_INP(dbp, pagep);
  675. if (shrink != 0) {
  676. /* Copy data. */
  677. src = (u_int8_t *)(pagep) + HOFFSET(pagep);
  678. memmove(src + shrink, src, inp[ndx] - HOFFSET(pagep));
  679. HOFFSET(pagep) += shrink;
  681. /* Update index table. */
  682. for (i = ndx; i < NUM_ENT(pagep); i++)
  683. inp[i] += shrink;
  684. }
  686. /* Now copy the offdup entry onto the page. */
  687. memcpy(P_ENTRY(dbp, pagep, ndx), &od, HOFFDUP_SIZE);
  688. return (ret);
  689. }
  691. /*
  692.  * __ham_dsearch:
  693.  * Locate a particular duplicate in a duplicate set.  Make sure that
  694.  * we exit with the cursor set appropriately.
  695.  *
  696.  * PUBLIC: void __ham_dsearch
  697.  * PUBLIC:     __P((DBC *, DBT *, u_int32_t *, int *, u_int32_t));
  698.  */
  699. void
  700. __ham_dsearch(dbc, dbt, offp, cmpp, flags)
  701. DBC *dbc;
  702. DBT *dbt;
  703. u_int32_t *offp, flags;
  704. int *cmpp;
  705. {
  706. DB *dbp;
  707. HASH_CURSOR *hcp;
  708. DBT cur;
  709. db_indx_t i, len;
  710. int (*func) __P((DB *, const DBT *, const DBT *));
  711. u_int8_t *data;
  713. dbp = dbc->dbp;
  714. hcp = (HASH_CURSOR *)dbc->internal;
  715. func = dbp->dup_compare == NULL ? __bam_defcmp : dbp->dup_compare;
  717. i = F_ISSET(hcp, H_CONTINUE) ? hcp->dup_off: 0;
  718. data = HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page, hcp->indx)) + i;
  719. hcp->dup_tlen = LEN_HDATA(dbp, hcp->page, dbp->pgsize, hcp->indx);
  720. while (i < hcp->dup_tlen) {
  721. memcpy(&len, data, sizeof(db_indx_t));
  722. data += sizeof(db_indx_t);
  723. cur.data = data;
  724. cur.size = (u_int32_t)len;
  726. /*
  727.  * If we find an exact match, we're done.  If in a sorted
  728.  * duplicate set and the item is larger than our test item,
  729.  * we're done.  In the latter case, if permitting partial
  730.  * matches, it's not a failure.
  731.  */
  732. *cmpp = func(dbp, dbt, &cur);
  733. if (*cmpp == 0)
  734. break;
  735. if (*cmpp < 0 && dbp->dup_compare != NULL) {
  736. if (flags == DB_GET_BOTH_RANGE)
  737. *cmpp = 0;
  738. break;
  739. }
  741. i += len + 2 * sizeof(db_indx_t);
  742. data += len + sizeof(db_indx_t);
  743. }
  745. *offp = i;
  746. hcp->dup_off = i;
  747. hcp->dup_len = len;
  748. F_SET(hcp, H_ISDUP);
  749. }
  751. #ifdef DEBUG
  752. /*
  753.  * __ham_cprint --
  754.  * Display the current cursor list.
  755.  *
  756.  * PUBLIC: void __ham_cprint __P((DBC *));
  757.  */
  758. void
  759. __ham_cprint(dbc)
  760. DBC *dbc;
  761. {
  762. HASH_CURSOR *cp;
  764. cp = (HASH_CURSOR *)dbc->internal;
  766. fprintf(stderr, "%#0lx->%#0lx: page: %lu index: %lu",
  767.     P_TO_ULONG(dbc), P_TO_ULONG(cp), (u_long)cp->pgno,
  768.     (u_long)cp->indx);
  769. if (F_ISSET(cp, H_DELETED))
  770. fprintf(stderr, " (deleted)");
  771. fprintf(stderr, "n");
  772. }
  773. #endif /* DEBUG */
  775. /*
  776.  * __ham_dcursor --
  777.  *
  778.  * Create an off page duplicate cursor for this cursor.
  779.  */
  780. static int
  781. __ham_dcursor(dbc, pgno, indx)
  782. DBC *dbc;
  783. db_pgno_t pgno;
  784. u_int32_t indx;
  785. {
  786. DB *dbp;
  787. HASH_CURSOR *hcp;
  788. BTREE_CURSOR *dcp;
  789. int ret;
  791. dbp = dbc->dbp;
  792. hcp = (HASH_CURSOR *)dbc->internal;
  794. if ((ret = __db_c_newopd(dbc, pgno, hcp->opd, &hcp->opd)) != 0)
  795. return (ret);
  797. dcp = (BTREE_CURSOR *)hcp->opd->internal;
  798. dcp->pgno = pgno;
  799. dcp->indx = indx;
  801. if (dbp->dup_compare == NULL) {
  802. /*
  803.  * Converting to off-page Recno trees is tricky.  The
  804.  * record number for the cursor is the index + 1 (to
  805.  * convert to 1-based record numbers).
  806.  */
  807. dcp->recno = indx + 1;
  808. }
  810. /*
  811.  * Transfer the deleted flag from the top-level cursor to the
  812.  * created one.
  813.  */
  814. if (F_ISSET(hcp, H_DELETED)) {
  815. F_SET(dcp, C_DELETED);
  816. F_CLR(hcp, H_DELETED);
  817. }
  819. return (0);
  820. }
  822. /*
  823.  * __ham_c_chgpg --
  824.  * Adjust the cursors after moving an item to a new page.  We only
  825.  * move cursors that are pointing at this one item and are not
  826.  * deleted;  since we only touch non-deleted cursors, and since
  827.  * (by definition) no item existed at the pgno/indx we're moving the
  828.  * item to, we're guaranteed that all the cursors we affect here or
  829.  * on abort really do refer to this one item.
  830.  */
  831. static int
  832. __ham_c_chgpg(dbc, old_pgno, old_index, new_pgno, new_index)
  833. DBC *dbc;
  834. db_pgno_t old_pgno, new_pgno;
  835. u_int32_t old_index, new_index;
  836. {
  837. DB *dbp, *ldbp;
  838. DB_ENV *dbenv;
  839. DB_LSN lsn;
  840. DB_TXN *my_txn;
  841. DBC *cp;
  842. HASH_CURSOR *hcp;
  843. int found, ret;
  845. dbp = dbc->dbp;
  846. dbenv = dbp->dbenv;
  848. my_txn = IS_SUBTRANSACTION(dbc->txn) ? dbc->txn : NULL;
  849. found = 0;
  851. MUTEX_THREAD_LOCK(dbenv, dbenv->dblist_mutexp);
  852. for (ldbp = __dblist_get(dbenv, dbp->adj_fileid);
  853.     ldbp != NULL && ldbp->adj_fileid == dbp->adj_fileid;
  854.     ldbp = LIST_NEXT(ldbp, dblistlinks)) {
  855. MUTEX_THREAD_LOCK(dbenv, dbp->mutexp);
  856. for (cp = TAILQ_FIRST(&ldbp->active_queue); cp != NULL;
  857.     cp = TAILQ_NEXT(cp, links)) {
  858. if (cp == dbc || cp->dbtype != DB_HASH)
  859. continue;
  861. hcp = (HASH_CURSOR *)cp->internal;
  863. /*
  864.  * If a cursor is deleted, it doesn't refer to this
  865.  * item--it just happens to have the same indx, but
  866.  * it points to a former neighbor.  Don't move it.
  867.  */
  868. if (F_ISSET(hcp, H_DELETED))
  869. continue;
  871. if (hcp->pgno == old_pgno) {
  872. if (hcp->indx == old_index) {
  873. hcp->pgno = new_pgno;
  874. hcp->indx = new_index;
  875. } else
  876. continue;
  877. if (my_txn != NULL && cp->txn != my_txn)
  878. found = 1;
  879. }
  880. }
  881. MUTEX_THREAD_UNLOCK(dbenv, dbp->mutexp);
  882. }
  883. MUTEX_THREAD_UNLOCK(dbenv, dbenv->dblist_mutexp);
  885. if (found != 0 && DBC_LOGGING(dbc)) {
  886. if ((ret = __ham_chgpg_log(dbp, my_txn, &lsn, 0, DB_HAM_CHGPG,
  887.     old_pgno, new_pgno, old_index, new_index)) != 0)
  888. return (ret);
  889. }
  890. return (0);
  891. }