Question

Implement the following C language library routines that provide public function prototypes and struct definition:

a) Linked list.

b) Binary search tree.

c) Read-write lock.

d) Priority queue.

Answer 1

The question involves implementing four different data structures and synchronization primitives in C: a linked list, binary search tree, read-write lock, and a priority queue. Basic struct definitions and function prototypes are provided for each.

Step-by-step explanation

To implement these structures in C, one must first define the data structures and then provide the functions that will operate on them. Below are basic definitions and function prototypes for each item requested:

A linked list is data structure where each element contains a link to the next element:

typedef struct Node {
int data;
struct Node* next;
} Node;

void appendToList(Node** head, int data);
void deleteFromList(Node** head, int data);
Node* searchInList(Node* head, int data);

A binary search tree (BST) is a tree data structure where each node has at most two children:

typedef struct TreeNode {
int key;
struct TreeNode *left, *right;
} TreeNode;

void insertToBST(TreeNode** root, int key);
void deleteFromBST(TreeNode** root, int key);
TreeNode* searchBST(TreeNode* root, int key);

A read-write lock allows concurrent read access but exclusive write access:

typedef struct RWLock {
// Lock members go here
} RWLock;

void initializeRWLock(RWLock* lock);
void readLock(RWLock* lock);
void readUnlock(RWLock* lock);
void writeLock(RWLock* lock);
void writeUnlock(RWLock* lock);

A priority queue is an abstract data type where each element has a priority:

typedef struct PriorityQueue {
// Priority Queue members
} PriorityQueue;

void insertToPriorityQueue(PriorityQueue* pq, int data, int priority);
int removeFromPriorityQueue(PriorityQueue* pq);
For each of these data structures and synchronization primitive, appropriate functions must be implemented to manage and interact with the data.