bt_put.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322
  1. /*-
  2. * Copyright (c) 1990, 1993, 1994
  3. * The Regents of the University of California. All rights reserved.
  4. *
  5. * This code is derived from software contributed to Berkeley by
  6. * Mike Olson.
  7. *
  8. * Redistribution and use in source and binary forms, with or without
  9. * modification, are permitted provided that the following conditions
  10. * are met:
  11. * 1. Redistributions of source code must retain the above copyright
  12. * notice, this list of conditions and the following disclaimer.
  13. * 2. Redistributions in binary form must reproduce the above copyright
  14. * notice, this list of conditions and the following disclaimer in the
  15. * documentation and/or other materials provided with the distribution.
  16. * 3. All advertising materials mentioning features or use of this software
  17. * must display the following acknowledgement:
  18. * This product includes software developed by the University of
  19. * California, Berkeley and its contributors.
  20. * 4. Neither the name of the University nor the names of its contributors
  21. * may be used to endorse or promote products derived from this software
  22. * without specific prior written permission.
  23. *
  24. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34. * SUCH DAMAGE.
  35. */
  36. #if defined(LIBC_SCCS) && !defined(lint)
  37. static char sccsid[] = "@(#)bt_put.c 8.8 (Berkeley) 7/26/94";
  38. #endif /* LIBC_SCCS and not lint */
  39. #include <sys/types.h>
  40. #include <errno.h>
  41. #include <stdio.h>
  42. #include <stdlib.h>
  43. #include <string.h>
  44. #include "../include/db.h"
  45. #include "btree.h"
  46. static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *));
  47. /*
  48. * __BT_PUT -- Add a btree item to the tree.
  49. *
  50. * Parameters:
  51. * dbp: pointer to access method
  52. * key: key
  53. * data: data
  54. * flag: R_NOOVERWRITE
  55. *
  56. * Returns:
  57. * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
  58. * tree and R_NOOVERWRITE specified.
  59. */
  60. int
  61. __bt_put(dbp, key, data, flags)
  62. const DB *dbp;
  63. DBT *key;
  64. const DBT *data;
  65. u_int flags;
  66. {
  67. BTREE *t;
  68. DBT tkey, tdata;
  69. EPG *e = 0;
  70. PAGE *h;
  71. indx_t index, nxtindex;
  72. pgno_t pg;
  73. u_int32_t nbytes;
  74. int dflags, exact, status;
  75. char *dest, db[NOVFLSIZE], kb[NOVFLSIZE];
  76. t = dbp->internal;
  77. /* Toss any page pinned across calls. */
  78. if (t->bt_pinned != NULL) {
  79. mpool_put(t->bt_mp, t->bt_pinned, 0);
  80. t->bt_pinned = NULL;
  81. }
  82. /* Check for change to a read-only tree. */
  83. if (F_ISSET(t, B_RDONLY)) {
  84. errno = EPERM;
  85. return (RET_ERROR);
  86. }
  87. switch (flags) {
  88. case 0:
  89. case R_NOOVERWRITE:
  90. break;
  91. case R_CURSOR:
  92. /*
  93. * If flags is R_CURSOR, put the cursor. Must already
  94. * have started a scan and not have already deleted it.
  95. */
  96. if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
  97. !F_ISSET(&t->bt_cursor,
  98. CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
  99. break;
  100. /* FALLTHROUGH */
  101. default:
  102. errno = EINVAL;
  103. return (RET_ERROR);
  104. }
  105. /*
  106. * If the key/data pair won't fit on a page, store it on overflow
  107. * pages. Only put the key on the overflow page if the pair are
  108. * still too big after moving the data to an overflow page.
  109. *
  110. * XXX
  111. * If the insert fails later on, the overflow pages aren't recovered.
  112. */
  113. dflags = 0;
  114. if (key->size + data->size > t->bt_ovflsize) {
  115. if (key->size > t->bt_ovflsize) {
  116. storekey: if (__ovfl_put(t, key, &pg) == RET_ERROR)
  117. return (RET_ERROR);
  118. tkey.data = kb;
  119. tkey.size = NOVFLSIZE;
  120. memmove(kb, &pg, sizeof(pgno_t));
  121. memmove(kb + sizeof(pgno_t),
  122. &key->size, sizeof(u_int32_t));
  123. dflags |= P_BIGKEY;
  124. key = &tkey;
  125. }
  126. if (key->size + data->size > t->bt_ovflsize) {
  127. if (__ovfl_put(t, data, &pg) == RET_ERROR)
  128. return (RET_ERROR);
  129. tdata.data = db;
  130. tdata.size = NOVFLSIZE;
  131. memmove(db, &pg, sizeof(pgno_t));
  132. memmove(db + sizeof(pgno_t),
  133. &data->size, sizeof(u_int32_t));
  134. dflags |= P_BIGDATA;
  135. data = &tdata;
  136. }
  137. if (key->size + data->size > t->bt_ovflsize)
  138. goto storekey;
  139. }
  140. /* Replace the cursor. */
  141. if (flags == R_CURSOR) {
  142. if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL)
  143. return (RET_ERROR);
  144. index = t->bt_cursor.pg.index;
  145. goto delete;
  146. }
  147. /*
  148. * Find the key to delete, or, the location at which to insert.
  149. * Bt_fast and __bt_search both pin the returned page.
  150. */
  151. if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL)
  152. if ((e = __bt_search(t, key, &exact)) == NULL)
  153. return (RET_ERROR);
  154. h = e->page;
  155. index = e->index;
  156. /*
  157. * Add the key/data pair to the tree. If an identical key is already
  158. * in the tree, and R_NOOVERWRITE is set, an error is returned. If
  159. * R_NOOVERWRITE is not set, the key is either added (if duplicates are
  160. * permitted) or an error is returned.
  161. */
  162. switch (flags) {
  163. case R_NOOVERWRITE:
  164. if (!exact)
  165. break;
  166. mpool_put(t->bt_mp, h, 0);
  167. return (RET_SPECIAL);
  168. default:
  169. if (!exact || !F_ISSET(t, B_NODUPS))
  170. break;
  171. /*
  172. * !!!
  173. * Note, the delete may empty the page, so we need to put a
  174. * new entry into the page immediately.
  175. */
  176. delete: if (__bt_dleaf(t, key, h, index) == RET_ERROR) {
  177. mpool_put(t->bt_mp, h, 0);
  178. return (RET_ERROR);
  179. }
  180. break;
  181. }
  182. /*
  183. * If not enough room, or the user has put a ceiling on the number of
  184. * keys permitted in the page, split the page. The split code will
  185. * insert the key and data and unpin the current page. If inserting
  186. * into the offset array, shift the pointers up.
  187. */
  188. nbytes = NBLEAFDBT(key->size, data->size);
  189. if ((u_int32_t) (h->upper - h->lower) < nbytes + sizeof(indx_t)) {
  190. if ((status = __bt_split(t, h, key,
  191. data, dflags, nbytes, index)) != RET_SUCCESS)
  192. return (status);
  193. goto success;
  194. }
  195. if (index < (nxtindex = NEXTINDEX(h)))
  196. memmove(h->linp + index + 1, h->linp + index,
  197. (nxtindex - index) * sizeof(indx_t));
  198. h->lower += sizeof(indx_t);
  199. h->linp[index] = h->upper -= nbytes;
  200. dest = (char *)h + h->upper;
  201. WR_BLEAF(dest, key, data, dflags);
  202. /* If the cursor is on this page, adjust it as necessary. */
  203. if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
  204. !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
  205. t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= index)
  206. ++t->bt_cursor.pg.index;
  207. if (t->bt_order == NOT) {
  208. if (h->nextpg == P_INVALID) {
  209. if (index == NEXTINDEX(h) - 1) {
  210. t->bt_order = FORWARD;
  211. t->bt_last.index = index;
  212. t->bt_last.pgno = h->pgno;
  213. }
  214. } else if (h->prevpg == P_INVALID) {
  215. if (index == 0) {
  216. t->bt_order = BACK;
  217. t->bt_last.index = 0;
  218. t->bt_last.pgno = h->pgno;
  219. }
  220. }
  221. }
  222. mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  223. success:
  224. if (flags == R_SETCURSOR)
  225. __bt_setcur(t, e->page->pgno, e->index);
  226. F_SET(t, B_MODIFIED);
  227. return (RET_SUCCESS);
  228. }
  229. #ifdef STATISTICS
  230. u_long bt_cache_hit, bt_cache_miss;
  231. #endif
  232. /*
  233. * BT_FAST -- Do a quick check for sorted data.
  234. *
  235. * Parameters:
  236. * t: tree
  237. * key: key to insert
  238. *
  239. * Returns:
  240. * EPG for new record or NULL if not found.
  241. */
  242. static EPG *
  243. bt_fast(t, key, data, exactp)
  244. BTREE *t;
  245. const DBT *key, *data;
  246. int *exactp;
  247. {
  248. PAGE *h;
  249. u_int32_t nbytes;
  250. int cmp;
  251. if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) {
  252. t->bt_order = NOT;
  253. return (NULL);
  254. }
  255. t->bt_cur.page = h;
  256. t->bt_cur.index = t->bt_last.index;
  257. /*
  258. * If won't fit in this page or have too many keys in this page,
  259. * have to search to get split stack.
  260. */
  261. nbytes = NBLEAFDBT(key->size, data->size);
  262. if ((u_int32_t) (h->upper - h->lower) < nbytes + sizeof(indx_t))
  263. goto miss;
  264. if (t->bt_order == FORWARD) {
  265. if (t->bt_cur.page->nextpg != P_INVALID)
  266. goto miss;
  267. if (t->bt_cur.index != NEXTINDEX(h) - 1)
  268. goto miss;
  269. if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0)
  270. goto miss;
  271. t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index;
  272. } else {
  273. if (t->bt_cur.page->prevpg != P_INVALID)
  274. goto miss;
  275. if (t->bt_cur.index != 0)
  276. goto miss;
  277. if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0)
  278. goto miss;
  279. t->bt_last.index = 0;
  280. }
  281. *exactp = cmp == 0;
  282. #ifdef STATISTICS
  283. ++bt_cache_hit;
  284. #endif
  285. return (&t->bt_cur);
  286. miss:
  287. #ifdef STATISTICS
  288. ++bt_cache_miss;
  289. #endif
  290. t->bt_order = NOT;
  291. mpool_put(t->bt_mp, h, 0);
  292. return (NULL);
  293. }