Subversion Repositories HelenOS-historic

Rev

Rev 1248 | Rev 1549 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1200 jermar 1 
/*
2 
 * Copyright (C) 2006 Jakub Jermar
3 
 * All rights reserved.
4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
8 
 *
9 
 * - Redistributions of source code must retain the above copyright
10 
 *   notice, this list of conditions and the following disclaimer.
11 
 * - Redistributions in binary form must reproduce the above copyright
12 
 *   notice, this list of conditions and the following disclaimer in the
13 
 *   documentation and/or other materials provided with the distribution.
14 
 * - The name of the author may not be used to endorse or promote products
15 
 *   derived from this software without specific prior written permission.
16 
 *
17 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
 */
28 
 
1248 jermar 29 
/**
30 
 * @file    bitmap.c
31 
 * @brief   Implementation of bitmap ADT.
32 
 *
33 
 * This file implements bitmap ADT and provides functions for
34 
 * setting and clearing ranges of bits.
35 
 */
36 
 
1200 jermar 37 
#include <adt/bitmap.h>
38 
#include <typedefs.h>
39 
#include <arch/types.h>
40 
#include <align.h>
41 
#include <debug.h>
1262 jermar 42 
#include <macros.h>
1200 jermar 43 
 
44 
#define ALL_ONES    0xff
45 
#define ALL_ZEROES  0x00
46 
 
47 
/** Initialize bitmap.
48 
 *
49 
 * No portion of the bitmap is set or cleared by this function.
50 
 *
51 
 * @param bitmap Bitmap structure.
52 
 * @param map Address of the memory used to hold the map.
53 
 * @param bits Number of bits stored in bitmap.
54 
 */
55 
void bitmap_initialize(bitmap_t *bitmap, __u8 *map, count_t bits)
56 
{
57 
    bitmap->map = map;
58 
    bitmap->bits = bits;
59 
}
60 
 
61 
/** Set range of bits.
62 
 *
63 
 * @param bitmap Bitmap structure.
64 
 * @param start Starting bit.
65 
 * @param bits Number of bits to set.
66 
 */
67 
void bitmap_set_range(bitmap_t *bitmap, index_t start, count_t bits)
68 
{
69 
    index_t i;
70 
    index_t aligned_start;
71 
    count_t lub;        /* leading unaligned bits */
1262 jermar 72 
    count_t amb;        /* aligned middle bits */
73 
    count_t tab;        /* trailing aligned bits */
1200 jermar 74 
 
75 
    ASSERT(start + bits <= bitmap->bits);
76 
 
77 
    aligned_start = ALIGN_UP(start, 8);
1262 jermar 78 
    lub = min(aligned_start - start, bits);
79 
    amb = bits > lub ? bits - lub : 0;
80 
    tab = amb % 8;
1200 jermar 81 
 
82 
    if (lub) {
83 
        /*
84 
         * Make sure to set any leading unaligned bits.
85 
         */
86 
        bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1);
87 
    }
1262 jermar 88 
    for (i = 0; i < amb / 8; i++) {
1200 jermar 89 
        /*
90 
         * The middle bits can be set byte by byte.
91 
         */
92 
        bitmap->map[aligned_start / 8 + i] = ALL_ONES;
93 
    }
1262 jermar 94 
    if (tab) {
1200 jermar 95 
        /*
1262 jermar 96 
         * Make sure to set any trailing aligned bits.
1200 jermar 97 
         */
1262 jermar 98 
        bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1;
1200 jermar 99 
    }
100 
 
101 
}
102 
 
103 
/** Clear range of bits.
104 
 *
105 
 * @param bitmap Bitmap structure.
106 
 * @param start Starting bit.
107 
 * @param bits Number of bits to clear.
108 
 */
109 
void bitmap_clear_range(bitmap_t *bitmap, index_t start, count_t bits)
110 
{
111 
    index_t i;
112 
    index_t aligned_start;
113 
    count_t lub;        /* leading unaligned bits */
1262 jermar 114 
    count_t amb;        /* aligned middle bits */
115 
    count_t tab;        /* trailing aligned bits */
1200 jermar 116 
 
117 
    ASSERT(start + bits <= bitmap->bits);
118 
 
119 
    aligned_start = ALIGN_UP(start, 8);
1262 jermar 120 
    lub = min(aligned_start - start, bits);
121 
    amb = bits > lub ? bits - lub : 0;
122 
    tab = amb % 8;
123 
 
1200 jermar 124 
    if (lub) {
125 
        /*
126 
         * Make sure to clear any leading unaligned bits.
127 
         */
128 
        bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;
129 
    }
1262 jermar 130 
    for (i = 0; i < amb / 8; i++) {
1200 jermar 131 
        /*
132 
         * The middle bits can be cleared byte by byte.
133 
         */
134 
        bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;
135 
    }
1262 jermar 136 
    if (tab) {
1200 jermar 137 
        /*
1262 jermar 138 
         * Make sure to clear any trailing aligned bits.
1200 jermar 139 
         */
1262 jermar 140 
        bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1);
1200 jermar 141 
    }
1262 jermar 142 
 
1200 jermar 143 
}
144 
 
145 
/** Copy portion of one bitmap into another bitmap.
146 
 *
147 
 * @param dst Destination bitmap.
148 
 * @param src Source bitmap.
149 
 * @param bits Number of bits to copy.
150 
 */
151 
void bitmap_copy(bitmap_t *dst, bitmap_t *src, count_t bits)
152 
{
153 
    index_t i;
154 
 
155 
    ASSERT(bits <= dst->bits);
156 
    ASSERT(bits <= src->bits);
157 
 
158 
    for (i = 0; i < bits / 8; i++)
159 
        dst->map[i] = src->map[i];
160 
 
161 
    if (bits % 8) {
162 
        bitmap_clear_range(dst, i * 8, bits % 8);
163 
        dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1);
164 
    }
165 
}