1*7c478bd9Sstevel@tonic-gate /*
2*7c478bd9Sstevel@tonic-gate  * CDDL HEADER START
3*7c478bd9Sstevel@tonic-gate  *
4*7c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
5*7c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
6*7c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
7*7c478bd9Sstevel@tonic-gate  * with the License.
8*7c478bd9Sstevel@tonic-gate  *
9*7c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*7c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
11*7c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
12*7c478bd9Sstevel@tonic-gate  * and limitations under the License.
13*7c478bd9Sstevel@tonic-gate  *
14*7c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
15*7c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*7c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
17*7c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
18*7c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
19*7c478bd9Sstevel@tonic-gate  *
20*7c478bd9Sstevel@tonic-gate  * CDDL HEADER END
21*7c478bd9Sstevel@tonic-gate  */
22*7c478bd9Sstevel@tonic-gate /*
23*7c478bd9Sstevel@tonic-gate  *	db_index_entry.cc
24*7c478bd9Sstevel@tonic-gate  *
25*7c478bd9Sstevel@tonic-gate  *	Copyright (c) 1988-2000 by Sun Microsystems, Inc.
26*7c478bd9Sstevel@tonic-gate  *	All Rights Reserved.
27*7c478bd9Sstevel@tonic-gate  */
28*7c478bd9Sstevel@tonic-gate 
29*7c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
30*7c478bd9Sstevel@tonic-gate 
31*7c478bd9Sstevel@tonic-gate #include <stdio.h>
32*7c478bd9Sstevel@tonic-gate 
33*7c478bd9Sstevel@tonic-gate #include "db_headers.h"
34*7c478bd9Sstevel@tonic-gate #include "db_index_entry.h"
35*7c478bd9Sstevel@tonic-gate #include "nisdb_mt.h"
36*7c478bd9Sstevel@tonic-gate 
37*7c478bd9Sstevel@tonic-gate /* Constructor:  create an entry using given string and location info. */
db_index_entry(char * name,int nlen,entryp ep)38*7c478bd9Sstevel@tonic-gate db_index_entry::db_index_entry(char* name, int nlen, entryp ep)
39*7c478bd9Sstevel@tonic-gate {
40*7c478bd9Sstevel@tonic-gate 	if ((key = new item(name, nlen)) == NULL)
41*7c478bd9Sstevel@tonic-gate 		FATAL("db_index_entry::db_index_entry: cannot allocate space",
42*7c478bd9Sstevel@tonic-gate 			DB_MEMORY_LIMIT);
43*7c478bd9Sstevel@tonic-gate 	location = ep;
44*7c478bd9Sstevel@tonic-gate 	next_result = next = NULL;
45*7c478bd9Sstevel@tonic-gate 	/* what about hashval ? */
46*7c478bd9Sstevel@tonic-gate }
47*7c478bd9Sstevel@tonic-gate 
48*7c478bd9Sstevel@tonic-gate /*
49*7c478bd9Sstevel@tonic-gate  * Constructor:  create an entry using the given info.
50*7c478bd9Sstevel@tonic-gate  * A copy of the item is made.  New entry is added to head of list of 'n'.
51*7c478bd9Sstevel@tonic-gate */
db_index_entry(unsigned long hval,item * k,entryp ep,db_index_entry_p rest)52*7c478bd9Sstevel@tonic-gate db_index_entry::db_index_entry(unsigned long hval, item* k,
53*7c478bd9Sstevel@tonic-gate 				entryp ep, db_index_entry_p rest)
54*7c478bd9Sstevel@tonic-gate {
55*7c478bd9Sstevel@tonic-gate 	if ((key = new item(k)) == NULL)
56*7c478bd9Sstevel@tonic-gate 		FATAL(
57*7c478bd9Sstevel@tonic-gate 		"db_index_entry::db_index_entry: cannot allocate space (2)",
58*7c478bd9Sstevel@tonic-gate 		DB_MEMORY_LIMIT);
59*7c478bd9Sstevel@tonic-gate 	location = ep;
60*7c478bd9Sstevel@tonic-gate 	next = rest;
61*7c478bd9Sstevel@tonic-gate 	next_result = NULL;
62*7c478bd9Sstevel@tonic-gate 	hashval = hval;
63*7c478bd9Sstevel@tonic-gate }
64*7c478bd9Sstevel@tonic-gate 
65*7c478bd9Sstevel@tonic-gate /*
66*7c478bd9Sstevel@tonic-gate  * Join two lists (entry as identified by its 'location' occurs on both list,
67*7c478bd9Sstevel@tonic-gate  * then it is included in the list returned).
68*7c478bd9Sstevel@tonic-gate  * Returns pointer to resulting list; size of list
69*7c478bd9Sstevel@tonic-gate  * returned in 'newsize'.  List is chained using the 'nextresult' pointer.
70*7c478bd9Sstevel@tonic-gate  */
71*7c478bd9Sstevel@tonic-gate db_index_entry_p
join(long,long,db_index_entry_p list2,long * newsize)72*7c478bd9Sstevel@tonic-gate db_index_entry::join(long /* size1 */, long /* size2 */,
73*7c478bd9Sstevel@tonic-gate 	db_index_entry_p list2, long * newsize)
74*7c478bd9Sstevel@tonic-gate {
75*7c478bd9Sstevel@tonic-gate 	db_index_entry_p mergedlist = NULL, // records that occur on both lists
76*7c478bd9Sstevel@tonic-gate 		mergedtail = NULL, 	// tail pointer of mergedlist
77*7c478bd9Sstevel@tonic-gate 		current,		// current pointer of this list
78*7c478bd9Sstevel@tonic-gate 		other,			// current pointer of updated list2
79*7c478bd9Sstevel@tonic-gate 		otherprev,		// previous pointer of updated list2
80*7c478bd9Sstevel@tonic-gate 		otherstart = list2;	// head of updated list2
81*7c478bd9Sstevel@tonic-gate 	int count = 0;
82*7c478bd9Sstevel@tonic-gate 
83*7c478bd9Sstevel@tonic-gate 	/*
84*7c478bd9Sstevel@tonic-gate 	 * algorithm is straightforward:
85*7c478bd9Sstevel@tonic-gate 	 * traverse this list,
86*7c478bd9Sstevel@tonic-gate 	 * for each item, traverse list2,
87*7c478bd9Sstevel@tonic-gate 	 * if item on list1 matches item on list2,
88*7c478bd9Sstevel@tonic-gate 	 * add to merged list and delete it from list2.
89*7c478bd9Sstevel@tonic-gate 	 */
90*7c478bd9Sstevel@tonic-gate 
91*7c478bd9Sstevel@tonic-gate 	for (current = this; (current != NULL) && (otherstart != NULL);
92*7c478bd9Sstevel@tonic-gate 					current = current->next_result) {
93*7c478bd9Sstevel@tonic-gate 		/* find 'current' in 'other' list */
94*7c478bd9Sstevel@tonic-gate 		otherprev = NULL;
95*7c478bd9Sstevel@tonic-gate 		for (other = otherstart;
96*7c478bd9Sstevel@tonic-gate 			other != NULL;
97*7c478bd9Sstevel@tonic-gate 			other = other->next_result) {
98*7c478bd9Sstevel@tonic-gate 			if (current->location == other->location)
99*7c478bd9Sstevel@tonic-gate 				break;
100*7c478bd9Sstevel@tonic-gate 			else
101*7c478bd9Sstevel@tonic-gate 				otherprev = other;
102*7c478bd9Sstevel@tonic-gate 		}
103*7c478bd9Sstevel@tonic-gate 		if (other != NULL) { /* found */
104*7c478bd9Sstevel@tonic-gate 			/* delete 'other' from future consideration */
105*7c478bd9Sstevel@tonic-gate 			if (otherprev == NULL) {
106*7c478bd9Sstevel@tonic-gate 				/* new head */
107*7c478bd9Sstevel@tonic-gate 				otherstart = otherstart->next_result;
108*7c478bd9Sstevel@tonic-gate 			} else {
109*7c478bd9Sstevel@tonic-gate 				/* bypass 'other' */
110*7c478bd9Sstevel@tonic-gate 				otherprev->next_result = other->next_result;
111*7c478bd9Sstevel@tonic-gate 			}
112*7c478bd9Sstevel@tonic-gate 			/* add 'current' to list of items found so far */
113*7c478bd9Sstevel@tonic-gate 			if (mergedlist == NULL)
114*7c478bd9Sstevel@tonic-gate 				mergedlist = current;	/* first one found */
115*7c478bd9Sstevel@tonic-gate 			else
116*7c478bd9Sstevel@tonic-gate 				mergedtail->next_result = current; /* append */
117*7c478bd9Sstevel@tonic-gate 			mergedtail = current; /* point to last entry found */
118*7c478bd9Sstevel@tonic-gate 			++count;
119*7c478bd9Sstevel@tonic-gate 		}
120*7c478bd9Sstevel@tonic-gate 	}
121*7c478bd9Sstevel@tonic-gate 	if (mergedtail) mergedtail->next_result = NULL;  /* set end to null */
122*7c478bd9Sstevel@tonic-gate 	*newsize = count;
123*7c478bd9Sstevel@tonic-gate 	return (mergedlist);
124*7c478bd9Sstevel@tonic-gate }
125*7c478bd9Sstevel@tonic-gate 
126*7c478bd9Sstevel@tonic-gate /* Relocate bucket starting with this entry to new hashtable 'new_tab'. */
127*7c478bd9Sstevel@tonic-gate void
relocate(db_index_entry_p * new_tab,unsigned long hashsize)128*7c478bd9Sstevel@tonic-gate db_index_entry::relocate(db_index_entry_p *new_tab, unsigned long hashsize)
129*7c478bd9Sstevel@tonic-gate {
130*7c478bd9Sstevel@tonic-gate 	db_index_entry_p np, next_np, *hp;
131*7c478bd9Sstevel@tonic-gate 
132*7c478bd9Sstevel@tonic-gate 	for (np = this; np != NULL; np = next_np) {
133*7c478bd9Sstevel@tonic-gate 		next_np = np->next;
134*7c478bd9Sstevel@tonic-gate 		hp = &new_tab[np->hashval % hashsize];
135*7c478bd9Sstevel@tonic-gate 		np->next = *hp;
136*7c478bd9Sstevel@tonic-gate 		*hp = np;
137*7c478bd9Sstevel@tonic-gate 	}
138*7c478bd9Sstevel@tonic-gate }
139*7c478bd9Sstevel@tonic-gate 
140*7c478bd9Sstevel@tonic-gate /* Return the next entry in the bucket starting with this entry
141*7c478bd9Sstevel@tonic-gate 	    with the same hashvalue, key and location as this entry. */
142*7c478bd9Sstevel@tonic-gate db_index_entry_p
getnext(bool_t casein,unsigned long hval,item * i,entryp l)143*7c478bd9Sstevel@tonic-gate db_index_entry::getnext(bool_t casein, unsigned long hval, item *i, entryp l)
144*7c478bd9Sstevel@tonic-gate {
145*7c478bd9Sstevel@tonic-gate 	db_index_entry_p np;
146*7c478bd9Sstevel@tonic-gate 
147*7c478bd9Sstevel@tonic-gate 	for (np = this; np != NULL; np = np->next) {
148*7c478bd9Sstevel@tonic-gate 		if ((np->hashval == hval) &&
149*7c478bd9Sstevel@tonic-gate 	(np->key->equal(i, casein)) && l == location) {
150*7c478bd9Sstevel@tonic-gate 			break;
151*7c478bd9Sstevel@tonic-gate 		}
152*7c478bd9Sstevel@tonic-gate 	}
153*7c478bd9Sstevel@tonic-gate 
154*7c478bd9Sstevel@tonic-gate 	if (np != NULL)
155*7c478bd9Sstevel@tonic-gate 		return (np->next);
156*7c478bd9Sstevel@tonic-gate 	else
157*7c478bd9Sstevel@tonic-gate 		return (NULL);
158*7c478bd9Sstevel@tonic-gate }
159*7c478bd9Sstevel@tonic-gate 
160*7c478bd9Sstevel@tonic-gate /*
161*7c478bd9Sstevel@tonic-gate  * Return pointer to index entry with same hash value, same key,
162*7c478bd9Sstevel@tonic-gate  * and same record number as those supplied.  Returns NULL if not found.
163*7c478bd9Sstevel@tonic-gate  */
164*7c478bd9Sstevel@tonic-gate db_index_entry_p
lookup(bool_t casein,unsigned long hval,item * i,entryp recnum)165*7c478bd9Sstevel@tonic-gate db_index_entry::lookup(bool_t casein, unsigned long hval,
166*7c478bd9Sstevel@tonic-gate 			item *i, entryp recnum)
167*7c478bd9Sstevel@tonic-gate {
168*7c478bd9Sstevel@tonic-gate 	db_index_entry_p np;
169*7c478bd9Sstevel@tonic-gate 
170*7c478bd9Sstevel@tonic-gate 	for (np = this; np != NULL; np = np->next) {
171*7c478bd9Sstevel@tonic-gate 		if (np->hashval == hval && np->key->equal(i, casein) &&
172*7c478bd9Sstevel@tonic-gate 			np->location == recnum) {
173*7c478bd9Sstevel@tonic-gate 			break;
174*7c478bd9Sstevel@tonic-gate 		}
175*7c478bd9Sstevel@tonic-gate 	}
176*7c478bd9Sstevel@tonic-gate 	if (np) np->next_result = NULL;  /* should only be 1 */
177*7c478bd9Sstevel@tonic-gate 	return (np);
178*7c478bd9Sstevel@tonic-gate }
179*7c478bd9Sstevel@tonic-gate 
180*7c478bd9Sstevel@tonic-gate /*
181*7c478bd9Sstevel@tonic-gate  * Returns pointer to a list of index entries with the same hash value and
182*7c478bd9Sstevel@tonic-gate  * key as those given.  Returns in 'how_many' the number of entries in the
183*7c478bd9Sstevel@tonic-gate  * list returned.  The list is linked by the 'next_result' field of the
184*7c478bd9Sstevel@tonic-gate  * index entries.  These may be changed after the next call to 'lookup'
185*7c478bd9Sstevel@tonic-gate  * or 'join'.
186*7c478bd9Sstevel@tonic-gate  */
187*7c478bd9Sstevel@tonic-gate db_index_entry_p
lookup(bool_t casein,unsigned long hval,item * i,long * how_many)188*7c478bd9Sstevel@tonic-gate db_index_entry::lookup(bool_t casein, unsigned long hval,
189*7c478bd9Sstevel@tonic-gate 			item *i, long * how_many)
190*7c478bd9Sstevel@tonic-gate {
191*7c478bd9Sstevel@tonic-gate 	db_index_entry_p fst, prev, curr;
192*7c478bd9Sstevel@tonic-gate 	long count = 0;
193*7c478bd9Sstevel@tonic-gate 
194*7c478bd9Sstevel@tonic-gate 	for (fst = this; fst != NULL; fst = fst->next) {
195*7c478bd9Sstevel@tonic-gate 		if ((fst->hashval == hval) && (fst->key->equal(i, casein))) {
196*7c478bd9Sstevel@tonic-gate 			++count;
197*7c478bd9Sstevel@tonic-gate 			break;
198*7c478bd9Sstevel@tonic-gate 		}
199*7c478bd9Sstevel@tonic-gate 	}
200*7c478bd9Sstevel@tonic-gate 	/*
201*7c478bd9Sstevel@tonic-gate 	 * gather all the ones with the same key; assume that all entries
202*7c478bd9Sstevel@tonic-gate 	 * with same key are located contiguously.
203*7c478bd9Sstevel@tonic-gate 	 */
204*7c478bd9Sstevel@tonic-gate 	if (fst != NULL) {
205*7c478bd9Sstevel@tonic-gate 		prev = fst;
206*7c478bd9Sstevel@tonic-gate 		for (curr = fst->next; curr != NULL; curr = curr->next) {
207*7c478bd9Sstevel@tonic-gate 			if ((curr->hashval == hval) &&
208*7c478bd9Sstevel@tonic-gate 				(curr->key->equal(i, casein))) {
209*7c478bd9Sstevel@tonic-gate 	prev->addresult(curr);
210*7c478bd9Sstevel@tonic-gate 	prev = curr;
211*7c478bd9Sstevel@tonic-gate 	++count;
212*7c478bd9Sstevel@tonic-gate 			}
213*7c478bd9Sstevel@tonic-gate 			else
214*7c478bd9Sstevel@tonic-gate 	break;
215*7c478bd9Sstevel@tonic-gate 		}
216*7c478bd9Sstevel@tonic-gate 		prev->addresult(NULL); /* terminate the list -CM */
217*7c478bd9Sstevel@tonic-gate 	}
218*7c478bd9Sstevel@tonic-gate 	*how_many = count;
219*7c478bd9Sstevel@tonic-gate 	return (fst);
220*7c478bd9Sstevel@tonic-gate }
221*7c478bd9Sstevel@tonic-gate 
222*7c478bd9Sstevel@tonic-gate /*
223*7c478bd9Sstevel@tonic-gate  * Remove entry with the specified hashvalue, key, and record number.
224*7c478bd9Sstevel@tonic-gate  * Returns 'TRUE' if successful, FALSE otherwise.
225*7c478bd9Sstevel@tonic-gate  * If the entry being removed is at the head of the list, then
226*7c478bd9Sstevel@tonic-gate  * the head is updated to reflect the removal. The storage for the index
227*7c478bd9Sstevel@tonic-gate  * entry is freed. The record pointed to by 'recnum' must be removed
228*7c478bd9Sstevel@tonic-gate  * through another means.  All that is updated in this operation is the
229*7c478bd9Sstevel@tonic-gate  * index.
230*7c478bd9Sstevel@tonic-gate  */
231*7c478bd9Sstevel@tonic-gate bool_t
remove(db_index_entry_p * head,bool_t casein,unsigned long hval,item * i,entryp recnum)232*7c478bd9Sstevel@tonic-gate db_index_entry::remove(db_index_entry_p *head, bool_t casein,
233*7c478bd9Sstevel@tonic-gate 			unsigned long hval, item *i, entryp recnum)
234*7c478bd9Sstevel@tonic-gate {
235*7c478bd9Sstevel@tonic-gate 	db_index_entry_p np, dp;
236*7c478bd9Sstevel@tonic-gate 
237*7c478bd9Sstevel@tonic-gate 	/* Search for it in the bucket */
238*7c478bd9Sstevel@tonic-gate 	for (dp = np = this; np != NULL; np = np->next) {
239*7c478bd9Sstevel@tonic-gate 		if (np->hashval == hval && np->key->equal(i, casein) &&
240*7c478bd9Sstevel@tonic-gate 			np->location == recnum) {
241*7c478bd9Sstevel@tonic-gate 			break;
242*7c478bd9Sstevel@tonic-gate 		} else {
243*7c478bd9Sstevel@tonic-gate 			dp = np;
244*7c478bd9Sstevel@tonic-gate 		}
245*7c478bd9Sstevel@tonic-gate 	}
246*7c478bd9Sstevel@tonic-gate 
247*7c478bd9Sstevel@tonic-gate 	if (np == NULL) return FALSE;	// cannot delete if it is not there
248*7c478bd9Sstevel@tonic-gate 
249*7c478bd9Sstevel@tonic-gate 	if (dp == np) {
250*7c478bd9Sstevel@tonic-gate 		*head = np->next;	// deleting head of bucket
251*7c478bd9Sstevel@tonic-gate 	} else {
252*7c478bd9Sstevel@tonic-gate 		dp->next = np->next;	// deleting interior link
253*7c478bd9Sstevel@tonic-gate 		}
254*7c478bd9Sstevel@tonic-gate 	delete np;
255*7c478bd9Sstevel@tonic-gate 
256*7c478bd9Sstevel@tonic-gate 	return (TRUE);
257*7c478bd9Sstevel@tonic-gate }
258*7c478bd9Sstevel@tonic-gate 
259*7c478bd9Sstevel@tonic-gate /* Replace the 'location' field of the index entry with the given one. */
260*7c478bd9Sstevel@tonic-gate /*
261*7c478bd9Sstevel@tonic-gate void
262*7c478bd9Sstevel@tonic-gate db_index_entry::replace(entryp ep)
263*7c478bd9Sstevel@tonic-gate {
264*7c478bd9Sstevel@tonic-gate 	location = ep;
265*7c478bd9Sstevel@tonic-gate }
266*7c478bd9Sstevel@tonic-gate */
267*7c478bd9Sstevel@tonic-gate 
268*7c478bd9Sstevel@tonic-gate /*
269*7c478bd9Sstevel@tonic-gate  * Create and add an entry with the given hashvalue, key value, and record
270*7c478bd9Sstevel@tonic-gate  * location, to the bucket pointed to by 'hashvalue'.
271*7c478bd9Sstevel@tonic-gate  * If an entry with the same hashvalue and key value is found,
272*7c478bd9Sstevel@tonic-gate  * the entry is added after the first entry with this property.  Otherwise,
273*7c478bd9Sstevel@tonic-gate  * the entry is added to the head of the bucket.  This way, entries
274*7c478bd9Sstevel@tonic-gate  * with the same hashvalue and key are not scattered throughout the bucket
275*7c478bd9Sstevel@tonic-gate  * but they occur together. Copy is made of given key.
276*7c478bd9Sstevel@tonic-gate  */
277*7c478bd9Sstevel@tonic-gate bool_t
add(db_index_entry ** head,bool_t casein,unsigned long hval,item * i,entryp recnum)278*7c478bd9Sstevel@tonic-gate db_index_entry::add(db_index_entry **head, bool_t casein,
279*7c478bd9Sstevel@tonic-gate 			unsigned long hval, item *i, entryp recnum)
280*7c478bd9Sstevel@tonic-gate 
281*7c478bd9Sstevel@tonic-gate {
282*7c478bd9Sstevel@tonic-gate 	db_index_entry_p curr, prev, rp, save;
283*7c478bd9Sstevel@tonic-gate 
284*7c478bd9Sstevel@tonic-gate 	/* Search for it in the bucket */
285*7c478bd9Sstevel@tonic-gate 	for (prev = curr = this; curr != NULL; curr = curr->next) {
286*7c478bd9Sstevel@tonic-gate 		if (curr->hashval == hval && curr->key->equal(i, casein)) {
287*7c478bd9Sstevel@tonic-gate 			break;
288*7c478bd9Sstevel@tonic-gate 		} else {
289*7c478bd9Sstevel@tonic-gate 			prev = curr;
290*7c478bd9Sstevel@tonic-gate 		}
291*7c478bd9Sstevel@tonic-gate 	}
292*7c478bd9Sstevel@tonic-gate 
293*7c478bd9Sstevel@tonic-gate 
294*7c478bd9Sstevel@tonic-gate 
295*7c478bd9Sstevel@tonic-gate 	if (curr == NULL) {
296*7c478bd9Sstevel@tonic-gate 		/* none with same hashvalue/key found. Add to head of list. */
297*7c478bd9Sstevel@tonic-gate 		save = *head;
298*7c478bd9Sstevel@tonic-gate 		*head = new db_index_entry(hval, i, recnum, * head);
299*7c478bd9Sstevel@tonic-gate 		if (*head == NULL) {
300*7c478bd9Sstevel@tonic-gate 			*head = save;	// restore previous state
301*7c478bd9Sstevel@tonic-gate 			FATAL3(
302*7c478bd9Sstevel@tonic-gate 			"db_index_entry::add: cannot allocate space for head",
303*7c478bd9Sstevel@tonic-gate 			DB_MEMORY_LIMIT, FALSE);
304*7c478bd9Sstevel@tonic-gate 		}
305*7c478bd9Sstevel@tonic-gate 	} else {
306*7c478bd9Sstevel@tonic-gate 		/* Found same hashvalue/key.  Add entry after that one. */
307*7c478bd9Sstevel@tonic-gate 		save = prev->next;
308*7c478bd9Sstevel@tonic-gate 		prev->next = new db_index_entry(hval, i, recnum, prev->next);
309*7c478bd9Sstevel@tonic-gate 		if (prev->next == NULL) {
310*7c478bd9Sstevel@tonic-gate 			prev->next = save; // restore previous state
311*7c478bd9Sstevel@tonic-gate 			FATAL3(
312*7c478bd9Sstevel@tonic-gate 			"db_index_entry::add: cannot allocate space for entry",
313*7c478bd9Sstevel@tonic-gate 			DB_MEMORY_LIMIT, FALSE);
314*7c478bd9Sstevel@tonic-gate 		}
315*7c478bd9Sstevel@tonic-gate 	}
316*7c478bd9Sstevel@tonic-gate 
317*7c478bd9Sstevel@tonic-gate 	return (TRUE);
318*7c478bd9Sstevel@tonic-gate }
319*7c478bd9Sstevel@tonic-gate 
320*7c478bd9Sstevel@tonic-gate /* Print this entry to stdout. */
321*7c478bd9Sstevel@tonic-gate void
print()322*7c478bd9Sstevel@tonic-gate db_index_entry::print()
323*7c478bd9Sstevel@tonic-gate {
324*7c478bd9Sstevel@tonic-gate 	if (key != NULL) {
325*7c478bd9Sstevel@tonic-gate 			key->print();
326*7c478bd9Sstevel@tonic-gate 			printf("\t");
327*7c478bd9Sstevel@tonic-gate 		}
328*7c478bd9Sstevel@tonic-gate 	printf(": %d\n", location);
329*7c478bd9Sstevel@tonic-gate }
330*7c478bd9Sstevel@tonic-gate 
331*7c478bd9Sstevel@tonic-gate /* Print bucket starting with this entry. */
332*7c478bd9Sstevel@tonic-gate void
print_all()333*7c478bd9Sstevel@tonic-gate db_index_entry::print_all()
334*7c478bd9Sstevel@tonic-gate {
335*7c478bd9Sstevel@tonic-gate 	db_index_entry *np;
336*7c478bd9Sstevel@tonic-gate 	for (np = this; np != NULL; np = np->next) {
337*7c478bd9Sstevel@tonic-gate 		np->print();
338*7c478bd9Sstevel@tonic-gate 		}
339*7c478bd9Sstevel@tonic-gate }
340*7c478bd9Sstevel@tonic-gate 
341*7c478bd9Sstevel@tonic-gate /* Print result list starting with this entry. */
342*7c478bd9Sstevel@tonic-gate void
print_results()343*7c478bd9Sstevel@tonic-gate db_index_entry::print_results()
344*7c478bd9Sstevel@tonic-gate {
345*7c478bd9Sstevel@tonic-gate 	db_index_entry *np;
346*7c478bd9Sstevel@tonic-gate 	for (np = this; np != NULL; np = np->next_result) {
347*7c478bd9Sstevel@tonic-gate 		np->print();
348*7c478bd9Sstevel@tonic-gate 		}
349*7c478bd9Sstevel@tonic-gate }
350