lib.c

#define _GNU_SOURCE
#include <mpi.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define MAX_NEIGHBORS      4
#define MAX_BOOKS          10000

#define MSG_START_LE           10
#define MSG_EXPLORE            11
#define MSG_PARENT             12
#define MSG_LE_ANNOUNCE        13
#define MSG_LE_LIBR_DONE       14
#define MSG_LEND_BOOK          31
#define MSG_GET_BOOK           32
#define MSG_FIND_BOOK          33
#define MSG_BOOK_REQUEST       34
#define MSG_ACK_TB             35
#define MSG_DONATE_TO_LIB      41
#define MSG_ACK_DB             37
#define MSG_CHECK_NUM_BOOKS_LOAN    46
#define MSG_BOOKS_LOANED_RESULT     48
#define MSG_CHECK_NUM_BOOKS_LOAN_DONE 51
#define MSG_LIBRARY_LOAN_REQUEST  52
#define MSG_LIBRARY_LOAN_RESPONSE 53
#define MSG_GRID_TRAVERSE           54
#define MSG_GRID_TRAVERSE_RESULT    55
#define MSG_SHUTDOWN                99

typedef struct {
    int book_id;
    int cost;
    int copies_owned;
    int copies_loaned;
} LibraryBook;

typedef struct {
    int neighbors[MAX_NEIGHBORS];
    int neighbor_count;
    
    // DFS Spanning Tree Election state
    int tree_id;
    int parent;
    int children[MAX_NEIGHBORS];
    int child_count;
    int explore_replies_expected;
    int explore_replies_received;
    int election_active;
    int election_initiator;
    int election_completed;
    
    // Grid traversal state
    int grid_x, grid_y;
    int traversal_active;
    long long traversal_accumulator;
    int traversal_position;
} LibraryNode;

static int is_leader = 0;
static int leader_id = -1;
static int election_completed = 0;
static int N_global = 0;
static int book_to_library[MAX_BOOKS];
static LibraryBook library_books[MAX_BOOKS];
static int book_collection_size = 0;

// Forward function declarations
void check_election_completion(int rank, LibraryNode* node);
void complete_election_as_leader(int rank, LibraryNode* node);
void initialize_library_books(int rank, int N);
void print_library_status(int rank);

// Add book to library collection with enhanced logging
void add_book_to_library(int book_id, int copies) {
    printf("Library: Adding book %d with %d copies\n", book_id, copies);
    
    // Check if book already exists
    for (int i = 0; i < book_collection_size; i++) {
        if (library_books[i].book_id == book_id) {
            library_books[i].copies_owned += copies;
            printf("Library: Updated book %d - now has %d copies owned, %d loaned\n", 
                   book_id, library_books[i].copies_owned, library_books[i].copies_loaned);
            return;
        }
    }
    
    // Add new book
    if (book_collection_size < MAX_BOOKS) {
        library_books[book_collection_size].book_id = book_id;
        library_books[book_collection_size].cost = 5 + (rand() % 96); // Random cost 5-100
        library_books[book_collection_size].copies_owned = copies;
        library_books[book_collection_size].copies_loaned = 0;
        
        printf("Library: Added new book %d with %d copies (cost: %d) at index %d\n", 
               book_id, copies, library_books[book_collection_size].cost, book_collection_size);
        
        book_collection_size++;
    } else {
        printf("ERROR: Library book collection full (%d/%d) - cannot add book %d\n", 
               book_collection_size, MAX_BOOKS, book_id);
    }
}

