hash.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:52k
源码类别:

MySQL数据库

开发平台:

Visual 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.  * Margo Seltzer.  All rights reserved.
  10.  */
  11. /*
  12.  * Copyright (c) 1990, 1993, 1994
  13.  * The Regents of the University of California.  All rights reserved.
  14.  *
  15.  * This code is derived from software contributed to Berkeley by
  16.  * Margo Seltzer.
  17.  *
  18.  * Redistribution and use in source and binary forms, with or without
  19.  * modification, are permitted provided that the following conditions
  20.  * are met:
  21.  * 1. Redistributions of source code must retain the above copyright
  22.  *    notice, this list of conditions and the following disclaimer.
  23.  * 2. Redistributions in binary form must reproduce the above copyright
  24.  *    notice, this list of conditions and the following disclaimer in the
  25.  *    documentation and/or other materials provided with the distribution.
  26.  * 3. Neither the name of the University nor the names of its contributors
  27.  *    may be used to endorse or promote products derived from this software
  28.  *    without specific prior written permission.
  29.  *
  30.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  31.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  32.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  34.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  35.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  36.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  38.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  39.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  40.  * SUCH DAMAGE.
  41.  */
  42. #include "db_config.h"
  43. #ifndef lint
  44. static const char revid[] = "$Id: hash.c,v 11.166 2002/08/06 06:11:25 bostic Exp $";
  45. #endif /* not lint */
  46. #ifndef NO_SYSTEM_INCLUDES
  47. #include <sys/types.h>
  48. #include <stdlib.h>
  49. #include <string.h>
  50. #endif
  51. #include "db_int.h"
  52. #include "dbinc/db_page.h"
  53. #include "dbinc/db_shash.h"
  54. #include "dbinc/btree.h"
  55. #include "dbinc/hash.h"
  56. #include "dbinc/lock.h"
  57. static int  __ham_bulk __P((DBC *, DBT *, u_int32_t));
  58. static int  __ham_c_close __P((DBC *, db_pgno_t, int *));
  59. static int  __ham_c_del __P((DBC *));
  60. static int  __ham_c_destroy __P((DBC *));
  61. static int  __ham_c_get __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *));
  62. static int  __ham_c_put __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *));
  63. static int  __ham_c_writelock __P((DBC *));
  64. static int  __ham_dup_return __P((DBC *, DBT *, u_int32_t));
  65. static int  __ham_expand_table __P((DBC *));
  66. static int  __ham_lookup __P((DBC *,
  67. const DBT *, u_int32_t, db_lockmode_t, db_pgno_t *));
  68. static int  __ham_overwrite __P((DBC *, DBT *, u_int32_t));
  69. /*
  70.  * __ham_quick_delete --
  71.  * When performing a DB->del operation that does not involve secondary
  72.  * indices and is not removing an off-page duplicate tree, we can
  73.  * speed things up substantially by removing the entire duplicate
  74.  * set, if any is present, in one operation, rather than by conjuring
  75.  * up and deleting each of the items individually.  (All are stored
  76.  * in one big HKEYDATA structure.)  We don't bother to distinguish
  77.  * on-page duplicate sets from single, non-dup items;  they're deleted
  78.  * in exactly the same way.
  79.  *
  80.  * This function is called by __db_delete when the appropriate
  81.  * conditions are met, and it performs the delete in the optimized way.
  82.  *
  83.  * The cursor should be set to the first item in the duplicate
  84.  * set, or to the sole key/data pair when the key does not have a
  85.  * duplicate set, before the function is called.
  86.  *
  87.  * PUBLIC: int __ham_quick_delete __P((DBC *));
  88.  */
  89. int
  90. __ham_quick_delete(dbc)
  91. DBC *dbc;
  92. {
  93. int ret, t_ret;
  94. if ((ret = __ham_get_meta(dbc)) != 0)
  95. return (ret);
  96. /* Assert that we're not using secondary indices. */
  97. DB_ASSERT(!F_ISSET(dbc->dbp, DB_AM_SECONDARY));
  98. /*
  99.  * We should assert that we're not a primary either, but that
  100.  * would require grabbing the dbp's mutex, so we don't bother.
  101.  */
  102. /* Assert that we're set, but not to an off-page duplicate. */
  103. DB_ASSERT(IS_INITIALIZED(dbc));
  104. DB_ASSERT(((HASH_CURSOR *)dbc->internal)->opd == NULL);
  105. ret = __ham_del_pair(dbc, 1);
  106. if ((t_ret = __ham_release_meta(dbc)) != 0 && ret == 0)
  107. ret = t_ret;
  108. return (ret);
  109. }
  110. /* ****************** CURSORS ********************************** */
  111. /*
  112.  * __ham_c_init --
  113.  * Initialize the hash-specific portion of a cursor.
  114.  *
  115.  * PUBLIC: int __ham_c_init __P((DBC *));
  116.  */
  117. int
  118. __ham_c_init(dbc)
  119. DBC *dbc;
  120. {
  121. DB_ENV *dbenv;
  122. HASH_CURSOR *new_curs;
  123. int ret;
  124. dbenv = dbc->dbp->dbenv;
  125. if ((ret = __os_calloc(dbenv,
  126.     1, sizeof(struct cursor_t), &new_curs)) != 0)
  127. return (ret);
  128. if ((ret = __os_malloc(dbenv,
  129.     dbc->dbp->pgsize, &new_curs->split_buf)) != 0) {
  130. __os_free(dbenv, new_curs);
  131. return (ret);
  132. }
  133. dbc->internal = (DBC_INTERNAL *) new_curs;
  134. dbc->c_close = __db_c_close;
  135. dbc->c_count = __db_c_count;
  136. dbc->c_del = __db_c_del;
  137. dbc->c_dup = __db_c_dup;
  138. dbc->c_get = dbc->c_real_get = __db_c_get;
  139. dbc->c_pget = __db_c_pget;
  140. dbc->c_put = __db_c_put;
  141. dbc->c_am_bulk = __ham_bulk;
  142. dbc->c_am_close = __ham_c_close;
  143. dbc->c_am_del = __ham_c_del;
  144. dbc->c_am_destroy = __ham_c_destroy;
  145. dbc->c_am_get = __ham_c_get;
  146. dbc->c_am_put = __ham_c_put;
  147. dbc->c_am_writelock = __ham_c_writelock;
  148. __ham_item_init(dbc);
  149. return (0);
  150. }
  151. /*
  152.  * __ham_c_close --
  153.  * Close down the cursor from a single use.
  154.  */
  155. static int
  156. __ham_c_close(dbc, root_pgno, rmroot)
  157. DBC *dbc;
  158. db_pgno_t root_pgno;
  159. int *rmroot;
  160. {
  161. DB_MPOOLFILE *mpf;
  162. HASH_CURSOR *hcp;
  163. HKEYDATA *dp;
  164. int doroot, gotmeta, ret, t_ret;
  165. u_int32_t dirty;
  166. COMPQUIET(rmroot, 0);
  167. mpf = dbc->dbp->mpf;
  168. dirty = 0;
  169. doroot = gotmeta = ret = 0;
  170. hcp = (HASH_CURSOR *) dbc->internal;
  171. /* Check for off page dups. */
  172. if (dbc->internal->opd != NULL) {
  173. if ((ret = __ham_get_meta(dbc)) != 0)
  174. goto done;
  175. gotmeta = 1;
  176. if ((ret = __ham_get_cpage(dbc, DB_LOCK_READ)) != 0)
  177. goto out;
  178. dp = (HKEYDATA *)H_PAIRDATA(dbc->dbp, hcp->page, hcp->indx);
  179. /* If its not a dup we aborted before we changed it. */
  180. if (HPAGE_PTYPE(dp) == H_OFFDUP)
  181. memcpy(&root_pgno,
  182.     HOFFPAGE_PGNO(dp), sizeof(db_pgno_t));
  183. else
  184. root_pgno = PGNO_INVALID;
  185. if ((ret =
  186.     hcp->opd->c_am_close(hcp->opd, root_pgno, &doroot)) != 0)
  187. goto out;
  188. if (doroot != 0) {
  189. if ((ret = __ham_del_pair(dbc, 1)) != 0)
  190. goto out;
  191. dirty = DB_MPOOL_DIRTY;
  192. }
  193. }
  194. out: if (hcp->page != NULL && (t_ret =
  195.     mpf->put(mpf, hcp->page, dirty)) != 0 && ret == 0)
  196. ret = t_ret;
  197. if (gotmeta != 0 && (t_ret = __ham_release_meta(dbc)) != 0 && ret == 0)
  198. ret = t_ret;
  199. done:
  200. __ham_item_init(dbc);
  201. return (ret);
  202. }
  203. /*
  204.  * __ham_c_destroy --
  205.  * Cleanup the access method private part of a cursor.
  206.  */
  207. static int
  208. __ham_c_destroy(dbc)
  209. DBC *dbc;
  210. {
  211. HASH_CURSOR *hcp;
  212. hcp = (HASH_CURSOR *)dbc->internal;
  213. if (hcp->split_buf != NULL)
  214. __os_free(dbc->dbp->dbenv, hcp->split_buf);
  215. __os_free(dbc->dbp->dbenv, hcp);
  216. return (0);
  217. }
  218. /*
  219.  * __ham_c_count --
  220.  * Return a count of on-page duplicates.
  221.  *
  222.  * PUBLIC: int __ham_c_count __P((DBC *, db_recno_t *));
  223.  */
  224. int
  225. __ham_c_count(dbc, recnop)
  226. DBC *dbc;
  227. db_recno_t *recnop;
  228. {
  229. DB *dbp;
  230. DB_MPOOLFILE *mpf;
  231. HASH_CURSOR *hcp;
  232. db_indx_t len;
  233. db_recno_t recno;
  234. int ret, t_ret;
  235. u_int8_t *p, *pend;
  236. dbp = dbc->dbp;
  237. mpf = dbp->mpf;
  238. hcp = (HASH_CURSOR *)dbc->internal;
  239. recno = 0;
  240. if ((ret = __ham_get_cpage(dbc, DB_LOCK_READ)) != 0)
  241. return (ret);
  242. switch (HPAGE_PTYPE(H_PAIRDATA(dbp, hcp->page, hcp->indx))) {
  243. case H_KEYDATA:
  244. case H_OFFPAGE:
  245. recno = 1;
  246. break;
  247. case H_DUPLICATE:
  248. p = HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page, hcp->indx));
  249. pend = p +
  250.     LEN_HDATA(dbp, hcp->page, dbp->pgsize, hcp->indx);
  251. for (; p < pend; recno++) {
  252. /* p may be odd, so copy rather than just dereffing */
  253. memcpy(&len, p, sizeof(db_indx_t));
  254. p += 2 * sizeof(db_indx_t) + len;
  255. }
  256. break;
  257. default:
  258. ret = __db_pgfmt(dbp->dbenv, hcp->pgno);
  259. goto err;
  260. }
  261. *recnop = recno;
  262. err: if ((t_ret = mpf->put(mpf, hcp->page, 0)) != 0 && ret == 0)
  263. ret = t_ret;
  264. hcp->page = NULL;
  265. return (ret);
  266. }
  267. static int
  268. __ham_c_del(dbc)
  269. DBC *dbc;
  270. {
  271. DB *dbp;
  272. DBT repldbt;
  273. DB_MPOOLFILE *mpf;
  274. HASH_CURSOR *hcp;
  275. int ret, t_ret;
  276. dbp = dbc->dbp;
  277. mpf = dbp->mpf;
  278. hcp = (HASH_CURSOR *)dbc->internal;
  279. if (F_ISSET(hcp, H_DELETED))
  280. return (DB_NOTFOUND);
  281. if ((ret = __ham_get_meta(dbc)) != 0)
  282. goto out;
  283. if ((ret = __ham_get_cpage(dbc, DB_LOCK_WRITE)) != 0)
  284. goto out;
  285. /* Off-page duplicates. */
  286. if (HPAGE_TYPE(dbp, hcp->page, H_DATAINDEX(hcp->indx)) == H_OFFDUP)
  287. goto out;
  288. if (F_ISSET(hcp, H_ISDUP)) { /* On-page duplicate. */
  289. if (hcp->dup_off == 0 &&
  290.     DUP_SIZE(hcp->dup_len) == LEN_HDATA(dbp, hcp->page,
  291.     hcp->hdr->dbmeta.pagesize, hcp->indx))
  292. ret = __ham_del_pair(dbc, 1);
  293. else {
  294. repldbt.flags = 0;
  295. F_SET(&repldbt, DB_DBT_PARTIAL);
  296. repldbt.doff = hcp->dup_off;
  297. repldbt.dlen = DUP_SIZE(hcp->dup_len);
  298. repldbt.size = 0;
  299. repldbt.data = HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page,
  300.     hcp->indx));
  301. if ((ret = __ham_replpair(dbc, &repldbt, 0)) == 0) {
  302. hcp->dup_tlen -= DUP_SIZE(hcp->dup_len);
  303. F_SET(hcp, H_DELETED);
  304. ret = __ham_c_update(dbc,
  305.     DUP_SIZE(hcp->dup_len), 0, 1);
  306. }
  307. }
  308. } else /* Not a duplicate */
  309. ret = __ham_del_pair(dbc, 1);
  310. out: if (hcp->page != NULL) {
  311. if ((t_ret = mpf->put(mpf,
  312.     hcp->page, ret == 0 ? DB_MPOOL_DIRTY : 0)) && ret == 0)
  313. ret = t_ret;
  314. hcp->page = NULL;
  315. }
  316. if ((t_ret = __ham_release_meta(dbc)) != 0 && ret == 0)
  317. ret = t_ret;
  318. return (ret);
  319. }
  320. /*
  321.  * __ham_c_dup --
  322.  * Duplicate a hash cursor, such that the new one holds appropriate
  323.  * locks for the position of the original.
  324.  *
  325.  * PUBLIC: int __ham_c_dup __P((DBC *, DBC *));
  326.  */
  327. int
  328. __ham_c_dup(orig_dbc, new_dbc)
  329. DBC *orig_dbc, *new_dbc;
  330. {
  331. HASH_CURSOR *orig, *new;
  332. orig = (HASH_CURSOR *)orig_dbc->internal;
  333. new = (HASH_CURSOR *)new_dbc->internal;
  334. new->bucket = orig->bucket;
  335. new->lbucket = orig->lbucket;
  336. new->dup_off = orig->dup_off;
  337. new->dup_len = orig->dup_len;
  338. new->dup_tlen = orig->dup_tlen;
  339. if (F_ISSET(orig, H_DELETED))
  340. F_SET(new, H_DELETED);
  341. if (F_ISSET(orig, H_ISDUP))
  342. F_SET(new, H_ISDUP);
  343. /*
  344.  * If the old cursor held a lock and we're not in transactions, get one
  345.  * for the new one.   The reason that we don't need a new lock if we're
  346.  * in a transaction is because we already hold a lock and will continue
  347.  * to do so until commit, so there is no point in reaquiring it. We
  348.  * don't know if the old lock was a read or write lock, but it doesn't
  349.  * matter. We'll get a read lock.  We know that this locker already
  350.  * holds a lock of the correct type, so if we need a write lock and
  351.  * request it, we know that we'll get it.
  352.  */
  353. if (!LOCK_ISSET(orig->lock) || orig_dbc->txn != NULL)
  354. return (0);
  355. return (__ham_lock_bucket(new_dbc, DB_LOCK_READ));
  356. }
  357. static int
  358. __ham_c_get(dbc, key, data, flags, pgnop)
  359. DBC *dbc;
  360. DBT *key;
  361. DBT *data;
  362. u_int32_t flags;
  363. db_pgno_t *pgnop;
  364. {
  365. DB *dbp;
  366. DB_MPOOLFILE *mpf;
  367. HASH_CURSOR *hcp;
  368. db_lockmode_t lock_type;
  369. int get_key, ret, t_ret;
  370. hcp = (HASH_CURSOR *)dbc->internal;
  371. dbp = dbc->dbp;
  372. mpf = dbp->mpf;
  373. /* Clear OR'd in additional bits so we can check for flag equality. */
  374. if (F_ISSET(dbc, DBC_RMW))
  375. lock_type = DB_LOCK_WRITE;
  376. else
  377. lock_type = DB_LOCK_READ;
  378. if ((ret = __ham_get_meta(dbc)) != 0)
  379. return (ret);
  380. hcp->seek_size = 0;
  381. ret = 0;
  382. get_key = 1;
  383. switch (flags) {
  384. case DB_PREV_NODUP:
  385. F_SET(hcp, H_NEXT_NODUP);
  386. /* FALLTHROUGH */
  387. case DB_PREV:
  388. if (IS_INITIALIZED(dbc)) {
  389. ret = __ham_item_prev(dbc, lock_type, pgnop);
  390. break;
  391. }
  392. /* FALLTHROUGH */
  393. case DB_LAST:
  394. ret = __ham_item_last(dbc, lock_type, pgnop);
  395. break;
  396. case DB_NEXT_NODUP:
  397. F_SET(hcp, H_NEXT_NODUP);
  398. /* FALLTHROUGH */
  399. case DB_NEXT:
  400. if (IS_INITIALIZED(dbc)) {
  401. ret = __ham_item_next(dbc, lock_type, pgnop);
  402. break;
  403. }
  404. /* FALLTHROUGH */
  405. case DB_FIRST:
  406. ret = __ham_item_first(dbc, lock_type, pgnop);
  407. break;
  408. case DB_NEXT_DUP:
  409. /* cgetchk has already determined that the cursor is set. */
  410. F_SET(hcp, H_DUPONLY);
  411. ret = __ham_item_next(dbc, lock_type, pgnop);
  412. break;
  413. case DB_SET:
  414. case DB_SET_RANGE:
  415. case DB_GET_BOTH:
  416. case DB_GET_BOTH_RANGE:
  417. ret = __ham_lookup(dbc, key, 0, lock_type, pgnop);
  418. get_key = 0;
  419. break;
  420. case DB_GET_BOTHC:
  421. F_SET(hcp, H_DUPONLY);
  422. ret = __ham_item_next(dbc, lock_type, pgnop);
  423. get_key = 0;
  424. break;
  425. case DB_CURRENT:
  426. /* cgetchk has already determined that the cursor is set. */
  427. if (F_ISSET(hcp, H_DELETED)) {
  428. ret = DB_KEYEMPTY;
  429. goto err;
  430. }
  431. ret = __ham_item(dbc, lock_type, pgnop);
  432. break;
  433. }
  434. /*
  435.  * Must always enter this loop to do error handling and
  436.  * check for big key/data pair.
  437.  */
  438. for (;;) {
  439. if (ret != 0 && ret != DB_NOTFOUND)
  440. goto err;
  441. else if (F_ISSET(hcp, H_OK)) {
  442. if (*pgnop == PGNO_INVALID)
  443. ret = __ham_dup_return(dbc, data, flags);
  444. break;
  445. } else if (!F_ISSET(hcp, H_NOMORE)) {
  446. __db_err(dbp->dbenv,
  447.     "H_NOMORE returned to __ham_c_get");
  448. ret = EINVAL;
  449. break;
  450. }
  451. /*
  452.  * Ran out of entries in a bucket; change buckets.
  453.  */
  454. switch (flags) {
  455. case DB_LAST:
  456. case DB_PREV:
  457. case DB_PREV_NODUP:
  458. ret = mpf->put(mpf, hcp->page, 0);
  459. hcp->page = NULL;
  460. if (hcp->bucket == 0) {
  461. ret = DB_NOTFOUND;
  462. hcp->pgno = PGNO_INVALID;
  463. goto err;
  464. }
  465. F_CLR(hcp, H_ISDUP);
  466. hcp->bucket--;
  467. hcp->indx = NDX_INVALID;
  468. hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
  469. if (ret == 0)
  470. ret = __ham_item_prev(dbc,
  471.     lock_type, pgnop);
  472. break;
  473. case DB_FIRST:
  474. case DB_NEXT:
  475. case DB_NEXT_NODUP:
  476. ret = mpf->put(mpf, hcp->page, 0);
  477. hcp->page = NULL;
  478. hcp->indx = NDX_INVALID;
  479. hcp->bucket++;
  480. F_CLR(hcp, H_ISDUP);
  481. hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
  482. if (hcp->bucket > hcp->hdr->max_bucket) {
  483. ret = DB_NOTFOUND;
  484. hcp->pgno = PGNO_INVALID;
  485. goto err;
  486. }
  487. if (ret == 0)
  488. ret = __ham_item_next(dbc,
  489.     lock_type, pgnop);
  490. break;
  491. case DB_GET_BOTH:
  492. case DB_GET_BOTHC:
  493. case DB_GET_BOTH_RANGE:
  494. case DB_NEXT_DUP:
  495. case DB_SET:
  496. case DB_SET_RANGE:
  497. /* Key not found. */
  498. ret = DB_NOTFOUND;
  499. goto err;
  500. case DB_CURRENT:
  501. /*
  502.  * This should only happen if you are doing
  503.  * deletes and reading with concurrent threads
  504.  * and not doing proper locking.  We return
  505.  * the same error code as we would if the
  506.  * cursor were deleted.
  507.  */
  508. ret = DB_KEYEMPTY;
  509. goto err;
  510. default:
  511. DB_ASSERT(0);
  512. }
  513. }
  514. if (get_key == 0)
  515. F_SET(key, DB_DBT_ISSET);
  516. err: if ((t_ret = __ham_release_meta(dbc)) != 0 && ret == 0)
  517. ret = t_ret;
  518. F_CLR(hcp, H_DUPONLY);
  519. F_CLR(hcp, H_NEXT_NODUP);
  520. return (ret);
  521. }
  522. /*
  523.  * __ham_bulk -- Return bulk data from a hash table.
  524.  */
  525. static int
  526. __ham_bulk(dbc, data, flags)
  527. DBC *dbc;
  528. DBT *data;
  529. u_int32_t flags;
  530. {
  531. DB *dbp;
  532. DB_MPOOLFILE *mpf;
  533. HASH_CURSOR *cp;
  534. PAGE *pg;
  535. db_indx_t dup_len, dup_off, dup_tlen, indx, *inp;
  536. db_lockmode_t lock_mode;
  537. db_pgno_t pgno;
  538. int32_t  *endp, key_off, *offp, *saveoff;
  539. u_int32_t key_size, size, space;
  540. u_int8_t *dbuf, *dp, *hk, *np, *tmp;
  541. int is_dup, is_key;
  542. int need_pg, next_key, no_dup, pagesize, ret, t_ret;
  543. ret = 0;
  544. key_off = 0;
  545. dup_len = dup_off = dup_tlen = 0;
  546. size = 0;
  547. dbp = dbc->dbp;
  548. pagesize = dbp->pgsize;
  549. mpf = dbp->mpf;
  550. cp = (HASH_CURSOR *)dbc->internal;
  551. is_key = LF_ISSET(DB_MULTIPLE_KEY) ? 1 : 0;
  552. next_key = is_key && LF_ISSET(DB_OPFLAGS_MASK) != DB_NEXT_DUP;
  553. no_dup = LF_ISSET(DB_OPFLAGS_MASK) == DB_NEXT_NODUP;
  554. dbuf = data->data;
  555. np = dp = dbuf;
  556. /* Keep track of space that is left.  There is an termination entry */
  557. space = data->ulen;
  558. space -= sizeof(*offp);
  559. /* Build the offset/size table from the end up. */
  560. endp = (int32_t *) ((u_int8_t *)dbuf + data->ulen);
  561. endp--;
  562. offp = endp;
  563. key_size = 0;
  564. lock_mode = F_ISSET(dbc, DBC_RMW) ? DB_LOCK_WRITE: DB_LOCK_READ;
  565. next_pg:
  566. need_pg = 1;
  567. indx = cp->indx;
  568. pg = cp->page;
  569. inp = P_INP(dbp, pg);
  570. do {
  571. if (is_key) {
  572. hk = H_PAIRKEY(dbp, pg, indx);
  573. if (HPAGE_PTYPE(hk) == H_OFFPAGE) {
  574. memcpy(&key_size,
  575.     HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
  576. memcpy(&pgno,
  577.     HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
  578. size = key_size;
  579. if (key_size > space)
  580. goto get_key_space;
  581. if ((ret = __bam_bulk_overflow(
  582.     dbc, key_size, pgno, np)) != 0)
  583. return (ret);
  584. space -= key_size;
  585. key_off = (int32_t)(np - dbuf);
  586. np += key_size;
  587. } else {
  588. if (need_pg) {
  589. dp = np;
  590. size = pagesize - HOFFSET(pg);
  591. if (space < size) {
  592. get_key_space:
  593. if (offp == endp) {
  594. data->size =
  595.     ALIGN(size +
  596.     pagesize,
  597.     sizeof(u_int32_t));
  598. return (ENOMEM);
  599. }
  600. goto back_up;
  601. }
  602. memcpy(dp,
  603.    (u_int8_t *)pg + HOFFSET(pg), size);
  604. need_pg = 0;
  605. space -= size;
  606. np += size;
  607. }
  608. key_size = LEN_HKEY(dbp, pg, pagesize, indx);
  609. key_off = (int32_t)(inp[indx] - HOFFSET(pg)
  610.     + dp - dbuf + SSZA(HKEYDATA, data));
  611. }
  612. }
  613. hk = H_PAIRDATA(dbp, pg, indx);
  614. switch (HPAGE_PTYPE(hk)) {
  615. case H_DUPLICATE:
  616. case H_KEYDATA:
  617. if (need_pg) {
  618. dp = np;
  619. size = pagesize - HOFFSET(pg);
  620. if (space < size) {
  621. back_up:
  622. if (indx != 0) {
  623. indx -= 2;
  624. /* XXX
  625.  * It's not clear that this is
  626.  * the right way to fix this,
  627.  * but here goes.
  628.  * If we are backing up onto a
  629.  * duplicate, then we need to
  630.  * position ourselves at the
  631.  * end of the duplicate set.
  632.  * We probably need to make
  633.  * this work for H_OFFDUP too.
  634.  * It might be worth making a
  635.  * dummy cursor and calling
  636.  * __ham_item_prev.
  637.  */
  638. tmp = H_PAIRDATA(dbp, pg, indx);
  639. if (HPAGE_PTYPE(tmp) ==
  640.     H_DUPLICATE) {
  641. dup_off = dup_tlen =
  642.     LEN_HDATA(dbp, pg,
  643.     pagesize, indx + 1);
  644. memcpy(&dup_len,
  645.     HKEYDATA_DATA(tmp),
  646.     sizeof(db_indx_t));
  647. }
  648. goto get_space;
  649. }
  650. /* indx == 0 */
  651. if ((ret = __ham_item_prev(dbc,
  652.     lock_mode, &pgno)) != 0) {
  653. if (ret != DB_NOTFOUND)
  654. return (ret);
  655. if ((ret = mpf->put(mpf,
  656.     cp->page, 0)) != 0)
  657. return (ret);
  658. cp->page = NULL;
  659. if (cp->bucket == 0) {
  660. cp->indx = indx =
  661.     NDX_INVALID;
  662. goto get_space;
  663. }
  664. if ((ret =
  665.     __ham_get_meta(dbc)) != 0)
  666. return (ret);
  667. cp->bucket--;
  668. cp->pgno = BUCKET_TO_PAGE(cp,
  669.     cp->bucket);
  670. cp->indx = NDX_INVALID;
  671. if ((ret = __ham_release_meta(
  672.     dbc)) != 0)
  673. return (ret);
  674. if ((ret = __ham_item_prev(dbc,
  675.     lock_mode, &pgno)) != 0)
  676. return (ret);
  677. }
  678. indx = cp->indx;
  679. get_space:
  680. /*
  681.  * See if we put any data in the buffer.
  682.  */
  683. if (offp >= endp ||
  684.     F_ISSET(dbc, DBC_TRANSIENT)) {
  685. data->size = ALIGN(size +
  686.     data->ulen - space,
  687.     sizeof(u_int32_t));
  688. return (ENOMEM);
  689. }
  690. /*
  691.  * Don't continue;  we're all out
  692.  * of space, even though we're
  693.  * returning success.
  694.  */
  695. next_key = 0;
  696. break;
  697. }
  698. memcpy(dp, (u_int8_t *)pg + HOFFSET(pg), size);
  699. need_pg = 0;
  700. space -= size;
  701. np += size;
  702. }
  703. /*
  704.  * We're about to crack the offset(s) and length(s)
  705.  * out of an H_KEYDATA or H_DUPLICATE item.
  706.  * There are three cases:
  707.  *   1. We were moved into a duplicate set by
  708.  * the standard hash cursor code.  Respect
  709.  * the dup_off and dup_tlen we were given.
  710.  *   2. We stumbled upon a duplicate set while
  711.  * walking the page on our own.  We need to
  712.  * recognize it as a dup and set dup_off and
  713.  * dup_tlen.
  714.  *   3. The current item is not a dup.
  715.  */
  716. if (F_ISSET(cp, H_ISDUP)) {
  717. /* Case 1 */
  718. is_dup = 1;
  719. dup_len = cp->dup_len;
  720. dup_off = cp->dup_off;
  721. dup_tlen = cp->dup_tlen;
  722. } else if (HPAGE_PTYPE(hk) == H_DUPLICATE) {
  723. /* Case 2 */
  724. is_dup = 1;
  725. /*
  726.  * If we run out of memory and bail,
  727.  * make sure the fact we're in a dup set
  728.  * isn't ignored later.
  729.  */
  730. F_SET(cp, H_ISDUP);
  731. dup_off = 0;
  732. memcpy(&dup_len,
  733.     HKEYDATA_DATA(hk), sizeof(db_indx_t));
  734. dup_tlen = LEN_HDATA(dbp, pg, pagesize, indx);
  735. } else
  736. /* Case 3 */
  737. is_dup = dup_len = dup_off = dup_tlen = 0;
  738. do {
  739. space -= (is_key ? 4 : 2) * sizeof(*offp);
  740. size += (is_key ? 4 : 2) * sizeof(*offp);
  741. /*
  742.  * Since space is an unsigned, if we happen
  743.  * to wrap, then this comparison will turn out
  744.  * to be true.  XXX Wouldn't it be better to
  745.  * simply check above that space is greater than
  746.  * the value we're about to subtract???
  747.  */
  748. if (space > data->ulen) {
  749. if (!is_dup || dup_off == 0)
  750. goto back_up;
  751. dup_off -= (db_indx_t)DUP_SIZE(offp[1]);
  752. goto get_space;
  753. }
  754. if (is_key) {
  755. *offp-- = key_off;
  756. *offp-- = key_size;
  757. }
  758. if (is_dup) {
  759. *offp-- = (int32_t)(
  760.     inp[indx + 1] - HOFFSET(pg) +
  761.     dp - dbuf + SSZA(HKEYDATA, data) +
  762.     dup_off + sizeof(db_indx_t));
  763. memcpy(&dup_len,
  764.     HKEYDATA_DATA(hk) + dup_off,
  765.     sizeof(db_indx_t));
  766. dup_off += DUP_SIZE(dup_len);
  767. *offp-- = dup_len;
  768. } else {
  769. *offp-- = (int32_t)(
  770.     inp[indx + 1] - HOFFSET(pg) +
  771.     dp - dbuf + SSZA(HKEYDATA, data));
  772. *offp-- = LEN_HDATA(dbp, pg,
  773.     pagesize, indx);
  774. }
  775. } while (is_dup && dup_off < dup_tlen && no_dup == 0);
  776. F_CLR(cp, H_ISDUP);
  777. break;
  778. case H_OFFDUP:
  779. memcpy(&pgno, HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
  780. space -= 2 * sizeof(*offp);
  781. if (space > data->ulen)
  782. goto back_up;
  783. if (is_key) {
  784. space -= 2 * sizeof(*offp);
  785. if (space > data->ulen)
  786. goto back_up;
  787. *offp-- = key_off;
  788. *offp-- = key_size;
  789. }
  790. saveoff = offp;
  791. if ((ret = __bam_bulk_duplicates(dbc,
  792.     pgno, dbuf, is_key ? offp + 2 : NULL,
  793.     &offp, &np, &space, no_dup)) != 0) {
  794. if (ret == ENOMEM) {
  795. size = space;
  796. if (is_key && saveoff == offp) {
  797. offp += 2;
  798. goto back_up;
  799. }
  800. goto get_space;
  801. }
  802. return (ret);
  803. }
  804. break;
  805. case H_OFFPAGE:
  806. space -= (is_key ? 4 : 2) * sizeof(*offp);
  807. if (space > data->ulen)
  808. goto back_up;
  809. memcpy(&size, HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
  810. memcpy(&pgno, HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
  811. if (size > space)
  812. goto back_up;
  813. if ((ret =
  814.     __bam_bulk_overflow(dbc, size, pgno, np)) != 0)
  815. return (ret);
  816. if (is_key) {
  817. *offp-- = key_off;
  818. *offp-- = key_size;
  819. }
  820. *offp-- = (int32_t)(np - dbuf);
  821. *offp-- = size;
  822. np += size;
  823. space -= size;
  824. break;
  825. }
  826. } while (next_key && (indx += 2) < NUM_ENT(pg));
  827. cp->indx = indx;
  828. cp->dup_len = dup_len;
  829. cp->dup_off = dup_off;
  830. cp->dup_tlen = dup_tlen;
  831. /* If we are off the page then try to the next page. */
  832. if (ret == 0 && next_key && indx >= NUM_ENT(pg)) {
  833. if ((ret = __ham_item_next(dbc, lock_mode, &pgno)) == 0)
  834. goto next_pg;
  835. if (ret != DB_NOTFOUND)
  836. return (ret);
  837. if ((ret = mpf->put(dbc->dbp->mpf, cp->page, 0)) != 0)
  838. return (ret);
  839. cp->page = NULL;
  840. if ((ret = __ham_get_meta(dbc)) != 0)
  841. return (ret);
  842. cp->bucket++;
  843. if (cp->bucket > cp->hdr->max_bucket) {
  844. /*
  845.  * Restore cursor to its previous state.  We're past
  846.  * the last item in the last bucket, so the next
  847.  * DBC->c_get(DB_NEXT) will return DB_NOTFOUND.
  848.  */
  849. cp->bucket--;
  850. ret = DB_NOTFOUND;
  851. } else {
  852. /*
  853.  * Start on the next bucket.
  854.  *
  855.  * Note that if this new bucket happens to be empty,
  856.  * but there's another non-empty bucket after it,
  857.  * we'll return early.  This is a rare case, and we
  858.  * don't guarantee any particular number of keys
  859.  * returned on each call, so just let the next call
  860.  * to bulk get move forward by yet another bucket.
  861.  */
  862. cp->pgno = BUCKET_TO_PAGE(cp, cp->bucket);
  863. cp->indx = NDX_INVALID;
  864. F_CLR(cp, H_ISDUP);
  865. ret = __ham_item_next(dbc, lock_mode, &pgno);
  866. }
  867. if ((t_ret = __ham_release_meta(dbc)) != 0)
  868. return (t_ret);
  869. if (ret == 0)
  870. goto next_pg;
  871. if (ret != DB_NOTFOUND)
  872. return (ret);
  873. }
  874. *offp = (u_int32_t) -1;
  875. return (0);
  876. }
  877. static int
  878. __ham_c_put(dbc, key, data, flags, pgnop)
  879. DBC *dbc;
  880. DBT *key;
  881. DBT *data;
  882. u_int32_t flags;
  883. db_pgno_t *pgnop;
  884. {
  885. DB *dbp;
  886. DB_MPOOLFILE *mpf;
  887. DBT tmp_val, *myval;
  888. HASH_CURSOR *hcp;
  889. u_int32_t nbytes;
  890. int ret, t_ret;
  891. /*
  892.  * The compiler doesn't realize that we only use this when ret is
  893.  * equal to 0 and that if ret is equal to 0, that we must have set
  894.  * myval.  So, we initialize it here to shut the compiler up.
  895.  */
  896. COMPQUIET(myval, NULL);
  897. dbp = dbc->dbp;
  898. mpf = dbp->mpf;
  899. hcp = (HASH_CURSOR *)dbc->internal;
  900. if (F_ISSET(hcp, H_DELETED) &&
  901.     flags != DB_KEYFIRST && flags != DB_KEYLAST)
  902. return (DB_NOTFOUND);
  903. if ((ret = __ham_get_meta(dbc)) != 0)
  904. goto err1;
  905. switch (flags) {
  906. case DB_KEYLAST:
  907. case DB_KEYFIRST:
  908. case DB_NODUPDATA:
  909. nbytes = (ISBIG(hcp, key->size) ? HOFFPAGE_PSIZE :
  910.     HKEYDATA_PSIZE(key->size)) +
  911.     (ISBIG(hcp, data->size) ? HOFFPAGE_PSIZE :
  912.     HKEYDATA_PSIZE(data->size));
  913. if ((ret = __ham_lookup(dbc,
  914.     key, nbytes, DB_LOCK_WRITE, pgnop)) == DB_NOTFOUND) {
  915. ret = 0;
  916. if (hcp->seek_found_page != PGNO_INVALID &&
  917.     hcp->seek_found_page != hcp->pgno) {
  918. if ((ret = mpf->put(mpf, hcp->page, 0)) != 0)
  919. goto err2;
  920. hcp->page = NULL;
  921. hcp->pgno = hcp->seek_found_page;
  922. hcp->indx = NDX_INVALID;
  923. }
  924. if (F_ISSET(data, DB_DBT_PARTIAL) && data->doff != 0) {
  925. /*
  926.  * A partial put, but the key does not exist
  927.  * and we are not beginning the write at 0.
  928.  * We must create a data item padded up to doff
  929.  * and then write the new bytes represented by
  930.  * val.
  931.  */
  932. if ((ret = __ham_init_dbt(dbp->dbenv, &tmp_val,
  933.     data->size + data->doff,
  934.     &dbc->my_rdata.data,
  935.     &dbc->my_rdata.ulen)) == 0) {
  936. memset(tmp_val.data, 0, data->doff);
  937. memcpy((u_int8_t *)tmp_val.data +
  938.     data->doff, data->data, data->size);
  939. myval = &tmp_val;
  940. }
  941. } else
  942. myval = (DBT *)data;
  943. if (ret == 0)
  944. ret = __ham_add_el(dbc, key, myval, H_KEYDATA);
  945. goto done;
  946. }
  947. break;
  948. case DB_BEFORE:
  949. case DB_AFTER:
  950. case DB_CURRENT:
  951. ret = __ham_item(dbc, DB_LOCK_WRITE, pgnop);
  952. break;
  953. }
  954. if (*pgnop == PGNO_INVALID && ret == 0) {
  955. if (flags == DB_CURRENT ||
  956.     ((flags == DB_KEYFIRST ||
  957.     flags == DB_KEYLAST || flags == DB_NODUPDATA) &&
  958.     !(F_ISSET(dbp, DB_AM_DUP) || F_ISSET(key, DB_DBT_DUPOK))))
  959. ret = __ham_overwrite(dbc, data, flags);
  960. else
  961. ret = __ham_add_dup(dbc, data, flags, pgnop);
  962. }
  963. done: if (ret == 0 && F_ISSET(hcp, H_EXPAND)) {
  964. ret = __ham_expand_table(dbc);
  965. F_CLR(hcp, H_EXPAND);
  966. }
  967. if (hcp->page != NULL &&
  968.     (t_ret = mpf->set(mpf, hcp->page, DB_MPOOL_DIRTY)) != 0 && ret == 0)
  969. ret = t_ret;
  970. err2: if ((t_ret = __ham_release_meta(dbc)) != 0 && ret == 0)
  971. ret = t_ret;
  972. err1: return (ret);
  973. }
  974. /********************************* UTILITIES ************************/
  975. /*
  976.  * __ham_expand_table --
  977.  */
  978. static int
  979. __ham_expand_table(dbc)
  980. DBC *dbc;
  981. {
  982. DB *dbp;
  983. DB_LOCK metalock;
  984. DB_LSN lsn;
  985. DB_MPOOLFILE *mpf;
  986. DBMETA *mmeta;
  987. HASH_CURSOR *hcp;
  988. PAGE *h;
  989. db_pgno_t pgno, mpgno;
  990. u_int32_t newalloc, new_bucket, old_bucket;
  991. int dirty_meta, got_meta, logn, new_double, ret;
  992. dbp = dbc->dbp;
  993. mpf = dbp->mpf;
  994. hcp = (HASH_CURSOR *)dbc->internal;
  995. if ((ret = __ham_dirty_meta(dbc)) != 0)
  996. return (ret);
  997. LOCK_INIT(metalock);
  998. mmeta = (DBMETA *) hcp->hdr;
  999. mpgno = mmeta->pgno;
  1000. h = NULL;
  1001. dirty_meta = 0;
  1002. got_meta = 0;
  1003. newalloc = 0;
  1004. /*
  1005.  * If the split point is about to increase, make sure that we
  1006.  * have enough extra pages.  The calculation here is weird.
  1007.  * We'd like to do this after we've upped max_bucket, but it's
  1008.  * too late then because we've logged the meta-data split.  What
  1009.  * we'll do between then and now is increment max bucket and then
  1010.  * see what the log of one greater than that is; here we have to
  1011.  * look at the log of max + 2.  VERY NASTY STUFF.
  1012.  *
  1013.  * We figure out what we need to do, then we log it, then request
  1014.  * the pages from mpool.  We don't want to fail after extending
  1015.  * the file.
  1016.  *
  1017.  * If the page we are about to split into has already been allocated,
  1018.  * then we simply need to get it to get its LSN.  If it hasn't yet
  1019.  * been allocated, then we know it's LSN (0,0).
  1020.  */
  1021. new_bucket = hcp->hdr->max_bucket + 1;
  1022. old_bucket = new_bucket & hcp->hdr->low_mask;
  1023. new_double = hcp->hdr->max_bucket == hcp->hdr->high_mask;
  1024. logn = __db_log2(new_bucket);
  1025. if (!new_double || hcp->hdr->spares[logn + 1] != PGNO_INVALID) {
  1026. /* Page exists; get it so we can get its LSN */
  1027. pgno = BUCKET_TO_PAGE(hcp, new_bucket);
  1028. if ((ret =
  1029.     mpf->get(mpf, &pgno, DB_MPOOL_CREATE, &h)) != 0)
  1030. goto err;
  1031. lsn = h->lsn;
  1032. } else {
  1033. /* Get the master meta-data page to do allocation. */
  1034. if (F_ISSET(dbp, DB_AM_SUBDB)) {
  1035. mpgno = PGNO_BASE_MD;
  1036. if ((ret = __db_lget(dbc,
  1037.    0, mpgno, DB_LOCK_WRITE, 0, &metalock)) != 0)
  1038. goto err;
  1039. if ((ret =
  1040.     mpf->get(mpf, &mpgno, 0, (PAGE **)&mmeta)) != 0)
  1041. goto err;
  1042. got_meta = 1;
  1043. }
  1044. pgno = mmeta->last_pgno + 1;
  1045. ZERO_LSN(lsn);
  1046. newalloc = 1;
  1047. }
  1048. /* Log the meta-data split first. */
  1049. if (DBC_LOGGING(dbc)) {
  1050. /*
  1051.  * We always log the page number of the first page of
  1052.  * the allocation group.  However, the LSN that we log
  1053.  * is either the LSN on the first page (if we did not
  1054.  * do the actual allocation here) or the LSN on the last
  1055.  * page of the unit (if we did do the allocation here).
  1056.  */
  1057. if ((ret = __ham_metagroup_log(dbp, dbc->txn,
  1058.     &lsn, 0, hcp->hdr->max_bucket, mpgno, &mmeta->lsn,
  1059.     hcp->hdr->dbmeta.pgno, &hcp->hdr->dbmeta.lsn,
  1060.     pgno, &lsn, newalloc)) != 0)
  1061. goto err;
  1062. } else
  1063. LSN_NOT_LOGGED(lsn);
  1064. hcp->hdr->dbmeta.lsn = lsn;
  1065. if (new_double && hcp->hdr->spares[logn + 1] == PGNO_INVALID) {
  1066. /*
  1067.  * We need to begin a new doubling and we have not allocated
  1068.  * any pages yet.  Read the last page in and initialize it to
  1069.  * make the allocation contiguous.  The pgno we calculated
  1070.  * above is the first page allocated. The entry in spares is
  1071.  * that page number minus any buckets already allocated (it
  1072.  * simplifies bucket to page transaction).  After we've set
  1073.  * that, we calculate the last pgno.
  1074.  */
  1075. hcp->hdr->spares[logn + 1] = pgno - new_bucket;
  1076. pgno += hcp->hdr->max_bucket;
  1077. mmeta->last_pgno = pgno;
  1078. mmeta->lsn = lsn;
  1079. dirty_meta = DB_MPOOL_DIRTY;
  1080. if ((ret = mpf->get(mpf, &pgno, DB_MPOOL_CREATE, &h)) != 0)
  1081. goto err;
  1082. P_INIT(h, dbp->pgsize,
  1083.     pgno, PGNO_INVALID, PGNO_INVALID, 0, P_HASH);
  1084. }
  1085. /* Write out whatever page we ended up modifying. */
  1086. h->lsn = lsn;
  1087. if ((ret = mpf->put(mpf, h, DB_MPOOL_DIRTY)) != 0)
  1088. goto err;
  1089. h = NULL;
  1090. /*
  1091.  * Update the meta-data page of this hash database.
  1092.  */
  1093. hcp->hdr->max_bucket = new_bucket;
  1094. if (new_double) {
  1095. hcp->hdr->low_mask = hcp->hdr->high_mask;
  1096. hcp->hdr->high_mask = new_bucket | hcp->hdr->low_mask;
  1097. }
  1098. /* Relocate records to the new bucket */
  1099. ret = __ham_split_page(dbc, old_bucket, new_bucket);
  1100. err: if (got_meta)
  1101. (void)mpf->put(mpf, mmeta, dirty_meta);
  1102. if (LOCK_ISSET(metalock))
  1103. (void)__TLPUT(dbc, metalock);
  1104. if (h != NULL)
  1105. (void)mpf->put(mpf, h, 0);
  1106. return (ret);
  1107. }
  1108. /*
  1109.  * PUBLIC: u_int32_t __ham_call_hash __P((DBC *, u_int8_t *, int32_t));
  1110.  */
  1111. u_int32_t
  1112. __ham_call_hash(dbc, k, len)
  1113. DBC *dbc;
  1114. u_int8_t *k;
  1115. int32_t len;
  1116. {
  1117. DB *dbp;
  1118. u_int32_t n, bucket;
  1119. HASH_CURSOR *hcp;
  1120. HASH *hashp;
  1121. dbp = dbc->dbp;
  1122. hcp = (HASH_CURSOR *)dbc->internal;
  1123. hashp = dbp->h_internal;
  1124. n = (u_int32_t)(hashp->h_hash(dbp, k, len));
  1125. bucket = n & hcp->hdr->high_mask;
  1126. if (bucket > hcp->hdr->max_bucket)
  1127. bucket = bucket & hcp->hdr->low_mask;
  1128. return (bucket);
  1129. }
  1130. /*
  1131.  * Check for duplicates, and call __db_ret appropriately.  Release
  1132.  * everything held by the cursor.
  1133.  */
  1134. static int
  1135. __ham_dup_return(dbc, val, flags)
  1136. DBC *dbc;
  1137. DBT *val;
  1138. u_int32_t flags;
  1139. {
  1140. DB *dbp;
  1141. HASH_CURSOR *hcp;
  1142. PAGE *pp;
  1143. DBT *myval, tmp_val;
  1144. db_indx_t ndx;
  1145. db_pgno_t pgno;
  1146. u_int32_t off, tlen;
  1147. u_int8_t *hk, type;
  1148. int cmp, ret;
  1149. db_indx_t len;
  1150. /* Check for duplicate and return the first one. */
  1151. dbp = dbc->dbp;
  1152. hcp = (HASH_CURSOR *)dbc->internal;
  1153. ndx = H_DATAINDEX(hcp->indx);
  1154. type = HPAGE_TYPE(dbp, hcp->page, ndx);
  1155. pp = hcp->page;
  1156. myval = val;
  1157. /*
  1158.  * There are 4 cases:
  1159.  * 1. We are not in duplicate, simply return; the upper layer
  1160.  *    will do the right thing.
  1161.  * 2. We are looking at keys and stumbled onto a duplicate.
  1162.  * 3. We are in the middle of a duplicate set. (ISDUP set)
  1163.  * 4. We need to check for particular data match.
  1164.  */
  1165. /* We should never get here with off-page dups. */
  1166. DB_ASSERT(type != H_OFFDUP);
  1167. /* Case 1 */
  1168. if (type != H_DUPLICATE && flags != DB_GET_BOTH &&
  1169.     flags != DB_GET_BOTHC && flags != DB_GET_BOTH_RANGE)
  1170. return (0);
  1171. /*
  1172.  * Here we check for the case where we just stumbled onto a
  1173.  * duplicate.  In this case, we do initialization and then
  1174.  * let the normal duplicate code handle it. (Case 2)
  1175.  */
  1176. if (!F_ISSET(hcp, H_ISDUP) && type == H_DUPLICATE) {
  1177. F_SET(hcp, H_ISDUP);
  1178. hcp->dup_tlen = LEN_HDATA(dbp, hcp->page,
  1179.     hcp->hdr->dbmeta.pagesize, hcp->indx);
  1180. hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  1181. if (flags == DB_LAST ||
  1182.     flags == DB_PREV || flags == DB_PREV_NODUP) {
  1183. hcp->dup_off = 0;
  1184. do {
  1185. memcpy(&len,
  1186.     HKEYDATA_DATA(hk) + hcp->dup_off,
  1187.     sizeof(db_indx_t));
  1188. hcp->dup_off += DUP_SIZE(len);
  1189. } while (hcp->dup_off < hcp->dup_tlen);
  1190. hcp->dup_off -= DUP_SIZE(len);
  1191. } else {
  1192. memcpy(&len,
  1193.     HKEYDATA_DATA(hk), sizeof(db_indx_t));
  1194. hcp->dup_off = 0;
  1195. }
  1196. hcp->dup_len = len;
  1197. }
  1198. /*
  1199.  * If we are retrieving a specific key/data pair, then we
  1200.  * may need to adjust the cursor before returning data.
  1201.  * Case 4
  1202.  */
  1203. if (flags == DB_GET_BOTH ||
  1204.     flags == DB_GET_BOTHC || flags == DB_GET_BOTH_RANGE) {
  1205. if (F_ISSET(hcp, H_ISDUP)) {
  1206. /*
  1207.  * If we're doing a join, search forward from the
  1208.  * current position, not the beginning of the dup set.
  1209.  */
  1210. if (flags == DB_GET_BOTHC)
  1211. F_SET(hcp, H_CONTINUE);
  1212. __ham_dsearch(dbc, val, &off, &cmp, flags);
  1213. /*
  1214.  * This flag is set nowhere else and is safe to
  1215.  * clear unconditionally.
  1216.  */
  1217. F_CLR(hcp, H_CONTINUE);
  1218. hcp->dup_off = off;
  1219. } else {
  1220. hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  1221. if (((HKEYDATA *)hk)->type == H_OFFPAGE) {
  1222. memcpy(&tlen,
  1223.     HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
  1224. memcpy(&pgno,
  1225.     HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
  1226. if ((ret = __db_moff(dbp, val,
  1227.     pgno, tlen, dbp->dup_compare, &cmp)) != 0)
  1228. return (ret);
  1229. } else {
  1230. /*
  1231.  * We do not zero tmp_val since the comparison
  1232.  * routines may only look at data and size.
  1233.  */
  1234. tmp_val.data = HKEYDATA_DATA(hk);
  1235. tmp_val.size = LEN_HDATA(dbp, hcp->page,
  1236.     dbp->pgsize, hcp->indx);
  1237. cmp = dbp->dup_compare == NULL ?
  1238.     __bam_defcmp(dbp, &tmp_val, val) :
  1239.     dbp->dup_compare(dbp, &tmp_val, val);
  1240. }
  1241. }
  1242. if (cmp != 0)
  1243. return (DB_NOTFOUND);
  1244. }
  1245. /*
  1246.  * If we're doing a bulk get, we don't want to actually return
  1247.  * the data:  __ham_bulk will take care of cracking out the
  1248.  * duplicates appropriately.
  1249.  *
  1250.  * The rest of this function calculates partial offsets and
  1251.  * handles the actual __db_ret, so just return if
  1252.  * DB_MULTIPLE(_KEY) is set.
  1253.  */
  1254. if (F_ISSET(dbc, DBC_MULTIPLE | DBC_MULTIPLE_KEY))
  1255. return (0);
  1256. /*
  1257.  * Now, everything is initialized, grab a duplicate if
  1258.  * necessary.
  1259.  */
  1260. if (F_ISSET(hcp, H_ISDUP)) { /* Case 3 */
  1261. /*
  1262.  * Copy the DBT in case we are retrieving into user
  1263.  * memory and we need the parameters for it.  If the
  1264.  * user requested a partial, then we need to adjust
  1265.  * the user's parameters to get the partial of the
  1266.  * duplicate which is itself a partial.
  1267.  */
  1268. memcpy(&tmp_val, val, sizeof(*val));
  1269. if (F_ISSET(&tmp_val, DB_DBT_PARTIAL)) {
  1270. /*
  1271.  * Take the user's length unless it would go
  1272.  * beyond the end of the duplicate.
  1273.  */
  1274. if (tmp_val.doff + hcp->dup_off > hcp->dup_len)
  1275. tmp_val.dlen = 0;
  1276. else if (tmp_val.dlen + tmp_val.doff >
  1277.     hcp->dup_len)
  1278. tmp_val.dlen =
  1279.     hcp->dup_len - tmp_val.doff;
  1280. /*
  1281.  * Calculate the new offset.
  1282.  */
  1283. tmp_val.doff += hcp->dup_off;
  1284. } else {
  1285. F_SET(&tmp_val, DB_DBT_PARTIAL);
  1286. tmp_val.dlen = hcp->dup_len;
  1287. tmp_val.doff = hcp->dup_off + sizeof(db_indx_t);
  1288. }
  1289. myval = &tmp_val;
  1290. }
  1291. /*
  1292.  * Finally, if we had a duplicate, pp, ndx, and myval should be
  1293.  * set appropriately.
  1294.  */
  1295. if ((ret = __db_ret(dbp, pp, ndx, myval, &dbc->rdata->data,
  1296.     &dbc->rdata->ulen)) != 0)
  1297. return (ret);
  1298. /*
  1299.  * In case we sent a temporary off to db_ret, set the real
  1300.  * return values.
  1301.  */
  1302. val->data = myval->data;
  1303. val->size = myval->size;
  1304. F_SET(val, DB_DBT_ISSET);
  1305. return (0);
  1306. }
  1307. static int
  1308. __ham_overwrite(dbc, nval, flags)
  1309. DBC *dbc;
  1310. DBT *nval;
  1311. u_int32_t flags;
  1312. {
  1313. DB *dbp;
  1314. DB_ENV *dbenv;
  1315. HASH_CURSOR *hcp;
  1316. DBT *myval, tmp_val, tmp_val2;
  1317. void *newrec;
  1318. u_int8_t *hk, *p;
  1319. u_int32_t len, nondup_size;
  1320. db_indx_t newsize;
  1321. int ret;
  1322. dbp = dbc->dbp;
  1323. dbenv = dbp->dbenv;
  1324. hcp = (HASH_CURSOR *)dbc->internal;
  1325. if (F_ISSET(hcp, H_ISDUP)) {
  1326. /*
  1327.  * This is an overwrite of a duplicate. We should never
  1328.  * be off-page at this point.
  1329.  */
  1330. DB_ASSERT(hcp->opd == NULL);
  1331. /* On page dups */
  1332. if (F_ISSET(nval, DB_DBT_PARTIAL)) {
  1333. /*
  1334.  * We're going to have to get the current item, then
  1335.  * construct the record, do any padding and do a
  1336.  * replace.
  1337.  */
  1338. memset(&tmp_val, 0, sizeof(tmp_val));
  1339. if ((ret =
  1340.     __ham_dup_return(dbc, &tmp_val, DB_CURRENT)) != 0)
  1341. return (ret);
  1342. /* Figure out new size. */
  1343. nondup_size = tmp_val.size;
  1344. newsize = nondup_size;
  1345. /*
  1346.  * Three cases:
  1347.  * 1. strictly append (may need to allocate space
  1348.  * for pad bytes; really gross).
  1349.  * 2. overwrite some and append.
  1350.  * 3. strictly overwrite.
  1351.  */
  1352. if (nval->doff > nondup_size)
  1353. newsize +=
  1354.     (nval->doff - nondup_size + nval->size);
  1355. else if (nval->doff + nval->dlen > nondup_size)
  1356. newsize += nval->size -
  1357.     (nondup_size - nval->doff);
  1358. else
  1359. newsize += nval->size - nval->dlen;
  1360. /*
  1361.  * Make sure that the new size doesn't put us over
  1362.  * the onpage duplicate size in which case we need
  1363.  * to convert to off-page duplicates.
  1364.  */
  1365. if (ISBIG(hcp, hcp->dup_tlen - nondup_size + newsize)) {
  1366. if ((ret = __ham_dup_convert(dbc)) != 0)
  1367. return (ret);
  1368. return (hcp->opd->c_am_put(hcp->opd,
  1369.     NULL, nval, flags, NULL));
  1370. }
  1371. if ((ret = __os_malloc(dbp->dbenv,
  1372.     DUP_SIZE(newsize), &newrec)) != 0)
  1373. return (ret);
  1374. memset(&tmp_val2, 0, sizeof(tmp_val2));
  1375. F_SET(&tmp_val2, DB_DBT_PARTIAL);
  1376. /* Construct the record. */
  1377. p = newrec;
  1378. /* Initial size. */
  1379. memcpy(p, &newsize, sizeof(db_indx_t));
  1380. p += sizeof(db_indx_t);
  1381. /* First part of original record. */
  1382. len = nval->doff > tmp_val.size
  1383.     ? tmp_val.size : nval->doff;
  1384. memcpy(p, tmp_val.data, len);
  1385. p += len;
  1386. if (nval->doff > tmp_val.size) {
  1387. /* Padding */
  1388. memset(p, 0, nval->doff - tmp_val.size);
  1389. p += nval->doff - tmp_val.size;
  1390. }
  1391. /* New bytes */
  1392. memcpy(p, nval->data, nval->size);
  1393. p += nval->size;
  1394. /* End of original record (if there is any) */
  1395. if (nval->doff + nval->dlen < tmp_val.size) {
  1396. len = tmp_val.size - nval->doff - nval->dlen;
  1397. memcpy(p, (u_int8_t *)tmp_val.data +
  1398.     nval->doff + nval->dlen, len);
  1399. p += len;
  1400. }
  1401. /* Final size. */
  1402. memcpy(p, &newsize, sizeof(db_indx_t));
  1403. /*
  1404.  * Make sure that the caller isn't corrupting
  1405.  * the sort order.
  1406.  */
  1407. if (dbp->dup_compare != NULL) {
  1408. tmp_val2.data =
  1409.     (u_int8_t *)newrec + sizeof(db_indx_t);
  1410. tmp_val2.size = newsize;
  1411. if (dbp->dup_compare(
  1412.     dbp, &tmp_val, &tmp_val2) != 0) {
  1413. (void)__os_free(dbenv, newrec);
  1414. return (__db_duperr(dbp, flags));
  1415. }
  1416. }
  1417. tmp_val2.data = newrec;
  1418. tmp_val2.size = DUP_SIZE(newsize);
  1419. tmp_val2.doff = hcp->dup_off;
  1420. tmp_val2.dlen = DUP_SIZE(hcp->dup_len);
  1421. ret = __ham_replpair(dbc, &tmp_val2, 0);
  1422. (void)__os_free(dbenv, newrec);
  1423. /* Update cursor */
  1424. if (ret != 0)
  1425. return (ret);
  1426. if (newsize > nondup_size)
  1427. hcp->dup_tlen += (newsize - nondup_size);
  1428. else
  1429. hcp->dup_tlen -= (nondup_size - newsize);
  1430. hcp->dup_len = DUP_SIZE(newsize);
  1431. return (0);
  1432. } else {
  1433. /* Check whether we need to convert to off page. */
  1434. if (ISBIG(hcp,
  1435.     hcp->dup_tlen - hcp->dup_len + nval->size)) {
  1436. if ((ret = __ham_dup_convert(dbc)) != 0)
  1437. return (ret);
  1438. return (hcp->opd->c_am_put(hcp->opd,
  1439.     NULL, nval, flags, NULL));
  1440. }
  1441. /* Make sure we maintain sort order. */
  1442. if (dbp->dup_compare != NULL) {
  1443. tmp_val2.data =
  1444.     HKEYDATA_DATA(H_PAIRDATA(dbp, hcp->page,
  1445.     hcp->indx)) + hcp->dup_off +
  1446.     sizeof(db_indx_t);
  1447. tmp_val2.size = hcp->dup_len;
  1448. if (dbp->dup_compare(dbp, nval, &tmp_val2) != 0)
  1449. return (EINVAL);
  1450. }
  1451. /* Overwriting a complete duplicate. */
  1452. if ((ret =
  1453.     __ham_make_dup(dbp->dbenv, nval, &tmp_val,
  1454.     &dbc->my_rdata.data, &dbc->my_rdata.ulen)) != 0)
  1455. return (ret);
  1456. /* Now fix what we are replacing. */
  1457. tmp_val.doff = hcp->dup_off;
  1458. tmp_val.dlen = DUP_SIZE(hcp->dup_len);
  1459. /* Update cursor */
  1460. if (nval->size > hcp->dup_len)
  1461. hcp->dup_tlen += (nval->size - hcp->dup_len);
  1462. else
  1463. hcp->dup_tlen -= (hcp->dup_len - nval->size);
  1464. hcp->dup_len = (db_indx_t)DUP_SIZE(nval->size);
  1465. }
  1466. myval = &tmp_val;
  1467. } else if (!F_ISSET(nval, DB_DBT_PARTIAL)) {
  1468. /* Put/overwrite */
  1469. memcpy(&tmp_val, nval, sizeof(*nval));
  1470. F_SET(&tmp_val, DB_DBT_PARTIAL);
  1471. tmp_val.doff = 0;
  1472. hk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  1473. if (HPAGE_PTYPE(hk) == H_OFFPAGE)
  1474. memcpy(&tmp_val.dlen,
  1475.     HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
  1476. else
  1477. tmp_val.dlen = LEN_HDATA(dbp, hcp->page,
  1478.     hcp->hdr->dbmeta.pagesize, hcp->indx);
  1479. myval = &tmp_val;
  1480. } else
  1481. /* Regular partial put */
  1482. myval = nval;
  1483. return (__ham_replpair(dbc, myval, 0));
  1484. }
  1485. /*
  1486.  * Given a key and a cursor, sets the cursor to the page/ndx on which
  1487.  * the key resides.  If the key is found, the cursor H_OK flag is set
  1488.  * and the pagep, bndx, pgno (dpagep, dndx, dpgno) fields are set.
  1489.  * If the key is not found, the H_OK flag is not set.  If the sought
  1490.  * field is non-0, the pagep, bndx, pgno (dpagep, dndx, dpgno) fields
  1491.  * are set indicating where an add might take place.  If it is 0,
  1492.  * non of the cursor pointer field are valid.
  1493.  */
  1494. static int
  1495. __ham_lookup(dbc, key, sought, mode, pgnop)
  1496. DBC *dbc;
  1497. const DBT *key;
  1498. u_int32_t sought;
  1499. db_lockmode_t mode;
  1500. db_pgno_t *pgnop;
  1501. {
  1502. DB *dbp;
  1503. HASH_CURSOR *hcp;
  1504. db_pgno_t pgno;
  1505. u_int32_t tlen;
  1506. int match, ret;
  1507. u_int8_t *hk, *dk;
  1508. dbp = dbc->dbp;
  1509. hcp = (HASH_CURSOR *)dbc->internal;
  1510. /*
  1511.  * Set up cursor so that we're looking for space to add an item
  1512.  * as we cycle through the pages looking for the key.
  1513.  */
  1514. if ((ret = __ham_item_reset(dbc)) != 0)
  1515. return (ret);
  1516. hcp->seek_size = sought;
  1517. hcp->bucket = __ham_call_hash(dbc, (u_int8_t *)key->data, key->size);
  1518. hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
  1519. for (;;) {
  1520. *pgnop = PGNO_INVALID;
  1521. if ((ret = __ham_item_next(dbc, mode, pgnop)) != 0)
  1522. return (ret);
  1523. if (F_ISSET(hcp, H_NOMORE))
  1524. break;
  1525. hk = H_PAIRKEY(dbp, hcp->page, hcp->indx);
  1526. switch (HPAGE_PTYPE(hk)) {
  1527. case H_OFFPAGE:
  1528. memcpy(&tlen, HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
  1529. if (tlen == key->size) {
  1530. memcpy(&pgno,
  1531.     HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
  1532. if ((ret = __db_moff(dbp,
  1533.     key, pgno, tlen, NULL, &match)) != 0)
  1534. return (ret);
  1535. if (match == 0)
  1536. goto found_key;
  1537. }
  1538. break;
  1539. case H_KEYDATA:
  1540. if (key->size ==
  1541.     LEN_HKEY(dbp, hcp->page, dbp->pgsize, hcp->indx) &&
  1542.     memcmp(key->data,
  1543.     HKEYDATA_DATA(hk), key->size) == 0) {
  1544. /* Found the key, check for data type. */
  1545. found_key: F_SET(hcp, H_OK);
  1546. dk = H_PAIRDATA(dbp, hcp->page, hcp->indx);
  1547. if (HPAGE_PTYPE(dk) == H_OFFDUP)
  1548. memcpy(pgnop, HOFFDUP_PGNO(dk),
  1549.     sizeof(db_pgno_t));
  1550. return (0);
  1551. }
  1552. break;
  1553. case H_DUPLICATE:
  1554. case H_OFFDUP:
  1555. /*
  1556.  * These are errors because keys are never
  1557.  * duplicated, only data items are.
  1558.  */
  1559. return (__db_pgfmt(dbp->dbenv, PGNO(hcp->page)));
  1560. }
  1561. }
  1562. /*
  1563.  * Item was not found.
  1564.  */
  1565. if (sought != 0)
  1566. return (ret);
  1567. return (ret);
  1568. }
  1569. /*
  1570.  * __ham_init_dbt --
  1571.  * Initialize a dbt using some possibly already allocated storage
  1572.  * for items.
  1573.  *
  1574.  * PUBLIC: int __ham_init_dbt __P((DB_ENV *,
  1575.  * PUBLIC:     DBT *, u_int32_t, void **, u_int32_t *));
  1576.  */
  1577. int
  1578. __ham_init_dbt(dbenv, dbt, size, bufp, sizep)
  1579. DB_ENV *dbenv;
  1580. DBT *dbt;
  1581. u_int32_t size;
  1582. void **bufp;
  1583. u_int32_t *sizep;
  1584. {
  1585. int ret;
  1586. memset(dbt, 0, sizeof(*dbt));
  1587. if (*sizep < size) {
  1588. if ((ret = __os_realloc(dbenv, size, bufp)) != 0) {
  1589. *sizep = 0;
  1590. return (ret);
  1591. }
  1592. *sizep = size;
  1593. }
  1594. dbt->data = *bufp;
  1595. dbt->size = size;
  1596. return (0);
  1597. }
  1598. /*
  1599.  * Adjust the cursor after an insert or delete.  The cursor passed is
  1600.  * the one that was operated upon; we just need to check any of the
  1601.  * others.
  1602.  *
  1603.  * len indicates the length of the item added/deleted
  1604.  * add indicates if the item indicated by the cursor has just been
  1605.  * added (add == 1) or deleted (add == 0).
  1606.  * dup indicates if the addition occurred into a duplicate set.
  1607.  *
  1608.  * PUBLIC: int __ham_c_update
  1609.  * PUBLIC:    __P((DBC *, u_int32_t, int, int));
  1610.  */
  1611. int
  1612. __ham_c_update(dbc, len, add, is_dup)
  1613. DBC *dbc;
  1614. u_int32_t len;
  1615. int add, is_dup;
  1616. {
  1617. DB *dbp, *ldbp;
  1618. DBC *cp;
  1619. DB_ENV *dbenv;
  1620. DB_LSN lsn;
  1621. DB_TXN *my_txn;
  1622. HASH_CURSOR *hcp, *lcp;
  1623. int found, ret;
  1624. u_int32_t order;
  1625. dbp = dbc->dbp;
  1626. dbenv = dbp->dbenv;
  1627. hcp = (HASH_CURSOR *)dbc->internal;
  1628. /*
  1629.  * Adjustment will only be logged if this is a subtransaction.
  1630.  * Only subtransactions can abort and effect their parent
  1631.  * transactions cursors.
  1632.  */
  1633. my_txn = IS_SUBTRANSACTION(dbc->txn) ? dbc->txn : NULL;
  1634. found = 0;
  1635. MUTEX_THREAD_LOCK(dbenv, dbenv->dblist_mutexp);
  1636. /*
  1637.  * Calculate the order of this deleted record.
  1638.  * This will be one greater than any cursor that is pointing
  1639.  * at this record and already marked as deleted.
  1640.  */
  1641. order = 0;
  1642. if (!add) {
  1643. order = 1;
  1644. for (ldbp = __dblist_get(dbenv, dbp->adj_fileid);
  1645.     ldbp != NULL && ldbp->adj_fileid == dbp->adj_fileid;
  1646.     ldbp = LIST_NEXT(ldbp, dblistlinks)) {
  1647. MUTEX_THREAD_LOCK(dbenv, dbp->mutexp);
  1648. for (cp = TAILQ_FIRST(&ldbp->active_queue); cp != NULL;
  1649.     cp = TAILQ_NEXT(cp, links)) {
  1650. if (cp == dbc || cp->dbtype != DB_HASH)
  1651. continue;
  1652. lcp = (HASH_CURSOR *)cp->internal;
  1653. if (F_ISSET(lcp, H_DELETED) &&
  1654.     hcp->pgno == lcp->pgno &&
  1655.     hcp->indx == lcp->indx &&
  1656.     order <= lcp->order &&
  1657.     (!is_dup || hcp->dup_off == lcp->dup_off))
  1658. order = lcp->order + 1;
  1659. }
  1660. MUTEX_THREAD_UNLOCK(dbenv, dbp->mutexp);
  1661. }
  1662. hcp->order = order;
  1663. }
  1664. for (ldbp = __dblist_get(dbenv, dbp->adj_fileid);
  1665.     ldbp != NULL && ldbp->adj_fileid == dbp->adj_fileid;
  1666.     ldbp = LIST_NEXT(ldbp, dblistlinks)) {
  1667. MUTEX_THREAD_LOCK(dbenv, dbp->mutexp);
  1668. for (cp = TAILQ_FIRST(&ldbp->active_queue); cp != NULL;
  1669.     cp = TAILQ_NEXT(cp, links)) {
  1670. if (cp == dbc || cp->dbtype != DB_HASH)
  1671. continue;
  1672. lcp = (HASH_CURSOR *)cp->internal;
  1673. if (lcp->pgno != hcp->pgno || lcp->indx == NDX_INVALID)
  1674. continue;
  1675. if (my_txn != NULL && cp->txn != my_txn)
  1676. found = 1;
  1677. if (!is_dup) {
  1678. if (add) {
  1679. /*
  1680.  * This routine is not called to add
  1681.  * non-dup records which are always put
  1682.  * at the end.  It is only called from
  1683.  * recovery in this case and the
  1684.  * cursor will be marked deleted.
  1685.  * We are "undeleting" so unmark all
  1686.  * cursors with the same order.
  1687.  */
  1688. if (lcp->indx == hcp->indx &&
  1689.     F_ISSET(lcp, H_DELETED)) {
  1690. if (lcp->order == hcp->order)
  1691. F_CLR(lcp, H_DELETED);
  1692. else if (lcp->order >
  1693.     hcp->order) {
  1694. /*
  1695.  * If we've moved this cursor's
  1696.  * index, split its order
  1697.  * number--i.e., decrement it by
  1698.  * enough so that the lowest
  1699.  * cursor moved has order 1.
  1700.  * cp_arg->order is the split
  1701.  * point, so decrement by one
  1702.  * less than that.
  1703.  */
  1704. lcp->order -=
  1705.     (hcp->order - 1);
  1706. lcp->indx += 2;
  1707. }
  1708. } else if (lcp->indx >= hcp->indx)
  1709. lcp->indx += 2;
  1710. } else {
  1711. if (lcp->indx > hcp->indx) {
  1712. lcp->indx -= 2;
  1713. if (lcp->indx == hcp->indx &&
  1714.     F_ISSET(lcp, H_DELETED))
  1715. lcp->order += order;
  1716. } else if (lcp->indx == hcp->indx &&
  1717.     !F_ISSET(lcp, H_DELETED)) {
  1718. F_SET(lcp, H_DELETED);
  1719. F_CLR(lcp, H_ISDUP);
  1720. lcp->order = order;
  1721. }
  1722. }
  1723. } else if (lcp->indx == hcp->indx) {
  1724. /*
  1725.  * Handle duplicates.  This routine is
  1726.  * only called for on page dups.
  1727.  * Off page dups are handled by btree/rtree
  1728.  * code.
  1729.  */
  1730. if (add) {
  1731. lcp->dup_tlen += len;
  1732. if (lcp->dup_off == hcp->dup_off &&
  1733.     F_ISSET(hcp, H_DELETED) &&
  1734.     F_ISSET(lcp, H_DELETED)) {
  1735. /* Abort of a delete. */
  1736. if (lcp->order == hcp->order)
  1737. F_CLR(lcp, H_DELETED);
  1738. else if (lcp->order >
  1739.     hcp->order) {
  1740. lcp->order -=
  1741.     (hcp->order -1);
  1742. lcp->dup_off += len;
  1743. }
  1744. } else if (lcp->dup_off >= hcp->dup_off)
  1745. lcp->dup_off += len;
  1746. } else {
  1747. lcp->dup_tlen -= len;
  1748. if (lcp->dup_off > hcp->dup_off) {
  1749. lcp->dup_off -= len;
  1750. if (lcp->dup_off ==
  1751.     hcp->dup_off &&
  1752.     F_ISSET(lcp, H_DELETED))
  1753. lcp->order += order;
  1754. } else if (lcp->dup_off ==
  1755.     hcp->dup_off &&
  1756.     !F_ISSET(lcp, H_DELETED)) {
  1757. F_SET(lcp, H_DELETED);
  1758. lcp->order = order;
  1759. }
  1760. }
  1761. }
  1762. }
  1763. MUTEX_THREAD_UNLOCK(dbenv, dbp->mutexp);
  1764. }
  1765. MUTEX_THREAD_UNLOCK(dbenv, dbenv->dblist_mutexp);
  1766. if (found != 0 && DBC_LOGGING(dbc)) {
  1767. if ((ret = __ham_curadj_log(dbp, my_txn, &lsn, 0, hcp->pgno,
  1768.     hcp->indx, len, hcp->dup_off, add, is_dup, order)) != 0)
  1769. return (ret);
  1770. }
  1771. return (0);
  1772. }
  1773. /*
  1774.  * __ham_get_clist --
  1775.  *
  1776.  * Get a list of cursors either on a particular bucket or on a particular
  1777.  * page and index combination.  The former is so that we can update
  1778.  * cursors on a split.  The latter is so we can update cursors when we
  1779.  * move items off page.
  1780.  *
  1781.  * PUBLIC: int __ham_get_clist __P((DB *, db_pgno_t, u_int32_t, DBC ***));
  1782.  */
  1783. int
  1784. __ham_get_clist(dbp, pgno, indx, listp)
  1785. DB *dbp;
  1786. db_pgno_t pgno;
  1787. u_int32_t indx;
  1788. DBC ***listp;
  1789. {
  1790. DB *ldbp;
  1791. DBC *cp;
  1792. DB_ENV *dbenv;
  1793. int nalloc, nused, ret;
  1794. /*
  1795.  * Assume that finding anything is the exception, so optimize for
  1796.  * the case where there aren't any.
  1797.  */
  1798. nalloc = nused = 0;
  1799. *listp = NULL;
  1800. dbenv = dbp->dbenv;
  1801. MUTEX_THREAD_LOCK(dbenv, dbenv->dblist_mutexp);
  1802. for (ldbp = __dblist_get(dbenv, dbp->adj_fileid);
  1803.     ldbp != NULL && ldbp->adj_fileid == dbp->adj_fileid;
  1804.     ldbp = LIST_NEXT(ldbp, dblistlinks)) {
  1805. MUTEX_THREAD_LOCK(dbenv, dbp->mutexp);
  1806. for (cp = TAILQ_FIRST(&ldbp->active_queue); cp != NULL;
  1807.     cp = TAILQ_NEXT(cp, links))
  1808. /*
  1809.  * We match if cp->pgno matches the specified
  1810.  * pgno, and if either the cp->indx matches
  1811.  * or we weren't given an index.
  1812.  */
  1813. if (cp->internal->pgno == pgno &&
  1814.     (indx == NDX_INVALID ||
  1815.     cp->internal->indx == indx)) {
  1816. if (nused >= nalloc) {
  1817. nalloc += 10;
  1818. if ((ret = __os_realloc(dbp->dbenv,
  1819.     nalloc * sizeof(HASH_CURSOR *),
  1820.     listp)) != 0)
  1821. goto err;
  1822. }
  1823. (*listp)[nused++] = cp;
  1824. }
  1825. MUTEX_THREAD_UNLOCK(dbp->dbenv, dbp->mutexp);
  1826. }
  1827. MUTEX_THREAD_UNLOCK(dbenv, dbenv->dblist_mutexp);
  1828. if (listp != NULL) {
  1829. if (nused >= nalloc) {
  1830. nalloc++;
  1831. if ((ret = __os_realloc(dbp->dbenv,
  1832.     nalloc * sizeof(HASH_CURSOR *), listp)) != 0)
  1833. return (ret);
  1834. }
  1835. (*listp)[nused] = NULL;
  1836. }
  1837. return (0);
  1838. err:
  1839. MUTEX_THREAD_UNLOCK(dbp->dbenv, dbp->mutexp);
  1840. MUTEX_THREAD_UNLOCK(dbenv, dbenv->dblist_mutexp);
  1841. return (ret);
  1842. }
  1843. static int
  1844. __ham_c_writelock(dbc)
  1845. DBC *dbc;
  1846. {
  1847. DB_ENV *dbenv;
  1848. DB_LOCK tmp_lock;
  1849. HASH_CURSOR *hcp;
  1850. int ret;
  1851. /*
  1852.  * All we need do is acquire the lock and let the off-page
  1853.  * dup tree do its thing.
  1854.  */
  1855. if (!STD_LOCKING(dbc))
  1856. return (0);
  1857. hcp = (HASH_CURSOR *)dbc->internal;
  1858. if ((!LOCK_ISSET(hcp->lock) || hcp->lock_mode == DB_LOCK_READ)) {
  1859. tmp_lock = hcp->lock;
  1860. if ((ret = __ham_lock_bucket(dbc, DB_LOCK_WRITE)) != 0)
  1861. return (ret);
  1862. dbenv = dbc->dbp->dbenv;
  1863. if (LOCK_ISSET(tmp_lock) &&
  1864.     (ret = dbenv->lock_put(dbenv, &tmp_lock)) != 0)
  1865. return (ret);
  1866. }
  1867. return (0);
  1868. }