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