Lines Matching defs:radix
30 * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting
37 * A radix tree is used to maintain the bitmap. Two radix constants are
43 * low. When the radix tree is searched, allocation failures in subtrees
46 * The radix tree also implements two collapsed states for meta nodes:
53 * the general radix structure optimizes both allocations and frees. The
54 * radix tree should be able to operate well no matter how much
66 * LAYOUT: The radix tree is laid out recursively using a
75 * must be encompassed in larger root-node radix.
80 * radix is large enough that this restriction does not affect the swap
139 blist_blkno_t bl_radix; /* coverage radix */
142 blmeta_t *bl_root; /* root of radix tree */
155 blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip);
158 blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip,
160 static void blst_copy(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix,
164 blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip,
166 static blist_blkno_t blst_radix_init(blmeta_t *scan, blist_blkno_t radix,
170 blist_blkno_t radix, blist_blkno_t skip, int tab);
187 blist_blkno_t radix;
191 * Calculate radix and skip field used for scanning.
195 radix = BLIST_BMAP_RADIX;
197 while (radix < blocks) {
198 radix *= BLIST_META_RADIX;
205 bl->bl_radix = radix;
219 printf("BLIST raw radix tree contains %" PRIu64 " records\n",
300 * blist_resize() - resize an existing radix tree to handle the
330 * blist_print() - dump radix tree
354 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
430 * blist_meta_alloc() - allocate at a meta in the radix tree.
443 blist_blkno_t radix,
457 if (scan->u.bmu_avail == radix) {
458 radix /= BLIST_META_RADIX;
471 scan[i].bm_bighint = radix;
472 scan[i].u.bmu_avail = radix;
476 radix /= BLIST_META_RADIX;
493 r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1);
501 } else if (count > radix) {
508 blk += radix;
558 * BLST_META_FREE() - free allocated blocks from radix tree meta info
561 * The range must be entirely enclosed by this radix node. If a
573 blist_blkno_t radix,
584 (uint64_t)blk, (uint64_t)radix
596 if (count != radix) {
611 /* scan->bm_bighint = radix; */
618 if (scan->u.bmu_avail == radix)
620 if (scan->u.bmu_avail > radix)
625 (uint64_t)radix);
631 radix /= BLIST_META_RADIX;
633 i = (freeBlk - blk) / radix;
634 blk += i * radix;
640 v = blk + radix - freeBlk;
650 blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
656 blk += radix;
662 * BLIST_RADIX_COPY() - copy one radix tree to another
671 blist_blkno_t radix,
683 if (radix == BLIST_BMAP_RADIX) {
709 if (scan->u.bmu_avail == radix) {
713 if (count < radix)
716 blist_free(dest, blk, radix);
721 radix /= BLIST_META_RADIX;
728 if (count >= radix) {
732 radix,
735 radix
737 count -= radix;
743 radix,
751 blk += radix;
795 blist_blkno_t radix,
803 if (count == radix || scan->u.bmu_avail == 0) {
813 if (count > radix)
816 if (scan->u.bmu_avail == radix) {
817 radix /= BLIST_META_RADIX;
829 scan[i].bm_bighint = radix;
830 scan[i].u.bmu_avail = radix;
834 radix /= BLIST_META_RADIX;
837 i = (allocBlk - blk) / radix;
838 blk += i * radix;
844 v = blk + radix - allocBlk;
855 radix, next_skip - 1, blk);
859 blk += radix;
867 * BLST_RADIX_INIT() - initialize radix tree
871 * be considerably less than the calculated radix due to the large
872 * RADIX values we use.
876 blst_radix_init(blmeta_t *scan, blist_blkno_t radix, blist_blkno_t skip,
887 if (radix == BLIST_BMAP_RADIX) {
906 radix /= BLIST_META_RADIX;
910 if (count >= radix) {
916 radix,
918 radix
920 count -= radix;
927 radix,
949 blst_radix_print(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix,
956 if (radix == BLIST_BMAP_RADIX) {
963 (uint64_t)radix,
977 (uint64_t)radix
981 if (scan->u.bmu_avail == radix) {
987 (uint64_t)radix
998 (uint64_t)radix,
1000 (uint64_t)radix,
1004 radix /= BLIST_META_RADIX;
1015 (uint64_t)radix
1023 radix,
1027 blk += radix;
Indexes created Thu Sep 25 16:09:42 GMT 2025