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