// Enhanced lend book function with detailed logging
int lend_book(int book_id) {
    printf("Library: Attempting to lend book %d (collection size: %d)\n", 
           book_id, book_collection_size);
    
    for (int i = 0; i < book_collection_size; i++) {
        printf("Library: Checking book at index %d - id=%d (looking for %d)\n", 
               i, library_books[i].book_id, book_id);
               
        if (library_books[i].book_id == book_id) {
            printf("Library: Found book %d - owned: %d, loaned: %d\n", 
                   book_id, library_books[i].copies_owned, library_books[i].copies_loaned);
            
            if (library_books[i].copies_owned > 0) {
                library_books[i].copies_owned--;
                library_books[i].copies_loaned++;
                printf("Library: Successfully lent book %d - now owned: %d, loaned: %d\n", 
                       book_id, library_books[i].copies_owned, library_books[i].copies_loaned);
                return 1; // Success
            } else {
                printf("Library: Book %d has no available copies (all %d copies are loaned)\n", 
                       book_id, library_books[i].copies_loaned);
                return 0; // No copies available
            }
        }
    }
    
    printf("Library: Book %d not found in my collection\n", book_id);
    return 0; // Book not found
}

// Calculate grid coordinates from rank
void calculate_grid_position(int rank, int N, int* x, int* y) {
    int lib_index = rank - 1; // Convert to 0-based
    *x = lib_index % N;
    *y = lib_index / N;
    printf("Library %d: Grid position calculated as (%d,%d)\n", rank, *x, *y);
}

// Enhanced DFS Spanning Tree Election
void start_dfs_election(int rank, LibraryNode* node) {
    printf("Library %d: Starting DFS Spanning Tree election with tree_id %d\n", rank, rank);
    
    node->tree_id = rank;
    node->parent = -1;
    node->child_count = 0;
    node->explore_replies_expected = node->neighbor_count;
    node->explore_replies_received = 0;
    node->election_active = 1;
    node->election_initiator = 1;
    node->election_completed = 0;
    
    printf("Library %d: Election state - expecting %d replies from neighbors\n", 
           rank, node->explore_replies_expected);
    
    // Send EXPLORE messages to all neighbors
    for (int i = 0; i < node->neighbor_count; i++) {
        int explore_msg[3] = {MSG_EXPLORE, rank, rank};  // msg_type, tree_id, sender
        MPI_Send(explore_msg, 3, MPI_INT, node->neighbors[i], 0, MPI_COMM_WORLD);
        printf("Library %d: Sent EXPLORE (tree_id=%d) to neighbor %d\n", 
               rank, rank, node->neighbors[i]);
    }
    
    // If no neighbors, I'm automatically the leader
    if (node->neighbor_count == 0) {
        printf("Library %d: No neighbors - becoming leader immediately\n", rank);
        complete_election_as_leader(rank, node);
    }
}

// Handle EXPLORE message with proper concurrent tree mergin    g
void handle_explore_message(int rank, int tree_id, int sender, LibraryNode* node) {
    printf("Library %d: Received EXPLORE from %d with tree_id %d (my tree_id: %d, active: %d)\n", 
           rank, sender, tree_id, node->tree_id, node->election_active);
    
    if (!node->election_active) {
        // Start my own election if not already active
        printf("Library %d: Election not active - starting with tree_id %d\n", rank, rank);
        node->tree_id = rank;
        node->parent = -1;
        node->child_count = 0;
        node->election_active = 1;
        node->election_initiator = 0;
        node->explore_replies_expected = node->neighbor_count;
        node->explore_replies_received = 0;
        node->election_completed = 0;
    }
    
    if (tree_id > node->tree_id) {
        // Higher tree ID wins - join that tree
        printf("Library %d: Higher tree_id %d wins over my %d - joining tree\n", 
               rank, tree_id, node->tree_id);
        node->tree_id = tree_id;
        node->parent = sender;
        
        // Send PARENT acknowledgment
        int parent_msg[3] = {MSG_PARENT, tree_id, rank};
        MPI_Send(parent_msg, 3, MPI_INT, sender, 0, MPI_COMM_WORLD);
        printf("Library %d: Sent PARENT ack to %d for tree %d\n", rank, sender, tree_id);
        
        // Forward EXPLORE to other neighbors with new tree_id
        for (int i = 0; i < node->neighbor_count; i++) {
            if (node->neighbors[i] != sender) {
                int explore_msg[3] = {MSG_EXPLORE, tree_id, rank};
                MPI_Send(explore_msg, 3, MPI_INT, node->neighbors[i], 0, MPI_COMM_WORLD);
                printf("Library %d: Forwarded EXPLORE (tree_id=%d) to neighbor %d\n", 
                       rank, tree_id, node->neighbors[i]);
            }
        }
    } else if (tree_id < node->tree_id) {
        // My tree ID is higher - reject with my tree_id
        printf("Library %d: My tree_id %d is higher than %d - rejecting\n", 
               rank, node->tree_id, tree_id);
        int reject_msg[3] = {MSG_EXPLORE, node->tree_id, rank};
        MPI_Send(reject_msg, 3, MPI_INT, sender, 0, MPI_COMM_WORLD);
    } else {
        // Same tree_id - send ACK
        printf("Library %d: Same tree_id %d - sending PARENT ack\n", rank, tree_id);
        int ack_msg[3] = {MSG_PARENT, tree_id, rank};
        MPI_Send(ack_msg, 3, MPI_INT, sender, 0, MPI_COMM_WORLD);
    }
}

