Changeset f7bb6d1 in mainline for kernel/generic/src/adt/bitmap.c


Ignore:
Timestamp:
2013-09-17T19:51:20Z (11 years ago)
Author:
Jakub Klama <jakub.klama@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
6ac3d27
Parents:
3efc35a (diff), ca62f86 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge from launchpad branch.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/adt/bitmap.c

    r3efc35a rf7bb6d1  
    3535 *
    3636 * This file implements bitmap ADT and provides functions for
    37  * setting and clearing ranges of bits.
     37 * setting and clearing ranges of bits and for finding ranges
     38 * of unset bits.
     39 *
     40 * The bitmap ADT can optionally implement a two-level hierarchy
     41 * for faster range searches. The second level bitmap (of blocks)
     42 * is not precise, but conservative. This means that if the block
     43 * bit is set, it guarantees that all bits in the block are set.
     44 * But if the block bit is unset, nothing can be said about the
     45 * bits in the block.
     46 *
    3847 */
    3948
    … …  
    4453#include <macros.h>
    4554
    46 #define ALL_ONES        0xff
    47 #define ALL_ZEROES      0x00
     55#define ALL_ONES    0xff
     56#define ALL_ZEROES  0x00
     57
     58/** Get bitmap size
     59 *
     60 * Return the size (in bytes) required for the bitmap.
     61 *
     62 * @param elements   Number bits stored in bitmap.
     63 * @param block_size Block size of the 2nd level bitmap.
     64 *                   If set to zero, no 2nd level is used.
     65 *
     66 * @return Size (in bytes) required for the bitmap.
     67 *
     68 */
     69size_t bitmap_size(size_t elements, size_t block_size)
     70{
     71        size_t size = elements / BITMAP_ELEMENT;
     72       
     73        if ((elements % BITMAP_ELEMENT) != 0)
     74                size++;
     75       
     76        if (block_size > 0) {
     77                size += elements / block_size;
     78               
     79                if ((elements % block_size) != 0)
     80                        size++;
     81        }
     82       
     83        return size;
     84}
    4885
    4986/** Initialize bitmap.
    … …  
    5188 * No portion of the bitmap is set or cleared by this function.
    5289 *
    53  * @param bitmap        Bitmap structure.
    54  * @param map           Address of the memory used to hold the map.
    55  * @param bits          Number of bits stored in bitmap.
    56  */
    57 void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits)
    58 {
    59         bitmap->map = map;
    60         bitmap->bits = bits;
    61 }
    62 
    63 /** Set range of bits.
    64  *
    65  * @param bitmap        Bitmap structure.
    66  * @param start         Starting bit.
    67  * @param bits          Number of bits to set.
    68  */
    69 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits)
    70 {
    71         size_t i = 0;
    72         size_t aligned_start;
    73         size_t lub;     /* leading unaligned bits */
    74         size_t amb;     /* aligned middle bits */
    75         size_t tab;     /* trailing aligned bits */
    76        
    77         ASSERT(start + bits <= bitmap->bits);
    78        
    79         aligned_start = ALIGN_UP(start, 8);
    80         lub = min(aligned_start - start, bits);
    81         amb = bits > lub ? bits - lub : 0;
    82         tab = amb % 8;
    83        
    84         if (!bits)
    85                 return;
    86 
    87         if (start + bits < aligned_start) {
     90 * @param bitmap     Bitmap structure.
     91 * @param elements   Number of bits stored in bitmap.
     92 * @param block_size Block size of the 2nd level bitmap.
     93 *                   If set to zero, no 2nd level is used.
     94 * @param data       Address of the memory used to hold the map.
     95 *                   The optional 2nd level bitmap follows the 1st
     96 *                   level bitmap.
     97 *
     98 */
     99void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size,
     100    void *data)
     101{
     102        bitmap->elements = elements;
     103        bitmap->bits = (uint8_t *) data;
     104       
     105        if (block_size > 0) {
     106                bitmap->block_size = block_size;
     107                bitmap->blocks = bitmap->bits +
     108                    bitmap_size(elements, 0);
     109        } else {
     110                bitmap->block_size = 0;
     111                bitmap->blocks = NULL;
     112        }
     113}
     114
     115static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count)
     116{
     117        if (count == 0)
     118                return;
     119       
     120        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
     121       
     122        /* Leading unaligned bits */
     123        size_t lub = min(aligned_start - start, count);
     124       
     125        /* Aligned middle bits */
     126        size_t amb = (count > lub) ? (count - lub) : 0;
     127       
     128        /* Trailing aligned bits */
     129        size_t tab = amb % BITMAP_ELEMENT;
     130       
     131        if (start + count < aligned_start) {
    88132                /* Set bits in the middle of byte. */
    89                 bitmap->map[start / 8] |= ((1 << lub) - 1) << (start & 7);
     133                bits[start / BITMAP_ELEMENT] |=
     134                    ((1 << lub) - 1) << (start & BITMAP_REMAINER);
    90135                return;
    91136        }
    … …  
    93138        if (lub) {
    94139                /* Make sure to set any leading unaligned bits. */
    95                 bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1);
    96         }
    97         for (i = 0; i < amb / 8; i++) {
     140                bits[start / BITMAP_ELEMENT] |=
     141                    ~((1 << (BITMAP_ELEMENT - lub)) - 1);
     142        }
     143       
     144        size_t i;
     145       
     146        for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
    98147                /* The middle bits can be set byte by byte. */
    99                 bitmap->map[aligned_start / 8 + i] = ALL_ONES;
    100         }
     148                bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES;
     149        }
     150       
    101151        if (tab) {
    102152                /* Make sure to set any trailing aligned bits. */
    103                 bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1;
    104         }
    105        
    106 }
    107 
    108 /** Clear range of bits.
    109  *
    110  * @param bitmap        Bitmap structure.
    111  * @param start         Starting bit.
    112  * @param bits          Number of bits to clear.
    113  */
    114 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits)
    115 {
    116         size_t i = 0;
    117         size_t aligned_start;
    118         size_t lub;     /* leading unaligned bits */
    119         size_t amb;     /* aligned middle bits */
    120         size_t tab;     /* trailing aligned bits */
    121        
    122         ASSERT(start + bits <= bitmap->bits);
    123        
    124         aligned_start = ALIGN_UP(start, 8);
    125         lub = min(aligned_start - start, bits);
    126         amb = bits > lub ? bits - lub : 0;
    127         tab = amb % 8;
    128 
    129         if (!bits)
    130                 return;
    131 
    132         if (start + bits < aligned_start) {
     153                bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1;
     154        }
     155}
     156
     157/** Set range of bits.
     158 *
     159 * @param bitmap Bitmap structure.
     160 * @param start  Starting bit.
     161 * @param count  Number of bits to set.
     162 *
     163 */
     164void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)
     165{
     166        ASSERT(start + count <= bitmap->elements);
     167       
     168        bitmap_set_range_internal(bitmap->bits, start, count);
     169       
     170        if (bitmap->block_size > 0) {
     171                size_t aligned_start = ALIGN_UP(start, bitmap->block_size);
     172               
     173                /* Leading unaligned bits */
     174                size_t lub = min(aligned_start - start, count);
     175               
     176                /* Aligned middle bits */
     177                size_t amb = (count > lub) ? (count - lub) : 0;
     178               
     179                size_t aligned_size = amb / bitmap->block_size;
     180               
     181                bitmap_set_range_internal(bitmap->blocks, aligned_start,
     182                    aligned_size);
     183        }
     184}
     185
     186static void bitmap_clear_range_internal(uint8_t *bits, size_t start,
     187    size_t count)
     188{
     189        if (count == 0)
     190                return;
     191       
     192        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
     193       
     194        /* Leading unaligned bits */
     195        size_t lub = min(aligned_start - start, count);
     196       
     197        /* Aligned middle bits */
     198        size_t amb = (count > lub) ? (count - lub) : 0;
     199       
     200        /* Trailing aligned bits */
     201        size_t tab = amb % BITMAP_ELEMENT;
     202       
     203        if (start + count < aligned_start) {
    133204                /* Set bits in the middle of byte */
    134                 bitmap->map[start / 8] &= ~(((1 << lub) - 1) << (start & 7));
    135                 return;
    136         }
    137 
     205                bits[start / BITMAP_ELEMENT] &=
     206                    ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
     207                return;
     208        }
     209       
    138210        if (lub) {
    139211                /* Make sure to clear any leading unaligned bits. */
    140                 bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;
    141         }
    142         for (i = 0; i < amb / 8; i++) {
     212                bits[start / BITMAP_ELEMENT] &=
     213                    (1 << (BITMAP_ELEMENT - lub)) - 1;
     214        }
     215       
     216        size_t i;
     217       
     218        for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
    143219                /* The middle bits can be cleared byte by byte. */
    144                 bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;
    145         }
     220                bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES;
     221        }
     222       
    146223        if (tab) {
    147224                /* Make sure to clear any trailing aligned bits. */
    148                 bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1);
    149         }
    150 
     225                bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1);
     226        }
     227}
     228
     229/** Clear range of bits.
     230 *
     231 * @param bitmap Bitmap structure.
     232 * @param start  Starting bit.
     233 * @param count  Number of bits to clear.
     234 *
     235 */
     236void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
     237{
     238        ASSERT(start + count <= bitmap->elements);
     239       
     240        bitmap_clear_range_internal(bitmap->bits, start, count);
     241       
     242        if (bitmap->block_size > 0) {
     243                size_t aligned_start = start / bitmap->block_size;
     244               
     245                size_t aligned_end = (start + count) / bitmap->block_size;
     246               
     247                if (((start + count) % bitmap->block_size) != 0)
     248                        aligned_end++;
     249               
     250                size_t aligned_size = aligned_end - aligned_start;
     251               
     252                bitmap_clear_range_internal(bitmap->blocks, aligned_start,
     253                    aligned_size);
     254        }
    151255}
    152256
    153257/** Copy portion of one bitmap into another bitmap.
    154258 *
    155  * @param dst           Destination bitmap.
    156  * @param src           Source bitmap.
    157  * @param bits          Number of bits to copy.
    158  */
    159 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits)
    160 {
     259 * @param dst   Destination bitmap.
     260 * @param src   Source bitmap.
     261 * @param count Number of bits to copy.
     262 *
     263 */
     264void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count)
     265{
     266        ASSERT(count <= dst->elements);
     267        ASSERT(count <= src->elements);
     268       
    161269        size_t i;
    162270       
    163         ASSERT(bits <= dst->bits);
    164         ASSERT(bits <= src->bits);
    165        
    166         for (i = 0; i < bits / 8; i++)
    167                 dst->map[i] = src->map[i];
    168        
    169         if (bits % 8) {
    170                 bitmap_clear_range(dst, i * 8, bits % 8);
    171                 dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1);
     271        for (i = 0; i < count / BITMAP_ELEMENT; i++)
     272                dst->bits[i] = src->bits[i];
     273       
     274        if (count % BITMAP_ELEMENT) {
     275                bitmap_clear_range(dst, i * BITMAP_ELEMENT,
     276                    count % BITMAP_ELEMENT);
     277                dst->bits[i] |= src->bits[i] &
     278                    ((1 << (count % BITMAP_ELEMENT)) - 1);
    172279        }
    173280}
Note: See TracChangeset for help on using the changeset viewer.