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