// Handle PARENT message in DFS election
void handle_parent_message(int rank, int tree_id, int sender, LibraryNode* node) {
    printf("Library %d: Received PARENT from %d for tree_id %d (my tree_id: %d)\n", 
           rank, sender, tree_id, node->tree_id);
    
    if (tree_id == node->tree_id) {
        // Add as child if same tree
        int already_child = 0;
        for (int i = 0; i < node->child_count; i++) {
            if (node->children[i] == sender) {
                already_child = 1;
                break;
            }
        }
        
        if (!already_child && node->child_count < MAX_NEIGHBORS) {
            node->children[node->child_count++] = sender;
            printf("Library %d: Added %d as child (total children: %d)\n", 
                   rank, sender, node->child_count);
        }
    }
    
    node->explore_replies_received++;
    printf("Library %d: Received %d/%d explore replies\n", 
           rank, node->explore_replies_received, node->explore_replies_expected);
    
    check_election_completion(rank, node);
}

// Check if election is complete and declare leader
void check_election_completion(int rank, LibraryNode* node) {
    if (node->explore_replies_received >= node->explore_replies_expected && 
        !node->election_completed) {
        
        printf("Library %d: Election phase complete - tree_id %d\n", rank, node->tree_id);
        
        // The node with the highest tree_id that initiated becomes leader
        leader_id = node->tree_id;
        node->election_completed = 1;
        election_completed = 1;
        
        if (rank == leader_id) {
            complete_election_as_leader(rank, node);
        } else {
            printf("Library %d: Election complete - %d is the leader\n", rank, leader_id);
        }
    }
}

void complete_election_as_leader(int rank, LibraryNode* node) {
    if (is_leader) return; // Prevent multiple declarations
    
    is_leader = 1;
    leader_id = rank;
    printf("Library %d: I am the DFS ELECTED LEADER!\n", rank);
    
    // Initialize book-to-library mapping using assignment formula
    printf("Library %d (leader): Initializing book-to-library mapping\n", rank);
    for (int b = 0; b < MAX_BOOKS; b++) {
        book_to_library[b] = 1 + (b / N_global);
        if (book_to_library[b] > N_global * N_global) {
            book_to_library[b] = N_global * N_global;
        }
    }
    
    // Announce leadership to all other libraries
    for (int lib = 1; lib <= N_global * N_global; lib++) {
        if (lib != rank) {
            int announce_msg[2] = {MSG_LE_ANNOUNCE, rank};
            MPI_Send(announce_msg, 2, MPI_INT, lib, 0, MPI_COMM_WORLD);
            printf("Library %d (leader): Sent leadership announcement to library %d\n", rank, lib);
        }
    }
    
    // Notify coordinator
    MPI_Send(&rank, 1, MPI_INT, 0, MSG_LE_LIBR_DONE, MPI_COMM_WORLD);
    printf("Library %d (leader): Notified coordinator of leadership\n", rank);
}

