iPXE
Data Structures | Macros | Typedefs | Functions
bitmap.h File Reference

Bitmaps for multicast downloads. More...

#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>

Go to the source code of this file.

Data Structures

struct  bitmap
 A bitmap. More...
 

Macros

#define BITMAP_BLKSIZE   ( sizeof ( bitmap_block_t ) * 8 )
 Size of a block of bits (in bits) More...
 
#define BITMAP_INDEX(bit)   ( (bit) / BITMAP_BLKSIZE )
 Block index within bitmap. More...
 
#define BITMAP_MASK(bit)   ( 1UL << ( (bit) % BITMAP_BLKSIZE ) )
 Block mask within bitmap. More...
 

Typedefs

typedef unsigned long bitmap_block_t
 A single block of bits within a bitmap. More...
 

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
int bitmap_resize (struct bitmap *bitmap, unsigned int new_length)
 Resize bitmap. More...
 
int bitmap_test (struct bitmap *bitmap, unsigned int bit)
 Test bit in bitmap. More...
 
void bitmap_set (struct bitmap *bitmap, unsigned int bit)
 Set bit in bitmap. More...
 
static void bitmap_free (struct bitmap *bitmap)
 Free bitmap resources. More...
 
static unsigned int bitmap_first_gap (struct bitmap *bitmap)
 Get first gap within bitmap. More...
 
static int bitmap_full (struct bitmap *bitmap)
 Check to see if bitmap is full. More...
 

Detailed Description

Bitmaps for multicast downloads.

Definition in file bitmap.h.

Macro Definition Documentation

◆ BITMAP_BLKSIZE

#define BITMAP_BLKSIZE   ( sizeof ( bitmap_block_t ) * 8 )

Size of a block of bits (in bits)

Definition at line 20 of file bitmap.h.

◆ BITMAP_INDEX

#define BITMAP_INDEX (   bit)    ( (bit) / BITMAP_BLKSIZE )

Block index within bitmap.

Parameters
bitBit index
Return values
indexBlock index

Definition at line 28 of file bitmap.h.

◆ BITMAP_MASK

#define BITMAP_MASK (   bit)    ( 1UL << ( (bit) % BITMAP_BLKSIZE ) )

Block mask within bitmap.

Parameters
bitBit index
Return values
maskBlock mask

Definition at line 36 of file bitmap.h.

Typedef Documentation

◆ bitmap_block_t

typedef unsigned long bitmap_block_t

A single block of bits within a bitmap.

Definition at line 17 of file bitmap.h.

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ bitmap_resize()

int bitmap_resize ( struct bitmap bitmap,
unsigned int  new_length 
)

Resize bitmap.

Parameters
bitmapBitmap
new_lengthNew length of bitmap, in bits
Return values
rcReturn status code

Definition at line 42 of file bitmap.c.

42  {
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 }
#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
#define BITMAP_INDEX(bit)
Block index within bitmap.
Definition: bitmap.h:28
#define ENOMEM
Not enough space.
Definition: errno.h:534
A bitmap.
Definition: bitmap.h:39
void * realloc(void *old_ptr, size_t new_size)
Reallocate memory.
Definition: malloc.c:521

References BITMAP_BLKSIZE, BITMAP_INDEX, bitmap::blocks, DBGC, ENOMEM, bitmap::length, and realloc().

Referenced by slam_open(), slam_pull_header(), and tftp_presize().

◆ bitmap_test()

int bitmap_test ( struct bitmap bitmap,
unsigned int  bit 
)

Test bit in bitmap.

Parameters
bitmapBitmap
bitBit index
Return values
is_setBit is set

Definition at line 78 of file bitmap.c.

78  {
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 }
static unsigned int unsigned int bit
Definition: bigint.h:205
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
#define BITMAP_INDEX(bit)
Block index within bitmap.
Definition: bitmap.h:28
A bitmap.
Definition: bitmap.h:39
#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

References bit, BITMAP_INDEX, BITMAP_MASK, bitmap::blocks, index, and bitmap::length.

Referenced by bitmap_set(), slam_mc_socket_deliver(), and slam_tx_nack().

◆ bitmap_set()

void bitmap_set ( struct bitmap bitmap,
unsigned int  bit 
)

Set bit in bitmap.

Parameters
bitmapBitmap
bitBit index

Definition at line 93 of file bitmap.c.

93  {
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:205
#define DBGC(...)
Definition: compiler.h:505
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
A bitmap.
Definition: bitmap.h:39
unsigned int first_gap
Index of first gap in the bitmap.
Definition: bitmap.h:45
#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

References bit, BITMAP_INDEX, BITMAP_MASK, bitmap_test(), bitmap::blocks, DBGC, bitmap::first_gap, and index.

Referenced by slam_mc_socket_deliver(), and tftp_rx_data().

◆ bitmap_free()

static void bitmap_free ( struct bitmap bitmap)
inlinestatic

Free bitmap resources.

Parameters
bitmapBitmap

Definition at line 57 of file bitmap.h.

57  {
58  free ( bitmap->blocks );
59 }
bitmap_block_t * blocks
Bitmap data.
Definition: bitmap.h:41
A bitmap.
Definition: bitmap.h:39
static void(* free)(struct refcnt *refcnt))
Definition: refcnt.h:54

References bitmap::blocks, and free.

Referenced by slam_free(), slam_pull_header(), tftp_free(), and tftp_timer_expired().

◆ bitmap_first_gap()

static unsigned int bitmap_first_gap ( struct bitmap bitmap)
inlinestatic

Get first gap within bitmap.

Parameters
bitmapBitmap
Return values
first_gapFirst gap

The first gap is the first unset bit within the bitmap.

Definition at line 69 of file bitmap.h.

69  {
70  return bitmap->first_gap;
71 }
A bitmap.
Definition: bitmap.h:39
unsigned int first_gap
Index of first gap in the bitmap.
Definition: bitmap.h:45

References bitmap::first_gap.

Referenced by slam_tx_nack(), tftp_rx_data(), and tftp_send_ack().

◆ bitmap_full()

static int bitmap_full ( struct bitmap bitmap)
inlinestatic

Check to see if bitmap is full.

Parameters
bitmapBitmap
Return values
is_fullBitmap is full

The bitmap is full if it has no gaps (i.e. no unset bits).

Definition at line 81 of file bitmap.h.

81  {
82  return ( bitmap->first_gap == bitmap->length );
83 }
unsigned int length
Length of the bitmap, in bits.
Definition: bitmap.h:43
A bitmap.
Definition: bitmap.h:39
unsigned int first_gap
Index of first gap in the bitmap.
Definition: bitmap.h:45

References bitmap::first_gap, and bitmap::length.

Referenced by slam_mc_socket_deliver(), and tftp_rx_data().