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