// Initialize library books based on assignment formula
void initialize_library_books(int rank, int N) {
    book_collection_size = 0;
    
    // Library i (1-based) gets books (i-1)*N to i*N-1
    int lib_index = rank - 1;  // Convert to 0-based
    int first_book = lib_index * N;
    int last_book = first_book + N - 1;
    
    printf("Library %d: Initializing with books %d-%d (N=%d)\n", 
           rank, first_book, last_book, N);
    
    for (int book_id = first_book; book_id <= last_book; book_id++) {
        add_book_to_library(book_id, N);  // N copies of each book initially
    }
    
    printf("Library %d: Book initialization complete - %d books in collection\n", 
           rank, book_collection_size);
    print_library_status(rank);
}

// Print current library status for debugging
void print_library_status(int rank) {
    printf("=== Library %d Status ===\n", rank);
    printf("Collection size: %d\n", book_collection_size);
    printf("Is leader: %s\n", is_leader ? "YES" : "NO");
    printf("Books:\n");
    
    for (int i = 0; i < book_collection_size && i < 5; i++) {  // Show first 5
        printf("  Book %d: owned=%d, loaned=%d, cost=%d\n", 
               library_books[i].book_id,
               library_books[i].copies_owned,
               library_books[i].copies_loaned,
               library_books[i].cost);
    }
    
    if (book_collection_size > 5) {
        printf("  ... and %d more books\n", book_collection_size - 5);
    }
    printf("========================\n");
}

