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. */ 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 */ 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 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 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 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 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 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 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 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 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 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 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