Asterisk - The Open Source Telephony Project  18.5.0
rec_delete.c
Go to the documentation of this file.
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 
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)rec_delete.c 8.7 (Berkeley) 7/14/94";
39 #endif /* LIBC_SCCS and not lint */
40 
41 #include <sys/types.h>
42 
43 #include <errno.h>
44 #include <stdio.h>
45 #include <string.h>
46 
47 #include "../include/db.h"
48 #include "recno.h"
49 
50 static int rec_rdelete __P((BTREE *, recno_t));
51 
52 /*
53  * __REC_DELETE -- Delete the item(s) referenced by a key.
54  *
55  * Parameters:
56  * dbp: pointer to access method
57  * key: key to delete
58  * flags: R_CURSOR if deleting what the cursor references
59  *
60  * Returns:
61  * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
62  */
63 int
64 __rec_delete(dbp, key, flags)
65  const DB *dbp;
66  const DBT *key;
67  u_int flags;
68 {
69  BTREE *t;
70  recno_t nrec;
71  int status;
72 
73  t = dbp->internal;
74 
75  /* Toss any page pinned across calls. */
76  if (t->bt_pinned != NULL) {
77  mpool_put(t->bt_mp, t->bt_pinned, 0);
78  t->bt_pinned = NULL;
79  }
80 
81  switch(flags) {
82  case 0:
83  if ((nrec = *(recno_t *)key->data) == 0)
84  goto einval;
85  if (nrec > t->bt_nrecs)
86  return (RET_SPECIAL);
87  --nrec;
88  status = rec_rdelete(t, nrec);
89  break;
90  case R_CURSOR:
91  if (!F_ISSET(&t->bt_cursor, CURS_INIT))
92  goto einval;
93  if (t->bt_nrecs == 0)
94  return (RET_SPECIAL);
95  status = rec_rdelete(t, t->bt_cursor.rcursor - 1);
96  if (status == RET_SUCCESS)
97  --t->bt_cursor.rcursor;
98  break;
99  default:
100 einval: errno = EINVAL;
101  return (RET_ERROR);
102  }
103 
104  if (status == RET_SUCCESS)
106  return (status);
107 }
108 
109 /*
110  * REC_RDELETE -- Delete the data matching the specified key.
111  *
112  * Parameters:
113  * tree: tree
114  * nrec: record to delete
115  *
116  * Returns:
117  * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
118  */
119 static int
120 rec_rdelete(t, nrec)
121  BTREE *t;
122  recno_t nrec;
123 {
124  EPG *e;
125  PAGE *h;
126  int status;
127 
128  /* Find the record; __rec_search pins the page. */
129  if ((e = __rec_search(t, nrec, SDELETE)) == NULL)
130  return (RET_ERROR);
131 
132  /* Delete the record. */
133  h = e->page;
134  status = __rec_dleaf(t, h, e->index);
135  if (status != RET_SUCCESS) {
136  mpool_put(t->bt_mp, h, 0);
137  return (status);
138  }
139  mpool_put(t->bt_mp, h, MPOOL_DIRTY);
140  return (RET_SUCCESS);
141 }
142 
143 /*
144  * __REC_DLEAF -- Delete a single record from a recno leaf page.
145  *
146  * Parameters:
147  * t: tree
148  * index: index on current page to delete
149  *
150  * Returns:
151  * RET_SUCCESS, RET_ERROR.
152  */
153 int
154 __rec_dleaf(t, h, idx)
155  BTREE *t;
156  PAGE *h;
157  u_int32_t idx;
158 {
159  RLEAF *rl;
160  indx_t *ip, cnt, offset;
161  u_int32_t nbytes;
162  char *from;
163  void *to;
164 
165  /*
166  * Delete a record from a recno leaf page. Internal records are never
167  * deleted from internal pages, regardless of the records that caused
168  * them to be added being deleted. Pages made empty by deletion are
169  * not reclaimed. They are, however, made available for reuse.
170  *
171  * Pack the remaining entries at the end of the page, shift the indices
172  * down, overwriting the deleted record and its index. If the record
173  * uses overflow pages, make them available for reuse.
174  */
175  to = rl = GETRLEAF(h, idx);
176  if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR)
177  return (RET_ERROR);
178  nbytes = NRLEAF(rl);
179 
180  /*
181  * Compress the key/data pairs. Compress and adjust the [BR]LEAF
182  * offsets. Reset the headers.
183  */
184  from = (char *)h + h->upper;
185  memmove(from + nbytes, from, (char *)to - from);
186  h->upper += nbytes;
187 
188  offset = h->linp[idx];
189  for (cnt = &h->linp[idx] - (ip = &h->linp[0]); cnt--; ++ip)
190  if (ip[0] < offset)
191  ip[0] += nbytes;
192  for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip)
193  ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
194  h->lower -= sizeof(indx_t);
195  --t->bt_nrecs;
196  return (RET_SUCCESS);
197 }
static int rec_rdelete(BTREE *t, recno_t nrec)
Definition: rec_delete.c:120
#define R_CURSOR
Definition: db.h:91
Definition: btree.h:75
void * data
Definition: db.h:86
#define NEXTINDEX(p)
Definition: btree.h:98
#define RET_ERROR
Definition: db.h:51
#define GETRLEAF(pg, indx)
Definition: btree.h:220
#define F_SET(p, f)
Definition: btree.h:40
#define B_MODIFIED
Definition: btree.h:370
#define F_ISSET(p, f)
Definition: btree.h:42
u_char flags
Definition: btree.h:215
Definition: btree.h:213
int mpool_put(MPOOL *mp, void *page, u_int flags)
Definition: mpool.c:251
CURSOR bt_cursor
Definition: btree.h:320
recno_t rcursor
Definition: btree.h:286
Definition: btree.h:254
void * internal
Definition: db.h:137
Definition: db.h:85
indx_t lower
Definition: btree.h:89
#define NULL
Definition: resample.c:96
u_int16_t indx_t
Definition: db.h:80
EPG * __rec_search(BTREE *t, recno_t recno, enum SRCHOP op)
Definition: rec_search.c:64
indx_t upper
Definition: btree.h:90
recno_t bt_nrecs
Definition: btree.h:360
Definition: btree.h:312
#define R_MODIFIED
Definition: btree.h:382
#define MPOOL_DIRTY
Definition: mpool.h:61
#define NRLEAF(p)
Definition: btree.h:224
#define RET_SUCCESS
Definition: db.h:52
PAGE * bt_pinned
Definition: btree.h:318
PAGE * page
Definition: btree.h:255
indx_t linp[1]
Definition: btree.h:91
#define CURS_INIT
Definition: btree.h:291
MPOOL * bt_mp
Definition: btree.h:313
static int rec_rdelete __P((BTREE *, recno_t))
int __rec_dleaf(BTREE *t, PAGE *h, u_int32_t idx)
Definition: rec_delete.c:154
static DB * dbp
Definition: hsearch.c:49
indx_t index
Definition: btree.h:256
int errno
char bytes[1]
Definition: btree.h:216
unsigned int u_int32_t
Definition: recno.h:36
Definition: db.h:129
#define P_BIGDATA
Definition: btree.h:131
#define RET_SPECIAL
Definition: db.h:53
u_int32_t recno_t
Definition: db.h:82
int __rec_delete(DB *dbp, const DBT *key, u_int flags) const
Definition: rec_delete.c:64
jack_status_t status
Definition: app_jack.c:146
int __ovfl_delete(BTREE *t, void *p)
Definition: bt_overflow.c:193