Lines Matching defs:radix
2 * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting
12 * A radix tree is used to maintain the bitmap. Two radix constants are
18 * low. When the radix tree is searched, allocation failures in subtrees
21 * The radix tree also implements two collapsed states for meta nodes:
28 * the general radix structure optimizes both allocations and frees. The
29 * radix tree should be able to operate well no matter how much
41 * LAYOUT: The radix tree is layed out recursively using a
50 * must be encompassed in larger root-node radix.
55 * radix is large enough that this restriction does not effect the swap
134 daddr_t count, daddr_t radix, int skip);
137 daddr_t radix, int skip, daddr_t blk);
138 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
140 static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix,
144 daddr_t radix, int skip, int tab);
165 int radix;
169 * Calculate radix and skip field used for scanning.
171 radix = BLIST_BMAP_RADIX;
173 while (radix < blocks) {
174 radix <<= BLIST_META_RADIX_SHIFT;
183 bl->bl_radix = radix;
197 printf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks);
254 * blist_resize() - resize an existing radix tree to handle the
283 * blist_print() - dump radix tree
307 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
380 * blist_meta_alloc() - allocate at a meta in the radix tree.
389 blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, daddr_t radix,
403 if (scan->u.bmu_avail == radix) {
404 radix >>= BLIST_META_RADIX_SHIFT;
417 scan[i].bm_bighint = radix;
418 scan[i].u.bmu_avail = radix;
422 radix >>= BLIST_META_RADIX_SHIFT;
435 radix, next_skip - 1);
447 } else if (count > radix) {
454 blk += radix;
501 * BLST_META_FREE() - free allocated blocks from radix tree meta info
504 * The range must be entirely enclosed by this radix node. If a
512 blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix,
521 blk, radix
533 if (count != radix) {
547 /* scan->bm_bighint = radix; */
554 if (scan->u.bmu_avail == radix)
556 if (scan->u.bmu_avail > radix)
557 panic("blst_meta_free: freeing already free blocks (%d) %d/%d", count, scan->u.bmu_avail, radix);
563 radix >>= BLIST_META_RADIX_SHIFT;
565 i = (freeBlk - blk) / radix;
566 blk += i * radix;
572 v = blk + radix - freeBlk;
582 blst_meta_free(&scan[i], freeBlk, v, radix,
588 blk += radix;
594 * BLIST_RADIX_COPY() - copy one radix tree to another
600 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
610 if (radix == BLIST_BMAP_RADIX) {
634 if (scan->u.bmu_avail == radix) {
638 if (count < radix)
641 blist_free(dest, blk, radix);
645 radix >>= BLIST_META_RADIX_SHIFT;
652 if (count >= radix) {
656 radix,
659 radix
661 count -= radix;
667 radix,
675 blk += radix;
680 * BLST_RADIX_INIT() - initialize radix tree
684 * be considerably less then the calculated radix due to the large
689 blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count)
699 if (radix == BLIST_BMAP_RADIX) {
718 radix >>= BLIST_META_RADIX_SHIFT;
722 if (count >= radix) {
728 radix,
730 radix
732 count -= radix;
739 radix,
761 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab)
767 if (radix == BLIST_BMAP_RADIX) {
771 blk, radix,
783 radix
787 if (scan->u.bmu_avail == radix) {
792 radix
800 blk, radix,
802 radix,
806 radix >>= BLIST_META_RADIX_SHIFT;
815 blk, radix
823 radix,
827 blk += radix;