xref: /titanic_41/usr/src/cmd/sendmail/db/db/db_join.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 1998
5  *	Sleepycat Software.  All rights reserved.
6  */
7 
8 #pragma ident	"%Z%%M%	%I%	%E% SMI"
9 
10 #include "config.h"
11 
12 #ifndef lint
13 static const char sccsid[] = "@(#)db_join.c	10.10 (Sleepycat) 10/9/98";
14 #endif /* not lint */
15 
16 #ifndef NO_SYSTEM_INCLUDES
17 #include <sys/types.h>
18 
19 #include <errno.h>
20 #include <string.h>
21 #endif
22 
23 #include "db_int.h"
24 #include "db_page.h"
25 #include "db_join.h"
26 #include "db_am.h"
27 #include "common_ext.h"
28 
29 static int __db_join_close __P((DBC *));
30 static int __db_join_del __P((DBC *, u_int32_t));
31 static int __db_join_get __P((DBC *, DBT *, DBT *, u_int32_t));
32 static int __db_join_put __P((DBC *, DBT *, DBT *, u_int32_t));
33 
34 /*
35  * This is the duplicate-assisted join functionality.  Right now we're
36  * going to write it such that we return one item at a time, although
37  * I think we may need to optimize it to return them all at once.
38  * It should be easier to get it working this way, and I believe that
39  * changing it should be fairly straightforward.
40  *
41  * XXX
42  * Right now we do not maintain the number of duplicates so we do
43  * not optimize the join.  If the caller does, then best performance
44  * will be achieved by putting the cursor with the smallest cardinality
45  * first.
46  *
47  * The first cursor moves sequentially through the duplicate set while
48  * the others search explicitly for the duplicate in question.
49  *
50  */
51 
52 /*
53  * __db_join --
54  *	This is the interface to the duplicate-assisted join functionality.
55  * In the same way that cursors mark a position in a database, a cursor
56  * can mark a position in a join.  While most cursors are created by the
57  * cursor method of a DB, join cursors are created through an explicit
58  * call to DB->join.
59  *
60  * The curslist is an array of existing, intialized cursors and primary
61  * is the DB of the primary file.  The data item that joins all the
62  * cursors in the curslist is used as the key into the primary and that
63  * key and data are returned.  When no more items are left in the join
64  * set, the  c_next operation off the join cursor will return DB_NOTFOUND.
65  *
66  * PUBLIC: int __db_join __P((DB *, DBC **, u_int32_t, DBC **));
67  */
68 int
__db_join(primary,curslist,flags,dbcp)69 __db_join(primary, curslist, flags, dbcp)
70 	DB *primary;
71 	DBC **curslist, **dbcp;
72 	u_int32_t flags;
73 {
74 	DBC *dbc;
75 	JOIN_CURSOR *jc;
76 	int i, ret;
77 
78 	DB_PANIC_CHECK(primary);
79 
80 	if ((ret = __db_joinchk(primary, flags)) != 0)
81 		return (ret);
82 
83 	if (curslist == NULL || curslist[0] == NULL)
84 		return (EINVAL);
85 
86 	dbc = NULL;
87 	jc = NULL;
88 
89 	if ((ret = __os_calloc(1, sizeof(DBC), &dbc)) != 0)
90 		goto err;
91 
92 	if ((ret = __os_calloc(1, sizeof(JOIN_CURSOR), &jc)) != 0)
93 		goto err;
94 
95 	if ((ret = __os_malloc(256, NULL, &jc->j_key.data)) != 0)
96 		goto err;
97 	jc->j_key.ulen = 256;
98 	F_SET(&jc->j_key, DB_DBT_USERMEM);
99 
100 	for (jc->j_curslist = curslist;
101 	    *jc->j_curslist != NULL; jc->j_curslist++)
102 		;
103 	if ((ret = __os_calloc((jc->j_curslist - curslist + 1),
104 	    sizeof(DBC *), &jc->j_curslist)) != 0)
105 		goto err;
106 	for (i = 0; curslist[i] != NULL; i++) {
107 		if (i != 0)
108 			F_SET(curslist[i], DBC_KEYSET);
109 		jc->j_curslist[i] = curslist[i];
110 	}
111 
112 	dbc->c_close = __db_join_close;
113 	dbc->c_del = __db_join_del;
114 	dbc->c_get = __db_join_get;
115 	dbc->c_put = __db_join_put;
116 	dbc->internal = jc;
117 	dbc->dbp = primary;
118 	jc->j_init = 1;
119 	jc->j_primary = primary;
120 
121 	*dbcp = dbc;
122 
123 	return (0);
124 
125 err:	if (jc != NULL) {
126 		if (jc->j_curslist != NULL)
127 			__os_free(jc->j_curslist,
128 			    (jc->j_curslist - curslist + 1) * sizeof(DBC *));
129 		__os_free(jc, sizeof(JOIN_CURSOR));
130 	}
131 	if (dbc != NULL)
132 		__os_free(dbc, sizeof(DBC));
133 	return (ret);
134 }
135 
136 static int
__db_join_put(dbc,key,data,flags)137 __db_join_put(dbc, key, data, flags)
138 	DBC *dbc;
139 	DBT *key;
140 	DBT *data;
141 	u_int32_t flags;
142 {
143 	DB_PANIC_CHECK(dbc->dbp);
144 
145 	COMPQUIET(key, NULL);
146 	COMPQUIET(data, NULL);
147 	COMPQUIET(flags, 0);
148 	return (EINVAL);
149 }
150 
151 static int
__db_join_del(dbc,flags)152 __db_join_del(dbc, flags)
153 	DBC *dbc;
154 	u_int32_t flags;
155 {
156 	DB_PANIC_CHECK(dbc->dbp);
157 
158 	COMPQUIET(flags, 0);
159 	return (EINVAL);
160 }
161 
162 static int
__db_join_get(dbc,key,data,flags)163 __db_join_get(dbc, key, data, flags)
164 	DBC *dbc;
165 	DBT *key, *data;
166 	u_int32_t flags;
167 {
168 	DB *dbp;
169 	DBC **cpp;
170 	JOIN_CURSOR *jc;
171 	int ret;
172 	u_int32_t operation;
173 
174 	dbp = dbc->dbp;
175 
176 	DB_PANIC_CHECK(dbp);
177 
178 	operation = LF_ISSET(DB_OPFLAGS_MASK);
179 	if (operation != 0 && operation != DB_JOIN_ITEM)
180 		return (__db_ferr(dbp->dbenv, "DBcursor->c_get", 0));
181 
182 	LF_CLR(DB_OPFLAGS_MASK);
183 	if ((ret =
184 	    __db_fchk(dbp->dbenv, "DBcursor->c_get", flags, DB_RMW)) != 0)
185 		return (ret);
186 
187 	jc = (JOIN_CURSOR *)dbc->internal;
188 retry:
189 	ret = jc->j_curslist[0]->c_get(jc->j_curslist[0],
190 	    &jc->j_key, key, jc->j_init ? DB_CURRENT : DB_NEXT_DUP);
191 
192 	if (ret == ENOMEM) {
193 		jc->j_key.ulen <<= 1;
194 		if ((ret = __os_realloc(&jc->j_key.data, jc->j_key.ulen)) != 0)
195 			return (ret);
196 		goto retry;
197 	}
198 	if (ret != 0)
199 		return (ret);
200 
201 	jc->j_init = 0;
202 	do {
203 		/*
204 		 * We have the first element; now look for it in the
205 		 * other cursors.
206 		 */
207 		for (cpp = jc->j_curslist + 1; *cpp != NULL; cpp++) {
208 retry2:			if ((ret = ((*cpp)->c_get)(*cpp,
209 			    &jc->j_key, key, DB_GET_BOTH)) == DB_NOTFOUND)
210 				break;
211 			if (ret == ENOMEM) {
212 				jc->j_key.ulen <<= 1;
213 				if ((ret = __os_realloc(&jc->j_key.data,
214 				    jc->j_key.ulen)) != 0)
215 					return (ret);
216 				goto retry2;
217 			}
218 			if (F_ISSET(*cpp, DBC_KEYSET)) {
219 				F_CLR(*cpp, DBC_KEYSET);
220 				F_SET(*cpp, DBC_CONTINUE);
221 			}
222 		}
223 
224 		/*
225 		 * If we got out of here with ret != 0, then we failed to
226 		 * find the duplicate in one of the files, so we go on to
227 		 * the next item in the outermost relation. If ret was
228 		 * equal to 0, then we've got something to return.
229 		 */
230 		if (ret == 0)
231 			break;
232 	} while ((ret = jc->j_curslist[0]->c_get(jc->j_curslist[0],
233 	    &jc->j_key, key,  DB_NEXT_DUP)) == 0);
234 
235 	/*
236 	 * If ret != 0 here, we've exhausted the first file.  Otherwise,
237 	 * key and data are set and we need to do the lookup on the
238 	 * primary.
239 	 */
240 	if (ret != 0)
241 		return (ret);
242 
243 	if (operation == DB_JOIN_ITEM)
244 		return (0);
245 	else
246 		return ((jc->j_primary->get)(jc->j_primary,
247 		    jc->j_curslist[0]->txn, key, data, 0));
248 }
249 
250 static int
__db_join_close(dbc)251 __db_join_close(dbc)
252 	DBC *dbc;
253 {
254 	JOIN_CURSOR *jc;
255 	int i;
256 
257 	DB_PANIC_CHECK(dbc->dbp);
258 
259 	jc = (JOIN_CURSOR *)dbc->internal;
260 
261 	/*
262 	 * Clear the optimization flag in the cursors.
263 	 */
264 	for (i = 0; jc->j_curslist[i] != NULL; i++)
265 		F_CLR(jc->j_curslist[i], DBC_CONTINUE | DBC_KEYSET);
266 
267 	__os_free(jc->j_curslist, 0);
268 	__os_free(jc->j_key.data, jc->j_key.ulen);
269 	__os_free(jc, sizeof(JOIN_CURSOR));
270 	__os_free(dbc, sizeof(DBC));
271 
272 	return (0);
273 }
274