WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/adt/bitmap.c


/*
 * Copyright (C) 2006 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/**
 * @file    bitmap.c
 * @brief   Implementation of bitmap ADT.
 *
 * This file implements bitmap ADT and provides functions for
 * setting and clearing ranges of bits.
 */
 
#include <adt/bitmap.h>
#include <typedefs.h>
#include <arch/types.h>
#include <align.h>
#include <debug.h>
 
#define ALL_ONES    0xff
#define ALL_ZEROES  0x00
 
/** Initialize bitmap.
 *
 * No portion of the bitmap is set or cleared by this function.
 *
 * @param bitmap Bitmap structure.
 * @param map Address of the memory used to hold the map.
 * @param bits Number of bits stored in bitmap.
 */
void bitmap_initialize(bitmap_t *bitmap, __u8 *map, count_t bits)
{
    bitmap->map = map;
    bitmap->bits = bits;
}
 
/** Set range of bits.
 *
 * @param bitmap Bitmap structure.
 * @param start Starting bit.
 * @param bits Number of bits to set.
 */
void bitmap_set_range(bitmap_t *bitmap, index_t start, count_t bits)
{
    index_t i;
    index_t aligned_start;
    count_t lub;        /* leading unaligned bits */
    count_t tub;        /* trailing unaligned bits */
   
    ASSERT(start + bits <= bitmap->bits);
   
    aligned_start = ALIGN_UP(start, 8);
    lub = aligned_start - start;
    tub = (bits - lub) % 8;
   
    if (lub) {
        /*
         * Make sure to set any leading unaligned bits.
         */
        bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1);
    }
    for (i = 0; i < (bits - lub) / 8; i++) {
        /*
         * The middle bits can be set byte by byte.
         */
        bitmap->map[aligned_start / 8 + i] = ALL_ONES;
    }
    if (tub) {
        /*
         * Make sure to set any trailing unaligned bits.
         */
        bitmap->map[aligned_start / 8 + i] |= (1 << tub) - 1;
    }
   
}
 
/** Clear range of bits.
 *
 * @param bitmap Bitmap structure.
 * @param start Starting bit.
 * @param bits Number of bits to clear.
 */
void bitmap_clear_range(bitmap_t *bitmap, index_t start, count_t bits)
{
    index_t i;
    index_t aligned_start;
    count_t lub;        /* leading unaligned bits */
    count_t tub;        /* trailing unaligned bits */
   
    ASSERT(start + bits <= bitmap->bits);
   
    aligned_start = ALIGN_UP(start, 8);
    lub = aligned_start - start;
    tub = (bits - lub) % 8;
   
    if (lub) {
        /*
         * Make sure to clear any leading unaligned bits.
         */
        bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;
    }
    for (i = 0; i < (bits - lub) / 8; i++) {
        /*
         * The middle bits can be cleared byte by byte.
         */
        bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;
    }
    if (tub) {
        /*
         * Make sure to clear any trailing unaligned bits.
         */
        bitmap->map[aligned_start / 8 + i] &= ~((1 << tub) - 1);
    }
   
}
 
/** Copy portion of one bitmap into another bitmap.
 *
 * @param dst Destination bitmap.
 * @param src Source bitmap.
 * @param bits Number of bits to copy.
 */
void bitmap_copy(bitmap_t *dst, bitmap_t *src, count_t bits)
{
    index_t i;
   
    ASSERT(bits <= dst->bits);
    ASSERT(bits <= src->bits);
   
    for (i = 0; i < bits / 8; i++)
        dst->map[i] = src->map[i];
   
    if (bits % 8) {
        bitmap_clear_range(dst, i * 8, bits % 8);
        dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1);
    }
}
 

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/adt/bitmap.c @ 1757 – Rev 1200 → 1248

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