I need help with completing this program. I\'ll take any help I can get. Here is
ID: 3795177 • Letter: I
Question
I need help with completing this program. I'll take any help I can get. Here is what I need to complete:
#include "../include/block_store.h"
#include "../include/bitmap.h"
#include
typedef struct block_store block_store_t;
typedef struct block_store
{
size_t id;
}block_store_t;
/// This creates a new BS device, ready to go
/// eturn Pointer to a new block storage device, NULL on error
///
block_store_t *block_store_create()
{
return NULL;
}
/// Destroys the provided block storage device
/// This is an idempotent operation, so there is no return value
/// param bs BS device
///
void block_store_destroy(block_store_t *const bs)
{
if(bs == NULL)
{
break;
}
}
/// Searches for a free block, marks it as in use, and returns the block's id
/// param bs BS device
/// eturn Allocated block's id, SIZE_MAX on error
///
size_t block_store_allocate(block_store_t *const bs)
{
if(bs == NULL)
{
return NULL;
}
}
/// Attempts to allocate the requested block id
/// param bs the block store object
/// lock_id the requested block identifier
/// eturn boolean indicating success of operation
///
bool block_store_request(block_store_t *const bs, const size_t block_id)
{
if(bs == NULL || block_id == NULL)
{
return false;
}
}
/// Frees the specified block
/// param bs BS device
/// param block_id The block to free
///
void block_store_release(block_store_t *const bs, const size_t block_id)
{
if(bs == NULL || block_id == NULL)
{
break;
}
}
/// Counts the number of blocks marked as in use
/// param bs BS device
/// eturn Total blocks in use, SIZE_MAX on error
///
size_t block_store_get_used_blocks(const block_store_t *const bs)
{
if(bs == NULL)
{
return NULL;
}
}
/// Counts the number of blocks marked free for use
/// param bs BS device
/// eturn Total blocks free, SIZE_MAX on error
///
size_t block_store_get_free_blocks(const block_store_t *const bs)
{
if(bs == NULL)
{
return NULL;
}
}
/// Returns the total number of user-addressable blocks
/// (since this is constant, you don't even need the bs object)
/// eturn Total blocks
///
size_t block_store_get_total_blocks()
{
return NULL;
}
/// Reads data from the specified block and writes it to the designated buffer
/// param bs BS device
/// param block_id Source block id
/// param buffer Data buffer to write to
/// eturn Number of bytes read, 0 on error
///
size_t block_store_read(const block_store_t *const bs, const size_t block_id, void *buffer)
{
if(bs == NULL || block_id == NULL || buffer == NULL)
{
return NULL;
}
}
/// Reads data from the specified buffer and writes it to the designated block
/// param bs BS device
/// param block_id Destination block id
/// param buffer Data buffer to read from
/// eturn Number of bytes written, 0 on error
///
size_t block_store_write(block_store_t *const bs, const size_t block_id, const void *buffer)
{
if(bs == NULL || block_id == NULL || buffer == NULL)
{
return NULL;
}
}
------------------------------------------------------------------------------------------------------------------------------------------------
Here is the bitmap.c file, you don't need the bitmap.h file:
#include "../include/bitmap.h"
#include
// Just the one for now. Indicates we're an overlay and should not free
// (also, make sure that ALL is as wide as ll of the flags)
typedef enum { NONE = 0x00, OVERLAY = 0x01, ALL = 0xFF } BITMAP_FLAGS;
struct bitmap
{
unsigned leftover_bits; // Packing will increase this to an int anyway
BITMAP_FLAGS flags; // Generic place to store flags. Not enough flags to worry about width yet.
uint8_t *data;
size_t bit_count, byte_count;
};
#define FLAG_CHECK(bitmap, flag) ((bitmap)->flags & flag)
// Not sure I want these
// #define FLAG_SET(bitmap, flag) bitmap->flags |= flag
// #define FLAG_UNSET(bitmap, flag) bitmap->flags &= ~flag
// lookup instead of always shifting bits. Should be faster? Confirmed: 10% faster
// Also, using native int width because it should be faster as well? - Negligible/indeterminate
// Won't help until bitmap uses native width for the array
static const uint8_t mask[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
// Mask for all bits at index i and lower
static const uint8_t mask_down_inclusive[8] = {0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF};
// Inverted mask
static const uint8_t invert_mask[8] = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F};
// Way more testing than I should waste my time on suggested uint8_t was faster
// but it may still be negligible/indeterminate.
// Since the data store is uint8_t, we already get punished for our bad alignment
// so this doesn't really matter until everything gets moved to generic int
// Total bits set in the given byte in a handy lookup table
// Macros, man...
// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable
#define B2(n) n, n + 1, n + 1, n + 2
#define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
#define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
static const uint8_t bit_totals[256] = {B6(0), B6(1), B6(1), B6(2)};
#undef B6
#undef B4
#undef B2
// There is an alternative for getting bit count that only loops as many times as there are bits set
// but that's still a loop and this table is 256B.
/*
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; v >>= 1)
{
c += v & 1;
}
*/
// A place to generalize the creation process and setup
bitmap_t *bitmap_initialize(size_t n_bits, BITMAP_FLAGS flags);
/// Sets requested bit in bitmap
/// param bitmap The bitmap
/// param bit The bit to set
void bitmap_set(bitmap_t *const bitmap, const size_t bit)
{
bitmap->data[bit >> 3] |= mask[bit & 0x07];
}
/// Clears requested bit in bitmap
/// param bitmap The bitmap
/// param bit The bit to clear
void bitmap_reset(bitmap_t *const bitmap, const size_t bit)
{
bitmap->data[bit >> 3] &= invert_mask[bit & 0x07];
}
/// Returns bit in bitmap
/// param bitmap The bitmap
/// param bit The bit to query
/// eturn State of requested bit
bool bitmap_test(const bitmap_t *const bitmap, const size_t bit)
{
return bitmap->data[bit >> 3] & mask[bit & 0x07];
}
/// Flips bit in bitmap
/// param bitmap The bitmap
/// param bit The bit to flip
void bitmap_flip(bitmap_t *const bitmap, const size_t bit)
{
bitmap->data[bit >> 3] ^= mask[bit & 0x07];
}
/// Flips all bits in the bitmap
/// param bitmap The bitmap to invert
void bitmap_invert(bitmap_t *const bitmap)
{
for (size_t byte = 0; byte < bitmap->byte_count; ++byte)
{
bitmap->data[byte] = ~bitmap->data[byte];
}
}
/// Find first set
/// param bitmap The bitmap
/// eturn The first one bit address, SIZE_MAX on error/not found
size_t bitmap_ffs(const bitmap_t *const bitmap)
{
if (bitmap)
{
size_t result = 0;
for (; result < bitmap->bit_count && !bitmap_test(bitmap, result); ++result)
{
}
return (result == bitmap->bit_count ? SIZE_MAX : result);
}
return SIZE_MAX;
}
/// Find first zero
/// param bitmap The bitmap
/// eturn The first zero bit address, SIZE_MAX on error/not found
size_t bitmap_ffz(const bitmap_t *const bitmap)
{
if (bitmap)
{
size_t result = 0;
for (; result < bitmap->bit_count && bitmap_test(bitmap, result); ++result)
{
}
return (result == bitmap->bit_count ? SIZE_MAX : result);
}
return SIZE_MAX;
}
/// Count all bits set
/// param bitmap the bitmap
/// eturn the total number of bits that are set in the bitmap
size_t bitmap_total_set(const bitmap_t *const bitmap)
{
size_t total = 0;
if (bitmap)
{
// If we have leftover, stop a byte early because we have to handle it differently.
size_t stop = bitmap->leftover_bits ? bitmap->byte_count - 1 : bitmap->byte_count;
for (size_t idx = 0; idx < stop; ++idx)
{
total += bit_totals[bitmap->data[idx]];
}
if (bitmap->leftover_bits)
{
// haha, this is readable
// get the byte at the end of the bitmap, mask it so we're only looking at the bits in use
// then feed that to the bit_total lookup so we don't count the bits past our bit total
// (which whould be considered undetermined)
total += bit_totals[bitmap->data[bitmap->byte_count - 1] & mask_down_inclusive[bitmap->leftover_bits - 1]];
}
}
return total;
}
/// For each loop for all set bits
/// (Arguments passed to func are saved across calls)
/// param bitmap The bitmap
/// param func The function to apply (first parameter will be size_t with the bit number)
/// param args A generic pointer to pass to the called function
void bitmap_for_each(const bitmap_t *const bitmap, void (*func)(size_t, void *), void *arg)
{
if (bitmap && func)
{
for (size_t idx = 0; idx < bitmap->bit_count; ++idx)
{
if (bitmap_test(bitmap, idx))
{
func(idx, arg);
}
}
}
}
/// Resets bitmap contents to the desired pattern
/// (pattern not guarenteed accurate for final bits
/// if bit_count is not a multiple of 8)
/// param bitmap The bitmap
/// param pattern The pattern to apply to all bytes
void bitmap_format(bitmap_t *const bitmap, const uint8_t pattern)
{
memset(bitmap->data, pattern, bitmap->byte_count);
}
/// Gets total number of bits in bitmap
/// param bitmap The bitmap
/// eturn The number of bits in the bitmap
size_t bitmap_get_bits(const bitmap_t *const bitmap)
{
return bitmap->bit_count;
}
/// Gets total number of bytes in bitmap
/// param bitmap The bitmap
/// eturn number of bytes used by bitmap storage array
size_t bitmap_get_bytes(const bitmap_t *const bitmap)
{
return bitmap->byte_count;
}
/// Creates a bitmap to contain n bits (zero initialized)
/// param n_bits
/// eturn New bitmap pointer, NULL on error
bitmap_t *bitmap_create(const size_t n_bits)
{
return bitmap_initialize(n_bits, NONE);
}
/// Gets pointer to the internal data for exporting
/// Be sure to query the bit and byte size if it's unknown
/// param bitmap The bitmap
/// eturn Pointer for writing
const uint8_t *bitmap_export(const bitmap_t *const bitmap)
{
return bitmap->data;
}
/// Creates a new bitmap with the provided data
/// Note: This does not use the buffer but copies the data
/// to an internal buffer
/// param n_bits The number of bits in the bitmap
/// param bitmap_data The data to import
/// eturn New bitmap pointer, NULL on error
bitmap_t *bitmap_import(const size_t n_bits, const void *const bitmap_data)
{
if (bitmap_data)
{
bitmap_t *bitmap = bitmap_initialize(n_bits, NONE);
if (bitmap)
{
memcpy(bitmap->data, bitmap_data, bitmap->byte_count);
return bitmap;
}
}
return NULL;
}
/// Creates a new bitmap using the provided data
/// Note: This uses the given block of memory
/// and does not free this pointer on destruction
/// param n_bits The number of bits in the bitmap
/// param bitmap_data The data to import
/// eturn New bitmap pointer, NULL on error
bitmap_t *bitmap_overlay(const size_t n_bits, void *const bitmap_data)
{
if (bitmap_data)
{
bitmap_t *bitmap = bitmap_initialize(n_bits, OVERLAY);
if (bitmap)
{
bitmap->data = (uint8_t *) bitmap_data;
return bitmap;
}
}
return NULL;
}
/// Destructs and destroys bitmap object
/// param bitmap The bitmap
void bitmap_destroy(bitmap_t *bitmap)
{
if (bitmap)
{
if (!FLAG_CHECK(bitmap, OVERLAY))
{
// don't free memory that isn't ours!
free(bitmap->data);
}
free(bitmap);
}
}
//
///
// HERE BE DRAGONS
///
//
bitmap_t *bitmap_initialize(size_t n_bits, BITMAP_FLAGS flags)
{
if (n_bits)
{ // must be non-zero
bitmap_t *bitmap = (bitmap_t *) malloc(sizeof(bitmap_t));
if (bitmap)
{
bitmap->flags = flags;
bitmap->bit_count = n_bits;
bitmap->byte_count = n_bits >> 3;
bitmap->leftover_bits = n_bits & 0x07;
bitmap->byte_count += (bitmap->leftover_bits ? 1 : 0);
// FLAG HANDLING HERE
// This logic will need to be reworked when we have more than one flag, haha
// Maybe something like if (flags) and then contain a giant if/else-if for each flag
// Then a return at the end
if (FLAG_CHECK(bitmap, OVERLAY))
{
// don't mess with data, caller will set it
bitmap->data = NULL;
return bitmap;
} else
{
bitmap->data = (uint8_t *) calloc(bitmap->byte_count, 1);
if (bitmap->data)
{
return bitmap;
}
}
free(bitmap);
}
}
return NULL;
}
Explanation / Answer
//EXAMPLE PROGRAM FOR SINGLE LINKED LIST
# include <stdio.h>
# include <conio.h>
# include <alloc.h>
# include <stdlib.h>
struct list
{
int number;
struct list *next;
};
typedef struct list node;
node *first,*prev,*temp,*curr;
void create(void)
{
printf(" Stop by -999");
temp=(node *)(malloc(sizeof(node)));
printf(" Enter the numbers ");
scanf("%d",&temp->number);
while(temp->number!=-999)
{
temp->next=NULL;
if(first==NULL)
{
first=temp;
prev=first;
}
else
{
prev->next=temp;
prev=temp;
}
temp=(node *)(malloc(sizeof(node)));
scanf("%d",&temp->number);
} //end of while
}
void delete1(void)
{
int num;
printf(" Enter the number to delete ");
scanf("%d",&num);
if(first->number==num)
{
first=first->next;
return;
}
else
{
prev=first;
curr=first->next;
while(curr->next!=NULL)
{
if(curr->number==num)
{
prev->next=curr->next;
return;
}
prev=curr;
curr=curr->next;
}
}
if(curr->number==num)
{
prev->next=NULL;
return;
}
printf(" No such number");
}
void insertbefore(void)
{
int nu;
temp=(node *)(malloc(sizeof(node)));
printf(" Enter the number ");
scanf("%d",&temp->number);
printf(" Insert before which number ");
scanf("%d",&nu);
temp->next=NULL;
prev=first;
curr=first;
if(first==NULL) //if the list is empty then we can insert in this way
{
first=temp;
return;
}
if(curr->number==nu)
{
temp->next=first;
first=temp;
return;
}
else
{
prev=curr;
curr=curr->next;
while(curr->next!=NULL)
{
if(curr->number==nu)
{
prev->next=temp;
temp->next=curr;
return;
}
prev=curr;
curr=curr->next;
}
}
if(curr->number==nu)
{
prev->next=temp;
temp->next=curr;
return;
}
printf(" No such number ");
}
void insertafter(void)
{
int nu;
temp=(node *)(malloc(sizeof(node)));
printf(" Enter the number ");
scanf("%d",&temp->number);
printf(" Insert after which number ");
scanf("%d",&nu);
temp->next=NULL;
prev=first;
curr=first;
if(first==NULL) //if the list is empty then we can insert in this way
{
first=temp;
return;
}
if(curr->number==nu)
{
temp->next=curr->next;
curr->next=temp;
return;
}
else
{
prev=curr;
curr=curr->next;
while(curr->next!=NULL)
{
if(curr->number==nu)
{
temp->next=curr->next;
curr->next=temp;
return;
}
prev=curr;
curr=curr->next;
}
}
if(curr->number==nu)
{
curr->next=temp;
return;
}
printf(" No such number ");
}
void print(void)
{
printf(" The list is ");
printf(" ----------- ");
temp=first;
while(temp!=NULL)
{
printf("%d-->",temp->number);
temp=temp->next;
}
printf("Nil");
getch();
}
void main()
{
int ch=0;
first=NULL;
clrscr();
printf(" Linked List creation ");
create();
clrscr();
while(ch!=5)
{
clrscr();
printf(" 1.Insert Before");
printf(" 2.Insert After");
printf(" 3.Delete ");
printf(" 4.Print ");
printf(" 5.Exit ");
printf(" Enter your choice ");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertbefore();
print();
break;
case 2:
insertafter();
print();
break;
case 3:
delete1();
print();
break;
case 4:
print();
break;
case 5:
print();
exit(1);
}
}
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.