iPXE
bitmap.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17  * 02110-1301, USA.
18  *
19  * You can also choose to distribute this program under the terms of
20  * the Unmodified Binary Distribution Licence (as given in the file
21  * COPYING.UBDL), provided that you have satisfied its requirements.
22  */
23 
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25 
26 #include <errno.h>
27 #include <ipxe/bitmap.h>
28 
29 /** @file
30  *
31  * Bitmaps for multicast downloads
32  *
33  */
34 
35 /**
36  * Resize bitmap
37  *
38  * @v bitmap Bitmap
39  * @v new_length New length of bitmap, in bits
40  * @ret rc Return status code
41  */
42 int bitmap_resize ( struct bitmap *bitmap, unsigned int new_length ) {
43  unsigned int old_num_blocks;
44  unsigned int new_num_blocks;
45  size_t new_size;
46  bitmap_block_t *new_blocks;
47 
48  old_num_blocks = BITMAP_INDEX ( bitmap->length + BITMAP_BLKSIZE - 1 );
49  new_num_blocks = BITMAP_INDEX ( new_length + BITMAP_BLKSIZE - 1 );
50 
51  if ( old_num_blocks != new_num_blocks ) {
52  new_size = ( new_num_blocks * sizeof ( bitmap->blocks[0] ) );
53  new_blocks = realloc ( bitmap->blocks, new_size );
54  if ( ! new_blocks ) {
55  DBGC ( bitmap, "Bitmap %p could not resize to %d "
56  "bits\n", bitmap, new_length );
57  return -ENOMEM;
58  }
59  bitmap->blocks = new_blocks;
60  }
61  bitmap->length = new_length;
62 
63  while ( old_num_blocks < new_num_blocks ) {
64  bitmap->blocks[old_num_blocks++] = 0;
65  }
66 
67  DBGC ( bitmap, "Bitmap %p resized to %d bits\n", bitmap, new_length );
68  return 0;
69 }
70 
71 /**
72  * Test bit in bitmap
73  *
74  * @v bitmap Bitmap
75  * @v bit Bit index
76  * @ret is_set Bit is set
77  */
78 int bitmap_test ( struct bitmap *bitmap, unsigned int bit ) {
79  unsigned int index = BITMAP_INDEX ( bit );
80  bitmap_block_t mask = BITMAP_MASK ( bit );
81 
82  if ( bit >= bitmap->length )
83  return 0;
84  return ( ( bitmap->blocks[index] & mask ) != 0 );
85 }
86 
87 /**
88  * Set bit in bitmap
89  *
90  * @v bitmap Bitmap
91  * @v bit Bit index
92  */
93 void bitmap_set ( struct bitmap *bitmap, unsigned int bit ) {
94  unsigned int index = BITMAP_INDEX ( bit );
95  bitmap_block_t mask = BITMAP_MASK ( bit );
96 
97  DBGC ( bitmap, "Bitmap %p setting bit %d\n", bitmap, bit );
98 
99  /* Update bitmap */
100  bitmap->blocks[index] |= mask;
101 
102  /* Update first gap counter */
103  while ( bitmap_test ( bitmap, bitmap->first_gap ) ) {
104  bitmap->first_gap++;
105  }
106 }
static unsigned int unsigned int bit
Definition: bigint.h:196
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
Error codes.
#define DBGC(...)
Definition: compiler.h:505
#define BITMAP_BLKSIZE
Size of a block of bits (in bits)
Definition: bitmap.h:20
unsigned int length
Length of the bitmap, in bits.
Definition: bitmap.h:43
unsigned long bitmap_block_t
A single block of bits within a bitmap.
Definition: bitmap.h:17
bitmap_block_t * blocks
Bitmap data.
Definition: bitmap.h:41
int bitmap_test(struct bitmap *bitmap, unsigned int bit)
Test bit in bitmap.
Definition: bitmap.c:78
#define BITMAP_INDEX(bit)
Block index within bitmap.
Definition: bitmap.h:28
#define ENOMEM
Not enough space.
Definition: errno.h:534
int bitmap_resize(struct bitmap *bitmap, unsigned int new_length)
Resize bitmap.
Definition: bitmap.c:42
A bitmap.
Definition: bitmap.h:39
unsigned int first_gap
Index of first gap in the bitmap.
Definition: bitmap.h:45
void bitmap_set(struct bitmap *bitmap, unsigned int bit)
Set bit in bitmap.
Definition: bitmap.c:93
Bitmaps for multicast downloads.
void * realloc(void *old_ptr, size_t new_size)
Reallocate memory.
Definition: malloc.c:521
#define BITMAP_MASK(bit)
Block mask within bitmap.
Definition: bitmap.h:36
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21