• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 #ifndef _GPXE_BITMAP_H
2 #define _GPXE_BITMAP_H
3 
4 /** @file
5  *
6  * Bitmaps for multicast downloads
7  *
8  */
9 
10 FILE_LICENCE ( GPL2_OR_LATER );
11 
12 #include <stdint.h>
13 #include <stddef.h>
14 #include <stdlib.h>
15 
16 /** A single block of bits within a bitmap */
17 typedef unsigned long bitmap_block_t;
18 
19 /** Size of a block of bits (in bits) */
20 #define BITMAP_BLKSIZE ( sizeof ( bitmap_block_t ) * 8 )
21 
22 /**
23  * Block index within bitmap
24  *
25  * @v bit		Bit index
26  * @ret index		Block index
27  */
28 #define BITMAP_INDEX( bit ) ( (bit) / BITMAP_BLKSIZE )
29 
30 /**
31  * Block mask within bitmap
32  *
33  * @v bit		Bit index
34  * @ret mask		Block mask
35  */
36 #define BITMAP_MASK( bit ) ( 1 << ( (bit) % BITMAP_BLKSIZE ) )
37 
38 /** A bitmap */
39 struct bitmap {
40 	/** Bitmap data */
41 	bitmap_block_t *blocks;
42 	/** Length of the bitmap, in bits */
43 	unsigned int length;
44 	/** Index of first gap in the bitmap */
45 	unsigned int first_gap;
46 };
47 
48 extern int bitmap_resize ( struct bitmap *bitmap, unsigned int new_length );
49 extern int bitmap_test ( struct bitmap *bitmap, unsigned int bit );
50 extern void bitmap_set ( struct bitmap *bitmap, unsigned int bit );
51 
52 /**
53  * Free bitmap resources
54  *
55  * @v bitmap		Bitmap
56  */
bitmap_free(struct bitmap * bitmap)57 static inline void bitmap_free ( struct bitmap *bitmap ) {
58 	free ( bitmap->blocks );
59 }
60 
61 /**
62  * Get first gap within bitmap
63  *
64  * @v bitmap		Bitmap
65  * @ret first_gap	First gap
66  *
67  * The first gap is the first unset bit within the bitmap.
68  */
bitmap_first_gap(struct bitmap * bitmap)69 static inline unsigned int bitmap_first_gap ( struct bitmap *bitmap ) {
70 	return bitmap->first_gap;
71 }
72 
73 /**
74  * Check to see if bitmap is full
75  *
76  * @v bitmap		Bitmap
77  * @ret is_full		Bitmap is full
78  *
79  * The bitmap is full if it has no gaps (i.e. no unset bits).
80  */
bitmap_full(struct bitmap * bitmap)81 static inline int bitmap_full ( struct bitmap *bitmap ) {
82 	return ( bitmap->first_gap == bitmap->length );
83 }
84 
85 #endif /* _GPXE_BITMAP_H */
86