* Look for sequence of items which can be combined into a bitmap, if * multiple are present, take the one which saves most memory. * * Return (1) if a sequence was found to indicate that another call * might be able to do more. Return (0) if we found no suitable sequence. * * NB: called from alloc_unr(), no new memory allocation allowed. */
| 414 | * NB: called from alloc_unr(), no new memory allocation allowed. |
| 415 | */ |
| 416 | static int |
| 417 | optimize_unr(struct unrhdr *uh) |
| 418 | { |
| 419 | struct unr *up, *uf, *us; |
| 420 | struct unrb *ub, *ubf; |
| 421 | u_int a, l, ba; |
| 422 | |
| 423 | /* |
| 424 | * Look for the run of items (if any) which when collapsed into |
| 425 | * a bitmap would save most memory. |
| 426 | */ |
| 427 | us = NULL; |
| 428 | ba = 0; |
| 429 | TAILQ_FOREACH(uf, &uh->head, list) { |
| 430 | if (uf->len >= NBITS) |
| 431 | continue; |
| 432 | a = 1; |
| 433 | if (is_bitmap(uh, uf)) |
| 434 | a++; |
| 435 | l = uf->len; |
| 436 | up = uf; |
| 437 | while (1) { |
| 438 | up = TAILQ_NEXT(up, list); |
| 439 | if (up == NULL) |
| 440 | break; |
| 441 | if ((up->len + l) > NBITS) |
| 442 | break; |
| 443 | a++; |
| 444 | if (is_bitmap(uh, up)) |
| 445 | a++; |
| 446 | l += up->len; |
| 447 | } |
| 448 | if (a > ba) { |
| 449 | ba = a; |
| 450 | us = uf; |
| 451 | } |
| 452 | } |
| 453 | if (ba < 3) |
| 454 | return (0); |
| 455 | |
| 456 | /* |
| 457 | * If the first element is not a bitmap, make it one. |
| 458 | * Trying to do so without allocating more memory complicates things |
| 459 | * a bit |
| 460 | */ |
| 461 | if (!is_bitmap(uh, us)) { |
| 462 | uf = TAILQ_NEXT(us, list); |
| 463 | TAILQ_REMOVE(&uh->head, us, list); |
| 464 | a = us->len; |
| 465 | l = us->ptr == uh ? 1 : 0; |
| 466 | ub = (void *)us; |
| 467 | bit_nclear(ub->map, 0, NBITS - 1); |
| 468 | if (l) |
| 469 | bit_nset(ub->map, 0, a); |
| 470 | if (!is_bitmap(uh, uf)) { |
| 471 | if (uf->ptr == NULL) |
| 472 | bit_nclear(ub->map, a, a + uf->len - 1); |
| 473 | else |
no test coverage detected