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.
 */
 
 /** @addtogroup genericadt ADT
 * @ingroup kernel
 * @{
 */
/**
 * @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>
#include <macros.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=0;
    index_t aligned_start;
    count_t lub;        /* leading unaligned bits */
    count_t amb;        /* aligned middle bits */
    count_t tab;        /* trailing aligned bits */
   
    ASSERT(start + bits <= bitmap->bits);
   
    aligned_start = ALIGN_UP(start, 8);
    lub = min(aligned_start - start, bits);
    amb = bits > lub ? bits - lub : 0;
    tab = amb % 8;
   
    if ( start + bits < aligned_start ) {
        /*
        * Set bits in the middle of byte
        */
        bitmap->map[start / 8] |= ((1 << lub)-1) << (start&7);
        return;
    }
   
    if (lub) {
        /*
         * Make sure to set any leading unaligned bits.
         */
        bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1);
    }
    for (i = 0; i < amb / 8; i++) {
        /*
         * The middle bits can be set byte by byte.
         */
        bitmap->map[aligned_start / 8 + i] = ALL_ONES;
    }
    if (tab) {
        /*
         * Make sure to set any trailing aligned bits.
         */
        bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 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=0;
    index_t aligned_start;
    count_t lub;        /* leading unaligned bits */
    count_t amb;        /* aligned middle bits */
    count_t tab;        /* trailing aligned bits */
   
    ASSERT(start + bits <= bitmap->bits);
   
    aligned_start = ALIGN_UP(start, 8);
    lub = min(aligned_start - start, bits);
    amb = bits > lub ? bits - lub : 0;
    tab = amb % 8;
 
    if ( start + bits < aligned_start )
    {
        /*
        * Set bits in the middle of byte
        */
        bitmap->map[start / 8] &= ~(((1 << lub)-1) << (start&7));
        return;
    }
 
 
    if (lub) {
        /*
         * Make sure to clear any leading unaligned bits.
         */
        bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;
    }
    for (i = 0; i < amb / 8; i++) {
        /*
         * The middle bits can be cleared byte by byte.
         */
        bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;
    }
    if (tab) {
        /*
         * Make sure to clear any trailing aligned bits.
         */
        bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 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 – Rev 1549 → 1702

Rev 1549		Rev 1702
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	/** @addtogroup genericadt ADT
-		30	* @ingroup kernel
-		31	* @{
-		32	*/
29	/**	33	/**
30	* @file bitmap.c	34	* @file bitmap.c
31	* @brief Implementation of bitmap ADT.	35	* @brief Implementation of bitmap ADT.
32	*	36	*
33	* This file implements bitmap ADT and provides functions for	37	* This file implements bitmap ADT and provides functions for
34	* setting and clearing ranges of bits.	38	* setting and clearing ranges of bits.
35	*/	39	*/
36		40
37	#include <adt/bitmap.h>	41	#include <adt/bitmap.h>
38	#include <typedefs.h>	42	#include <typedefs.h>
39	#include <arch/types.h>	43	#include <arch/types.h>
40	#include <align.h>	44	#include <align.h>
41	#include <debug.h>	45	#include <debug.h>
42	#include <macros.h>	46	#include <macros.h>
43		47
44	#define ALL_ONES 0xff	48	#define ALL_ONES 0xff
45	#define ALL_ZEROES 0x00	49	#define ALL_ZEROES 0x00
46		50
47	/** Initialize bitmap.	51	/** Initialize bitmap.
48	*	52	*
49	* No portion of the bitmap is set or cleared by this function.	53	* No portion of the bitmap is set or cleared by this function.
50	*	54	*
51	* @param bitmap Bitmap structure.	55	* @param bitmap Bitmap structure.
52	* @param map Address of the memory used to hold the map.	56	* @param map Address of the memory used to hold the map.
53	* @param bits Number of bits stored in bitmap.	57	* @param bits Number of bits stored in bitmap.
54	*/	58	*/
55	void bitmap_initialize(bitmap_t bitmap, __u8 map, count_t bits)	59	void bitmap_initialize(bitmap_t bitmap, __u8 map, count_t bits)
56	{	60	{
57	bitmap->map = map;	61	bitmap->map = map;
58	bitmap->bits = bits;	62	bitmap->bits = bits;
59	}	63	}
60		64
61	/** Set range of bits.	65	/** Set range of bits.
62	*	66	*
63	* @param bitmap Bitmap structure.	67	* @param bitmap Bitmap structure.
64	* @param start Starting bit.	68	* @param start Starting bit.
65	* @param bits Number of bits to set.	69	* @param bits Number of bits to set.
66	*/	70	*/
67	void bitmap_set_range(bitmap_t *bitmap, index_t start, count_t bits)	71	void bitmap_set_range(bitmap_t *bitmap, index_t start, count_t bits)
68	{	72	{
69	index_t i=0;	73	index_t i=0;
70	index_t aligned_start;	74	index_t aligned_start;
71	count_t lub; /* leading unaligned bits */	75	count_t lub; /* leading unaligned bits */
72	count_t amb; /* aligned middle bits */	76	count_t amb; /* aligned middle bits */
73	count_t tab; /* trailing aligned bits */	77	count_t tab; /* trailing aligned bits */
74		78
75	ASSERT(start + bits <= bitmap->bits);	79	ASSERT(start + bits <= bitmap->bits);
76		80
77	aligned_start = ALIGN_UP(start, 8);	81	aligned_start = ALIGN_UP(start, 8);
78	lub = min(aligned_start - start, bits);	82	lub = min(aligned_start - start, bits);
79	amb = bits > lub ? bits - lub : 0;	83	amb = bits > lub ? bits - lub : 0;
80	tab = amb % 8;	84	tab = amb % 8;
81		85
82	if ( start + bits < aligned_start ) {	86	if ( start + bits < aligned_start ) {
83	/*	87	/*
84	* Set bits in the middle of byte	88	* Set bits in the middle of byte
85	*/	89	*/
86	bitmap->map[start / 8] \|= ((1 << lub)-1) << (start&7);	90	bitmap->map[start / 8] \|= ((1 << lub)-1) << (start&7);
87	return;	91	return;
88	}	92	}
89		93
90	if (lub) {	94	if (lub) {
91	/*	95	/*
92	* Make sure to set any leading unaligned bits.	96	* Make sure to set any leading unaligned bits.
93	*/	97	*/
94	bitmap->map[start / 8] \|= ~((1 << (8 - lub)) - 1);	98	bitmap->map[start / 8] \|= ~((1 << (8 - lub)) - 1);
95	}	99	}
96	for (i = 0; i < amb / 8; i++) {	100	for (i = 0; i < amb / 8; i++) {
97	/*	101	/*
98	* The middle bits can be set byte by byte.	102	* The middle bits can be set byte by byte.
99	*/	103	*/
100	bitmap->map[aligned_start / 8 + i] = ALL_ONES;	104	bitmap->map[aligned_start / 8 + i] = ALL_ONES;
101	}	105	}
102	if (tab) {	106	if (tab) {
103	/*	107	/*
104	* Make sure to set any trailing aligned bits.	108	* Make sure to set any trailing aligned bits.
105	*/	109	*/
106	bitmap->map[aligned_start / 8 + i] \|= (1 << tab) - 1;	110	bitmap->map[aligned_start / 8 + i] \|= (1 << tab) - 1;
107	}	111	}
108		112
109	}	113	}
110		114
111	/** Clear range of bits.	115	/** Clear range of bits.
112	*	116	*
113	* @param bitmap Bitmap structure.	117	* @param bitmap Bitmap structure.
114	* @param start Starting bit.	118	* @param start Starting bit.
115	* @param bits Number of bits to clear.	119	* @param bits Number of bits to clear.
116	*/	120	*/
117	void bitmap_clear_range(bitmap_t *bitmap, index_t start, count_t bits)	121	void bitmap_clear_range(bitmap_t *bitmap, index_t start, count_t bits)
118	{	122	{
119	index_t i=0;	123	index_t i=0;
120	index_t aligned_start;	124	index_t aligned_start;
121	count_t lub; /* leading unaligned bits */	125	count_t lub; /* leading unaligned bits */
122	count_t amb; /* aligned middle bits */	126	count_t amb; /* aligned middle bits */
123	count_t tab; /* trailing aligned bits */	127	count_t tab; /* trailing aligned bits */
124		128
125	ASSERT(start + bits <= bitmap->bits);	129	ASSERT(start + bits <= bitmap->bits);
126		130
127	aligned_start = ALIGN_UP(start, 8);	131	aligned_start = ALIGN_UP(start, 8);
128	lub = min(aligned_start - start, bits);	132	lub = min(aligned_start - start, bits);
129	amb = bits > lub ? bits - lub : 0;	133	amb = bits > lub ? bits - lub : 0;
130	tab = amb % 8;	134	tab = amb % 8;
131		135
132	if ( start + bits < aligned_start )	136	if ( start + bits < aligned_start )
133	{	137	{
134	/*	138	/*
135	* Set bits in the middle of byte	139	* Set bits in the middle of byte
136	*/	140	*/
137	bitmap->map[start / 8] &= ~(((1 << lub)-1) << (start&7));	141	bitmap->map[start / 8] &= ~(((1 << lub)-1) << (start&7));
138	return;	142	return;
139	}	143	}
140		144
141		145
142	if (lub) {	146	if (lub) {
143	/*	147	/*
144	* Make sure to clear any leading unaligned bits.	148	* Make sure to clear any leading unaligned bits.
145	*/	149	*/
146	bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;	150	bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;
147	}	151	}
148	for (i = 0; i < amb / 8; i++) {	152	for (i = 0; i < amb / 8; i++) {
149	/*	153	/*
150	* The middle bits can be cleared byte by byte.	154	* The middle bits can be cleared byte by byte.
151	*/	155	*/
152	bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;	156	bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;
153	}	157	}
154	if (tab) {	158	if (tab) {
155	/*	159	/*
156	* Make sure to clear any trailing aligned bits.	160	* Make sure to clear any trailing aligned bits.
157	*/	161	*/
158	bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1);	162	bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1);
159	}	163	}
160		164
161	}	165	}
162		166
163	/** Copy portion of one bitmap into another bitmap.	167	/** Copy portion of one bitmap into another bitmap.
164	*	168	*
165	* @param dst Destination bitmap.	169	* @param dst Destination bitmap.
166	* @param src Source bitmap.	170	* @param src Source bitmap.
167	* @param bits Number of bits to copy.	171	* @param bits Number of bits to copy.
168	*/	172	*/
169	void bitmap_copy(bitmap_t dst, bitmap_t src, count_t bits)	173	void bitmap_copy(bitmap_t dst, bitmap_t src, count_t bits)
170	{	174	{
171	index_t i;	175	index_t i;
172		176
173	ASSERT(bits <= dst->bits);	177	ASSERT(bits <= dst->bits);
174	ASSERT(bits <= src->bits);	178	ASSERT(bits <= src->bits);
175		179
176	for (i = 0; i < bits / 8; i++)	180	for (i = 0; i < bits / 8; i++)
177	dst->map[i] = src->map[i];	181	dst->map[i] = src->map[i];
178		182
179	if (bits % 8) {	183	if (bits % 8) {
180	bitmap_clear_range(dst, i * 8, bits % 8);	184	bitmap_clear_range(dst, i * 8, bits % 8);
181	dst->map[i] \|= src->map[i] & ((1 << (bits % 8)) - 1);	185	dst->map[i] \|= src->map[i] & ((1 << (bits % 8)) - 1);
182	}	186	}
183	}	187	}
-		188
-		189	/** @}
-		190	*/
-		191
184		192