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 (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 22 /* 23 * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 #include <sgs.h> 27 #include <string.h> 28 #include <stdio.h> 29 #include <sys/debug.h> 30 31 /* 32 * Alist manipulation. An Alist is a list of elements formed into an array. 33 * Traversal of the list is an array scan, which because of the locality of 34 * each reference is probably more efficient than a link-list traversal. 35 * 36 * See alist.h for more background information about array lists. 37 */ 38 39 /* 40 * Insert a value into an array at a specified index: 41 * 42 * alist_insert(): Insert an item into an Alist at the specified index 43 * alist_insert_by_offset(): Insert an item into an Alist at the 44 * specified offset relative to the list address. 45 * aplist_insert() Insert a pointer into an APlist at the specified index 46 * 47 * entry: 48 * Note: All the arguments for all three routines are listed here. 49 * The routine to which a given argument applies is given with 50 * each description. 51 * 52 * llp [all] - Address of a pointer to an Alist/APlist. The pointer should 53 * be initialized to NULL before its first use. 54 * datap [alist_insert / aplist_insert] - Pointer to item data, or 55 * NULL. If non-null the data referenced is copied into the 56 * Alist item. Otherwise, the list item is zeroed, and 57 * further initialization is left to the caller. 58 * ptr [aplist_insert] - Pointer to be inserted. 59 * size [alist_insert / alist_insert_by_offset] - Size of an item 60 * in the array list, in bytes. As with any array, A given 61 * Alist can support any item size, but every item in that 62 * list must have the same size. 63 * init_arritems [all] - Initial allocation size: On the first insertion 64 * into the array list, room for init_arritems items is allocated. 65 * idx [alist_insert / aplist_insert] - Index at which to insert the 66 * new item. This index must lie within the existing list, 67 * or be the next index following. 68 * off [alist_insert_by_offset] - Offset at which to insert the new 69 * item, based from the start of the Alist. The offset of 70 * the first item is ALIST_OFF_DATA. 71 * 72 * exit: 73 * The item is inserted at the specified position. This operation 74 * can cause memory for the list to be allocated, or reallocated, 75 * either of which will cause the value of the list pointer 76 * to change. 77 * 78 * These routines can only fail if unable to allocate memory, 79 * in which case NULL is returned. 80 * 81 * If a pointer list (aplist_insert), then the pointer 82 * is stored in the requested index. On success, the address 83 * of the pointer within the list is returned. 84 * 85 * If the list contains arbitrary data (not aplist_insert): If datap 86 * is non-NULL, the data it references is copied into the item at 87 * the index. If datap is NULL, the specified item is zeroed. 88 * On success, a pointer to the inserted item is returned. 89 * 90 * The caller must not retain the returned pointer from this 91 * routine across calls to the list module. It is only safe to use 92 * it until the next call to this module for the given list. 93 * 94 */ 95 void * 96 alist_insert(Alist **lpp, const void *datap, size_t size, 97 Aliste init_arritems, Aliste idx) 98 { 99 Alist *lp = *lpp; 100 char *addr; 101 102 /* The size and initial array count need to be non-zero */ 103 ASSERT(init_arritems != 0); 104 ASSERT(size != 0); 105 106 if (lp == NULL) { 107 Aliste bsize; 108 109 /* 110 * First time here, allocate a new Alist. Note that the 111 * Alist al_desc[] entry is defined for 1 element, 112 * but we actually allocate the number we need. 113 */ 114 bsize = size * init_arritems; 115 bsize = S_ROUND(bsize, sizeof (void *)); 116 bsize = ALIST_OFF_DATA + bsize; 117 if ((lp = malloc((size_t)bsize)) == NULL) 118 return (NULL); 119 lp->al_arritems = init_arritems; 120 lp->al_nitems = 0; 121 lp->al_next = ALIST_OFF_DATA; 122 lp->al_size = size; 123 *lpp = lp; 124 } else { 125 /* We must get the same value for size every time */ 126 ASSERT(size == lp->al_size); 127 128 if (lp->al_nitems >= lp->al_arritems) { 129 /* 130 * The list is full: Increase the memory allocation 131 * by doubling it. 132 */ 133 Aliste bsize; 134 135 bsize = lp->al_size * lp->al_arritems * 2; 136 bsize = S_ROUND(bsize, sizeof (void *)); 137 bsize = ALIST_OFF_DATA + bsize; 138 if ((lp = realloc((void *)lp, (size_t)bsize)) == 0) 139 return (NULL); 140 lp->al_arritems *= 2; 141 *lpp = lp; 142 } 143 } 144 145 /* 146 * The caller is not supposed to use an index that 147 * would introduce a "hole" in the array. 148 */ 149 ASSERT(idx <= lp->al_nitems); 150 151 addr = (idx * lp->al_size) + (char *)lp->al_data; 152 153 /* 154 * An appended item is added to the next available array element. 155 * An insert at any other spot requires that the data items that 156 * exist at the point of insertion be shifted down to open a slot. 157 */ 158 if (idx < lp->al_nitems) 159 (void) memmove(addr + lp->al_size, addr, 160 (lp->al_nitems - idx) * lp->al_size); 161 162 lp->al_nitems++; 163 lp->al_next += lp->al_size; 164 if (datap != NULL) 165 (void) memcpy(addr, datap, lp->al_size); 166 else 167 (void) memset(addr, 0, lp->al_size); 168 return (addr); 169 } 170 171 void * 172 alist_insert_by_offset(Alist **lpp, const void *datap, size_t size, 173 Aliste init_arritems, Aliste off) 174 { 175 Aliste idx; 176 177 if (*lpp == NULL) { 178 ASSERT(off == ALIST_OFF_DATA); 179 idx = 0; 180 } else { 181 idx = (off - ALIST_OFF_DATA) / (*lpp)->al_size; 182 } 183 184 return (alist_insert(lpp, datap, size, init_arritems, idx)); 185 } 186 187 void * 188 aplist_insert(APlist **lpp, const void *ptr, Aliste init_arritems, Aliste idx) 189 { 190 APlist *lp = *lpp; 191 192 /* The initial array count needs to be non-zero */ 193 ASSERT(init_arritems != 0); 194 195 if (lp == NULL) { 196 Aliste bsize; 197 198 /* 199 * First time here, allocate a new APlist. Note that the 200 * APlist apl_desc[] entry is defined for 1 element, 201 * but we actually allocate the number we need. 202 */ 203 bsize = APLIST_OFF_DATA + (sizeof (void *) * init_arritems); 204 if ((lp = malloc((size_t)bsize)) == NULL) 205 return (NULL); 206 lp->apl_arritems = init_arritems; 207 lp->apl_nitems = 0; 208 *lpp = lp; 209 } else if (lp->apl_nitems >= lp->apl_arritems) { 210 /* 211 * The list is full: Increase the memory allocation 212 * by doubling it. 213 */ 214 Aliste bsize; 215 216 bsize = APLIST_OFF_DATA + 217 (2 * sizeof (void *) * lp->apl_arritems); 218 if ((lp = realloc((void *)lp, (size_t)bsize)) == 0) 219 return (NULL); 220 lp->apl_arritems *= 2; 221 *lpp = lp; 222 } 223 224 /* 225 * The caller is not supposed to use an index that 226 * would introduce a "hole" in the array. 227 */ 228 ASSERT(idx <= lp->apl_nitems); 229 230 /* 231 * An appended item is added to the next available array element. 232 * An insert at any other spot requires that the data items that 233 * exist at the point of insertion be shifted down to open a slot. 234 */ 235 if (idx < lp->apl_nitems) 236 (void) memmove((char *)&lp->apl_data[idx + 1], 237 (char *)&lp->apl_data[idx], 238 (lp->apl_nitems - idx) * sizeof (void *)); 239 240 lp->apl_nitems++; 241 lp->apl_data[idx] = (void *)ptr; 242 return (&lp->apl_data[idx]); 243 } 244 245 /* 246 * Append a value to a list. These are convenience wrappers on top 247 * of the insert operation. See the description of those routine above 248 * for details. 249 */ 250 void * 251 alist_append(Alist **lpp, const void *datap, size_t size, 252 Aliste init_arritems) 253 { 254 Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->al_nitems; 255 256 return (alist_insert(lpp, datap, size, init_arritems, ndx)); 257 } 258 259 void * 260 aplist_append(APlist **lpp, const void *ptr, Aliste init_arritems) 261 { 262 Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->apl_nitems; 263 264 return (aplist_insert(lpp, ptr, init_arritems, ndx)); 265 } 266 267 /* 268 * Delete the item at a specified index/offset, and decrement the variable 269 * containing the index: 270 * 271 * alist_delete - Delete an item from an Alist at the specified 272 * index. 273 * alist_delete_by_offset - Delete an item from an Alist at the 274 * specified offset from the list pointer. 275 * aplist_delete - Delete a pointer from an APlist at the specified 276 * index. 277 * 278 * entry: 279 * alp - List to delete item from 280 * idxp - Address of variable containing the index of the 281 * item to delete. 282 * offp - Address of variable containing the offset of the 283 * item to delete. 284 * 285 * exit: 286 * The item at the position given by (*idxp) or (*offp), depending 287 * on the routine, is removed from the list. Then, the position 288 * variable (*idxp or *offp) is decremented by one item. This is done 289 * to facilitate use of this routine within a TRAVERSE loop. 290 * 291 * note: 292 * Deleting the last element in an array list is cheap, but 293 * deleting any other item causes a memory copy to occur to 294 * move the following items up. If you intend to traverse the 295 * entire list, deleting every item as you go, it will be cheaper 296 * to omit the delete within the traverse, and then call 297 * the reset function reset() afterwards. 298 */ 299 void 300 alist_delete(Alist *lp, Aliste *idxp) 301 { 302 Aliste idx = *idxp; 303 304 305 /* The list must be allocated and the index in range */ 306 ASSERT(lp != NULL); 307 ASSERT(idx < lp->al_nitems); 308 309 /* 310 * If the element to be removed is not the last entry of the array, 311 * slide the following elements over the present element. 312 */ 313 if (idx < --lp->al_nitems) { 314 char *addr = (idx * lp->al_size) + (char *)lp->al_data; 315 316 (void) memmove(addr, addr + lp->al_size, 317 (lp->al_nitems - idx) * lp->al_size); 318 } 319 lp->al_next -= lp->al_size; 320 321 /* Decrement the callers index variable */ 322 (*idxp)--; 323 } 324 325 void 326 alist_delete_by_offset(Alist *lp, Aliste *offp) 327 { 328 Aliste idx; 329 330 ASSERT(lp != NULL); 331 idx = (*offp - ALIST_OFF_DATA) / lp->al_size; 332 333 alist_delete(lp, &idx); 334 *offp -= lp->al_size; 335 } 336 337 void 338 aplist_delete(APlist *lp, Aliste *idxp) 339 { 340 Aliste idx = *idxp; 341 342 343 /* The list must be allocated and the index in range */ 344 ASSERT(lp != NULL); 345 ASSERT(idx < lp->apl_nitems); 346 347 /* 348 * If the element to be removed is not the last entry of the array, 349 * slide the following elements over the present element. 350 */ 351 if (idx < --lp->apl_nitems) 352 (void) memmove(&lp->apl_data[idx], &lp->apl_data[idx + 1], 353 (lp->apl_nitems - idx) * sizeof (void *)); 354 355 /* Decrement the callers index variable */ 356 (*idxp)--; 357 } 358 359 /* 360 * Delete the pointer with a specified value from the APlist. 361 * 362 * entry: 363 * lp - Initialized APlist to delete item from 364 * ptr - Pointer to be deleted. 365 * 366 * exit: 367 * The list is searched for an item containing the given pointer, 368 * and if a match is found, that item is delted and True (1) returned. 369 * If no match is found, then False (0) is returned. 370 * 371 * note: 372 * See note for delete operation, above. 373 */ 374 int 375 aplist_delete_value(APlist *lp, const void *ptr) 376 { 377 size_t idx; 378 379 /* 380 * If the pointer is found in the list, use aplist_delete to 381 * remove it, and we're done. 382 */ 383 for (idx = 0; idx < lp->apl_nitems; idx++) 384 if (ptr == lp->apl_data[idx]) { 385 aplist_delete(lp, &idx); 386 return (1); 387 } 388 389 /* If we get here, the item was not in the list */ 390 return (0); 391 } 392 393 /* 394 * Search the APlist for an element with a given value, and 395 * if not found, optionally append the element to the end of the list. 396 * 397 * entry: 398 * lpp, ptr - As per aplist_insert(). 399 * init_arritems - As per aplist_insert() if a non-zero value. 400 * A value of zero is special, and is taken to indicate 401 * that no insert operation should be performed if 402 * the item is not found in the list. 403 * 404 * exit 405 * The given item is compared to every item in the given APlist. 406 * If it is found, ALE_EXISTS is returned. 407 * 408 * If it is not found: If init_arr_items is False (0), then 409 * ALE_NOTFOUND is returned. If init_arr_items is True, then 410 * the item is appended to the list, and ALE_CREATE returned on success. 411 * 412 * On failure, which can only occur due to memory allocation failure, 413 * ALE_ALLOCFAIL is returned. 414 * 415 * note: 416 * The test operation used by this routine is a linear 417 * O(N) operation, and is not efficient for more than a 418 * few items. 419 */ 420 aplist_test_t 421 aplist_test(APlist **lpp, const void *ptr, Aliste init_arritems) 422 { 423 APlist *lp = *lpp; 424 size_t idx; 425 426 /* Is the pointer already in the list? */ 427 if (lp != NULL) 428 for (idx = 0; idx < lp->apl_nitems; idx++) 429 if (ptr == lp->apl_data[idx]) 430 return (ALE_EXISTS); 431 432 /* Is this a no-insert case? If so, report that the item is not found */ 433 if (init_arritems == 0) 434 return (ALE_NOTFND); 435 436 /* Add it to the end of the list */ 437 if (aplist_append(lpp, ptr, init_arritems) == NULL) 438 return (ALE_ALLOCFAIL); 439 return (ALE_CREATE); 440 } 441 442 /* 443 * Reset the given list to its empty state. Any memory allocated by the 444 * list is preserved, ready for reuse, but the list is set to its 445 * empty state, equivalent to having called the delete operation for 446 * every item. 447 * 448 * Note that no cleanup of the discarded items is done. The caller must 449 * take care of any necessary cleanup before calling aplist_reset(). 450 */ 451 void 452 alist_reset(Alist *lp) 453 { 454 if (lp != NULL) { 455 lp->al_nitems = 0; 456 lp->al_next = ALIST_OFF_DATA; 457 } 458 } 459 460 void 461 aplist_reset(APlist *lp) 462 { 463 if (lp != NULL) 464 lp->apl_nitems = 0; 465 } 466