Asterisk - The Open Source Telephony Project  GIT-master-e8cda4b
bt_overflow.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[] = "@(#)bt_overflow.c 8.5 (Berkeley) 7/16/94";
39 #endif /* LIBC_SCCS and not lint */
40 
41 #include <sys/param.h>
42 
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46 
47 #include "../include/db.h"
48 #include "btree.h"
49 
50 /*
51  * Big key/data code.
52  *
53  * Big key and data entries are stored on linked lists of pages. The initial
54  * reference is byte string stored with the key or data and is the page number
55  * and size. The actual record is stored in a chain of pages linked by the
56  * nextpg field of the PAGE header.
57  *
58  * The first page of the chain has a special property. If the record is used
59  * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
60  * in the header.
61  *
62  * XXX
63  * A single DBT is written to each chain, so a lot of space on the last page
64  * is wasted. This is a fairly major bug for some data sets.
65  */
66 
67 /*
68  * __OVFL_GET -- Get an overflow key/data item.
69  *
70  * Parameters:
71  * t: tree
72  * p: pointer to { pgno_t, u_int32_t }
73  * buf: storage address
74  * bufsz: storage size
75  *
76  * Returns:
77  * RET_ERROR, RET_SUCCESS
78  */
79 int
80 __ovfl_get(t, p, ssz, buf, bufsz)
81  BTREE *t;
82  void *p;
83  size_t *ssz;
84  void **buf;
85  size_t *bufsz;
86 {
87  PAGE *h;
88  pgno_t pg;
89  size_t nb, plen;
90  u_int32_t sz;
91 
92  memmove(&pg, p, sizeof(pgno_t));
93  memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
94  *ssz = sz;
95 
96 #ifdef DEBUG
97  if (pg == P_INVALID || sz == 0)
98  abort();
99 #endif
100  /* Make the buffer bigger as necessary. */
101  if (*bufsz < sz) {
102  *buf = (char *)(*buf == NULL ? malloc(sz) : realloc(*buf, sz));
103  if (*buf == NULL)
104  return (RET_ERROR);
105  *bufsz = sz;
106  }
107 
108  /*
109  * Step through the linked list of pages, copying the data on each one
110  * into the buffer. Never copy more than the data's length.
111  */
112  plen = t->bt_psize - BTDATAOFF;
113  for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
114  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
115  return (RET_ERROR);
116 
117  nb = MIN(sz, plen);
118  memmove(p, (char *)h + BTDATAOFF, nb);
119  mpool_put(t->bt_mp, h, 0);
120 
121  if ((sz -= nb) == 0)
122  break;
123  }
124  return (RET_SUCCESS);
125 }
126 
127 /*
128  * __OVFL_PUT -- Store an overflow key/data item.
129  *
130  * Parameters:
131  * t: tree
132  * data: DBT to store
133  * pgno: storage page number
134  *
135  * Returns:
136  * RET_ERROR, RET_SUCCESS
137  */
138 int
139 __ovfl_put(t, dbt, pg)
140  BTREE *t;
141  const DBT *dbt;
142  pgno_t *pg;
143 {
144  PAGE *h, *last;
145  void *p;
146  pgno_t npg;
147  size_t nb, plen;
148  u_int32_t sz;
149 
150  /*
151  * Allocate pages and copy the key/data record into them. Store the
152  * number of the first page in the chain.
153  */
154  plen = t->bt_psize - BTDATAOFF;
155  for (last = NULL, p = dbt->data, sz = dbt->size;;
156  p = (char *)p + plen, last = h) {
157  if ((h = __bt_new(t, &npg)) == NULL)
158  return (RET_ERROR);
159 
160  h->pgno = npg;
161  h->nextpg = h->prevpg = P_INVALID;
162  h->flags = P_OVERFLOW;
163  h->lower = h->upper = 0;
164 
165  nb = MIN(sz, plen);
166  memmove((char *)h + BTDATAOFF, p, nb);
167 
168  if (last) {
169  last->nextpg = h->pgno;
170  mpool_put(t->bt_mp, last, MPOOL_DIRTY);
171  } else
172  *pg = h->pgno;
173 
174  if ((sz -= nb) == 0) {
175  mpool_put(t->bt_mp, h, MPOOL_DIRTY);
176  break;
177  }
178  }
179  return (RET_SUCCESS);
180 }
181 
182 /*
183  * __OVFL_DELETE -- Delete an overflow chain.
184  *
185  * Parameters:
186  * t: tree
187  * p: pointer to { pgno_t, u_int32_t }
188  *
189  * Returns:
190  * RET_ERROR, RET_SUCCESS
191  */
192 int
194  BTREE *t;
195  void *p;
196 {
197  PAGE *h;
198  pgno_t pg;
199  size_t plen;
200  u_int32_t sz;
201 
202  memmove(&pg, p, sizeof(pgno_t));
203  memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
204 
205 #ifdef DEBUG
206  if (pg == P_INVALID || sz == 0)
207  abort();
208 #endif
209  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
210  return (RET_ERROR);
211 
212  /* Don't delete chains used by internal pages. */
213  if (h->flags & P_PRESERVE) {
214  mpool_put(t->bt_mp, h, 0);
215  return (RET_SUCCESS);
216  }
217 
218  /* Step through the chain, calling the free routine for each page. */
219  for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
220  pg = h->nextpg;
221  __bt_free(t, h);
222  if (sz <= plen)
223  break;
224  if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
225  return (RET_ERROR);
226  }
227  return (RET_SUCCESS);
228 }
Definition: btree.h:75
#define P_PRESERVE
Definition: btree.h:86
void * data
Definition: db.h:86
size_t size
Definition: db.h:87
#define RET_ERROR
Definition: db.h:51
pgno_t pgno
Definition: btree.h:76
#define realloc(a, b)
Definition: astmm.h:163
char buf[BUFSIZE]
Definition: eagi_proxy.c:66
int mpool_put(MPOOL *mp, void *page, u_int flags)
Definition: mpool.c:251
int __ovfl_get(BTREE *t, void *p, size_t *ssz, void **buf, size_t *bufsz)
Definition: bt_overflow.c:80
Definition: db.h:85
indx_t lower
Definition: btree.h:89
#define NULL
Definition: resample.c:96
indx_t upper
Definition: btree.h:90
Definition: btree.h:312
#define MPOOL_DIRTY
Definition: mpool.h:61
#define MIN(a, b)
Definition: utils.h:226
char * malloc()
void * mpool_get(MPOOL *mp, pgno_t pgno, u_int flags)
Definition: mpool.c:165
int __bt_free(BTREE *t, PAGE *h)
Definition: bt_page.c:60
u_int32_t flags
Definition: btree.h:87
struct sla_ringing_trunk * last
Definition: app_meetme.c:1092
#define RET_SUCCESS
Definition: db.h:52
MPOOL * bt_mp
Definition: btree.h:313
u_int32_t pgno_t
Definition: db.h:78
pgno_t nextpg
Definition: btree.h:78
pgno_t prevpg
Definition: btree.h:77
u_int32_t bt_psize
Definition: btree.h:338
unsigned int u_int32_t
#define P_INVALID
Definition: btree.h:63
#define BTDATAOFF
Definition: btree.h:95
#define P_OVERFLOW
Definition: btree.h:82
PAGE * __bt_new(BTREE *t, pgno_t *npg)
Definition: bt_page.c:86
int __ovfl_delete(BTREE *t, void *p)
Definition: bt_overflow.c:193
int __ovfl_put(BTREE *t, const DBT *dbt, pgno_t *pg)
Definition: bt_overflow.c:139