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