void run_library(int rank, int N) {
    N_global = N;
    srand(time(NULL) + rank); // Initialize random seed for book costs
    
    LibraryNode node;
    memset(&node, 0, sizeof(node));
    node.tree_id = rank;
    node.parent = -1;

    printf("Library %d: Starting up with N=%d\n", rank, N);

    // Calculate grid position and neighbors
    calculate_grid_position(rank, N, &node.grid_x, &node.grid_y);
    
    // Add neighbors based on grid topology
    printf("Library %d: Adding neighbors for grid position (%d,%d)\n", 
           rank, node.grid_x, node.grid_y);
    
    if (node.grid_x > 0) {
        node.neighbors[node.neighbor_count++] = rank - 1;
        printf("Library %d: Added left neighbor %d\n", rank, rank - 1);
    }
    if (node.grid_x < N - 1) {
        node.neighbors[node.neighbor_count++] = rank + 1;
        printf("Library %d: Added right neighbor %d\n", rank, rank + 1);
    }
    if (node.grid_y > 0) {
        node.neighbors[node.neighbor_count++] = rank - N;
        printf("Library %d: Added up neighbor %d\n", rank, rank - N);
    }
    if (node.grid_y < N - 1) {
        node.neighbors[node.neighbor_count++] = rank + N;
        printf("Library %d: Added down neighbor %d\n", rank, rank + N);
    }

    printf("Library %d: Total neighbors: %d\n", rank, node.neighbor_count);

    // Initialize books
    initialize_library_books(rank, N);

    MPI_Status status;
    int msg[4];

    printf("Library %d: Entering message loop\n", rank);

    while (1) {
        MPI_Recv(msg, 4, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
        int sender = status.MPI_SOURCE;

        printf("Library %d: Received message type %d from %d\n", rank, msg[0], sender);

        switch (msg[0]) {
            case MSG_START_LE: {
                printf("Library %d: Received START_LE - beginning election\n", rank);
                start_dfs_election(rank, &node);
                break;
            }
            
            case MSG_EXPLORE: {
                handle_explore_message(rank, msg[1], sender, &node);
                break;
            }
            
            case MSG_PARENT: {
                handle_parent_message(rank, msg[1], sender, &node);
                break;
            }
            
            case MSG_LE_ANNOUNCE: {
                leader_id = msg[1];
                election_completed = 1;
                printf("Library %d: Received leadership announcement - %d is leader\n", 
                       rank, leader_id);
                break;
            }
            
            case MSG_LEND_BOOK: {
                int b_id = msg[1];
                printf("Library %d: Received LEND_BOOK request for book %d from client %d\n", 
                       rank, b_id, sender);
                
                // Try to lend the book
                if (lend_book(b_id)) {
                    printf("Library %d: Successfully lent book %d to client %d\n", 
                           rank, b_id, sender);
                    int reply[2] = {MSG_GET_BOOK, b_id};
                    MPI_Send(reply, 2, MPI_INT, sender, 0, MPI_COMM_WORLD);
                    printf("Library %d: Sent GET_BOOK success response to client %d\n", 
                           rank, sender);
                } else {
                    // Try to find the book at the correct library
                    int target_lib = 1 + (b_id / N_global);
                    
                    printf("Library %d: Don't have book %d - should be at library %d\n", 
                           rank, b_id, target_lib);
                    
                    if (target_lib != rank && target_lib >= 1 && target_lib <= N_global * N_global) {
                        printf("Library %d: Forwarding request for book %d to library %d\n", 
                               rank, b_id, target_lib);
                        int forward_msg[3] = {MSG_BOOK_REQUEST, b_id, sender};
                        MPI_Send(forward_msg, 3, MPI_INT, target_lib, 0, MPI_COMM_WORLD);
                    } else {
                        printf("Library %d: Book %d not found - sending error to client %d\n", 
                               rank, b_id, sender);
                        int error_msg[2] = {MSG_GET_BOOK, -1};
                        MPI_Send(error_msg, 2, MPI_INT, sender, 0, MPI_COMM_WORLD);
                    }
                }
                break;
            }
            
            case MSG_BOOK_REQUEST: {
                int b_id = msg[1];
                int client_id = msg[2];
                
                printf("Library %d: Received BOOK_REQUEST for book %d for client %d\n", 
                       rank, b_id, client_id);
                
                if (lend_book(b_id)) {
                    printf("Library %d: Fulfilled forwarded request for book %d to client %d\n", 
                           rank, b_id, client_id);
                    int reply[2] = {MSG_GET_BOOK, b_id};
                    MPI_Send(reply, 2, MPI_INT, client_id, 0, MPI_COMM_WORLD);
                } else {
                    printf("Library %d: Cannot fulfill forwarded request for book %d\n", 
                           rank, b_id);
                    int error_msg[2] = {MSG_GET_BOOK, -1};
                    MPI_Send(error_msg, 2, MPI_INT, client_id, 0, MPI_COMM_WORLD);
                }
                break;
            }
            
            case MSG_CHECK_NUM_BOOKS_LOAN: {
                if (is_leader) {
                    printf("Library %d (leader): Starting library loan aggregation\n", rank);
                    
                    // Calculate my own loans first
                    long long my_loans = 0;
                    for (int i = 0; i < book_collection_size; i++) {
                        my_loans += library_books[i].copies_loaned;
                    }
                    
                    printf("Library %d (leader): My loans: %lld\n", rank, my_loans);
                    
                    // Send request to all other libraries to get their loan counts
                    long long total_loans = my_loans;
                    int libraries_responded = 0;
                    int libraries_expected = 0;
                    
                    // Count how many other libraries we need to hear from
                    for (int lib = 1; lib <= N_global * N_global; lib++) {
                        if (lib != rank) {
                            libraries_expected++;
                        }
                    }
                    
                    printf("Library %d (leader): Requesting loan counts from %d other libraries\n", 
                        rank, libraries_expected);
                    
                    // Send requests to all other libraries
                    for (int lib = 1; lib <= N_global * N_global; lib++) {
                        if (lib != rank) {
                            int request_msg = MSG_LIBRARY_LOAN_REQUEST;
                            MPI_Send(&request_msg, 1, MPI_INT, lib, 0, MPI_COMM_WORLD);
                            printf("Library %d (leader): Sent loan request to library %d\n", rank, lib);
                        }
                    }
                    
                    // Collect responses from all libraries
                    MPI_Status response_status;
                    while (libraries_responded < libraries_expected) {
                        int response_msg[3];
                        MPI_Recv(response_msg, 3, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, 
                                MPI_COMM_WORLD, &response_status);
                        
                        if (response_msg[0] == MSG_LIBRARY_LOAN_RESPONSE) {
                            long long library_loans = ((long long)response_msg[1] << 32) | 
                                                    (long long)response_msg[2];
                            total_loans += library_loans;
                            libraries_responded++;
                            
                            printf("Library %d (leader): Received %lld loans from library %d (%d/%d)\n", 
                                rank, library_loans, response_status.MPI_SOURCE, 
                                libraries_responded, libraries_expected);
                        }
                    }
                    
                    printf("Library %d (leader): Total library loans: %lld\n", rank, total_loans);
                    printf("Library Books %lld\n", total_loans);
                    
                    // Send result to coordinator
                    MPI_Send(&total_loans, 1, MPI_LONG_LONG_INT, 0, MSG_BOOKS_LOANED_RESULT, MPI_COMM_WORLD);
                    
                    // Send completion message
                    int done_msg = MSG_CHECK_NUM_BOOKS_LOAN_DONE;
                    MPI_Send(&done_msg, 1, MPI_INT, 0, MSG_CHECK_NUM_BOOKS_LOAN_DONE, MPI_COMM_WORLD);
                    printf("Library %d (leader): Sent aggregated result to coordinator\n", rank);
                    
                } else {
                    printf("Library %d: Received CHECK_NUM_BOOKS_LOAN but I'm not leader\n", rank);
                }
                break;
            }

            
            case MSG_DONATE_TO_LIB: {
                int b_id = msg[1];
                printf("Library %d: Received donation of book %d from client/coordinator\n", 
                       rank, b_id);
                
                add_book_to_library(b_id, 1);
                printf("Received donate book %d from %d\n", b_id, rank);
                
                int ack[2] = {MSG_ACK_DB, b_id};
                MPI_Send(ack, 2, MPI_INT, sender, 0, MPI_COMM_WORLD);
                printf("Library %d: Sent donation acknowledgment for book %d\n", rank, b_id);
                break;
            }
            
            case MSG_SHUTDOWN: {
                printf("Library %d: Received shutdown signal\n", rank);
                print_library_status(rank);
                return;
            }
            case MSG_LIBRARY_LOAN_REQUEST: {
                printf("Library %d: Received loan count request from leader %d\n", rank, sender);
                
                // Calculate my total loans
                long long my_loans = 0;
                for (int i = 0; i < book_collection_size; i++) {
                    my_loans += library_books[i].copies_loaned;
                }
                
                printf("Library %d: Sending %lld loans to leader\n", rank, my_loans);
                
                // Send response back to leader (split long long into two ints)
                int response[3] = {
                    MSG_LIBRARY_LOAN_RESPONSE,
                    (int)(my_loans >> 32),    // High 32 bits
                    (int)(my_loans & 0xFFFFFFFF)  // Low 32 bits
                };
                MPI_Send(response, 3, MPI_INT, sender, 0, MPI_COMM_WORLD);
                break;
            }

            case MSG_LIBRARY_LOAN_RESPONSE: {
                // This case is handled in the MSG_CHECK_NUM_BOOKS_LOAN aggregation loop
                // Just log it if received unexpectedly
                printf("Library %d: Received unexpected loan response from %d\n", rank, sender);
                break;
            }
            
            default: {
                printf("Library %d: Unknown message type %d from %d\n", rank, msg[0], sender);
                break;
            }
        }
    }
}