List Library

Author: amin tahmasebi Release Date: 2023 License: ISC License

The List library is a part of a project to reimplement C++ standard library features in C. It provides a generic container that encapsulates dynamic size List, offering similar functionality to std::list in C++.

Compilation

To compile the List library along with your main program, use the following GCC command: if you need other lib just you can add name of libs .c

gcc -std=c11 -O3 -march=native -flto -funroll-loops -Wall -Wextra -pedantic -s -o main ./main.c list/list.c

Ensure you have the GCC compiler installed on your system and that all source files are in the correct directory structure as shown in the project.

Usage

To use the List library in your project, include the list.h header file in your source code.

#include "list/list.h"

Functions Explanations

Here’s an updated documentation with a one-line explanation for each function in the List library:

---

List *list_create(size_t itemSize, CompareFunction compare);

Creates a new list with elements of a specified size and an optional comparison function.

size_t list_length(const List *list);

Returns the number of elements in the list.

void *list_front(const List *list);

Returns the first element in the list.

void *list_back(const List *list);

Returns the last element in the list.

void *list_insert(List *list, size_t index, void *value);

Inserts an element at a specified index in the list.

void *list_erase(List *list, size_t index);

Removes an element from a specified index in the list.

void list_resize(List *list, size_t newSize, void *defaultValue);

Resizes the list to a specified number of elements, filling with a default value if necessary.

void list_swap(List *list1, List *list2);

Swaps the contents of two lists.

void list_reverse(List *list);

Reverses the order of elements in the list.

void list_sort(List *list);

Sorts the elements of the list using the comparison function.

void list_push_front(List *list, void *value);

Adds an element to the front of the list.

void list_push_back(List *list, void *value);

Adds an element to the back of the list.

void list_pop_front(List *list);

Removes the first element from the list.

void list_pop_back(List *list);

Removes the last element from the list.

void list_clear(List *list);

Removes all elements from the list.

bool list_empty(const List *list);

Checks if the list is empty.

void list_deallocate(List *list);

Frees all memory used by the list.

Node *list_begin(const List *list);

Returns the first node in the list.

Node *list_end(const List *list);

Returns the position just past the last node in the list (equivalent to NULL).

Node *list_rbegin(const List *list);

Returns the last node in the list for reverse iteration.

Node *list_rend(const List *list);

Returns the position just before the first node in the list (equivalent to NULL).

const Node *list_cbegin(const List *list);

Returns a constant iterator to the first node in the list.

const Node *list_cend(const List *list);

Returns a constant iterator to the position just past the last node in the list.

const Node *list_crbegin(const List *list);

Returns a constant reverse iterator to the last node in the list.

const Node *list_crend(const List *list);

Returns a constant reverse iterator to the position just before the first node in the list.

void list_assign(List *list, void *values, size_t numValues);

Assigns a set of values to the list, replacing its current content.

void list_emplace_front(List *list, void *value);

Adds an element to the front of the list without copying the value.

void list_emplace_back(List *list, void *value);

Adds an element to the back of the list without copying the value.

void list_splice(List *dest, List *src, Node *pos);

Inserts elements from one list into another at a specified position.

void list_remove(List *list, void *value);

Removes all elements from the list that match a specified value.

void list_remove_if(List *list, ConditionFunction cond);

Removes elements from the list that satisfy a specified condition.

void list_unique(List *list);

Removes consecutive duplicate elements from the list.

void list_merge(List *list1, List *list2);

Merges two sorted lists into one, leaving the second list empty.

bool list_is_less(const List *list1, const List *list2);

Checks if the first list is lexicographically less than the second list.

bool list_is_greater(const List *list1, const List *list2);

Checks if the first list is lexicographically greater than the second list.

bool list_is_equal(const List *list1, const List *list2);

Checks if two lists are lexicographically equal.

bool list_is_less_or_equal(const List *list1, const List *list2);

Checks if the first list is lexicographically less than or equal to the second list.

bool list_is_greater_or_equal(const List *list1, const List *list2);

Checks if the first list is lexicographically greater than or equal to the second list.

bool list_is_not_equal(const List *list1, const List *list2);

Checks if two lists are not lexicographically equal.

Examples

Example 1: Create List and Add Elements Using list_push_back

#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int values[] = {10, 20, 30, 40, 50};

    for (int i = 0; i < 5; ++i) { 
        list_push_back(myList, &values[i]);
    }

    list_deallocate(myList);
    list_deallocate(myList);
    
    return 0;
}

Example 2: Add Elements Using list_push_front

#include <string.h>
#include "fmt/fmt.h"
#include "list/list.h"

static bool compare_string(const void* a, const void* b){
    const char* str_a = *(const char**)a;
    const char* str_b = *(const char**)b;
    return strcmp(str_a, str_b) == 0;
}

int main() {
    List *myList = list_create(sizeof(char*), compare_string);
    char* values[] = {"c++", "C", "Python", "Golang", "Rust"};

    for (int i = 0; i < 5; ++i) { 
        list_push_front(myList, &values[i]);
    }
    for (Node* node = list_begin(myList); node != list_end(myList); node = node->next){
        char* value = *(char**)node->value;
        fmt_printf("%s\n", value);
    }

    list_deallocate(myList);
    return 0;
}

Example 3: Pop Elements from Front list_pop_front

#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int value = 100;

    list_push_front(myList, &value);
    list_pop_front(myList);

    list_deallocate(myList);
    return 0;
}

Example 4: Pop Elements from Back with list_pop_back

#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int value = 100;

    list_push_back(myList, &value);
    list_pop_back(myList);

    list_deallocate(myList);
    return 0;
}

Example 5: Insert Element at Specific Position with list_insert

#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int value = 100;

    list_insert(myList, 0, &value); // Insert at the beginning

    list_deallocate(myList);
    return 0;
}

Example 6: Erase Element at Specific Position with list_erase

#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int value = 100;

    list_push_back(myList, &value);
    list_erase(myList, 0); // Erase the first element

    list_deallocate(myList);
    return 0;
}

Example 7: Clearing the List

#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int value = 100;

    list_push_back(myList, &value);

    list_deallocate(myList);
    return 0;
}

Example 8: Resize the List with list_resize

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *list1 = list_create(sizeof(int), compare_ints);

    int values[] = {50, 40, 30, 20, 10};
    for (int i = 0; i < 5; ++i) { 
        list_push_back(list1, &values[i]);
    }
    list_resize(list1, 10, 0);

    for (Node* node = list_begin(list1); node != list_end(list1); node = node->next){
        int* value = (int*)node->value;
        fmt_printf("%d\n", *value);
    }

    list_deallocate(list1);
    return 0;
}

Example 9: Swap Two Lists with list_swap

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *list1 = list_create(sizeof(int), compare_ints);
    List *list2 = list_create(sizeof(int), compare_ints);
    int values[] = {50, 40, 30, 20, 10};
    int values2[] = {100, 200, 300, 400, 500};

    for (int i = 0; i < 5; ++i) { 
        list_push_back(list1, &values[i]);
    }
    for (int i = 0; i < 5; ++i) { 
        list_push_back(list2, &values2[i]);
    }
    list_swap(list1, list2); // Swap list1 and list2

    for (Node* node = list_begin(list1); node != list_end(list1); node = node->next){
        int* value = (int*)node->value;
        fmt_printf("%d\n", *value);
    }

    list_deallocate(list1);
    list_deallocate(list2);

    return 0;
}

Example 10: Reverse a List with list_reverse

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int values[] = {50, 40, 30, 20, 10};

    for (int i = 0; i < 5; ++i) { 
        list_push_back(myList, &values[i]);
    }
    list_reverse(myList); // Reverse the list_
    
    for (Node* node = list_begin(myList); node != list_end(myList); node = node->next) {
        int* value = (int*)node->value;
        fmt_printf("%d\n", *value);
    }

    list_deallocate(myList);
    return 0;
}

Example 11: Sort a List with list_sort

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int values[] = {50, 40, 30, 20, 10};

    for (int i = 0; i < 5; ++i) { 
        list_push_back(myList, &values[i]);
    }
    list_sort(myList); // Sort the list
    
    for (Node* node = list_begin(myList); node != list_end(myList); node = node->next) {
        int* value = (int*)node->value;
        fmt_printf("%d\n", *value);
    }

    list_deallocate(myList);
    return 0;
}

Example 12: Check if List is Empty with list_empty

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    bool isEmpty = list_empty(myList); // Check if list is empty

    fmt_printf("%s\n", isEmpty? "Yes its empty": "No its not empty");

    list_deallocate(myList);
    return 0;
}

Example 13: Get the Length of the List with list_length

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int value = 100;

    list_push_back(myList, &value);
    size_t length = list_length(myList); // Get the length of the list

    fmt_printf("Size of List %zu\n", length);
    
    list_deallocate(myList);
    return 0;
}

Example 14: Assign Values to List with list_assign

#include "fmt/fmt.h"
#include "list/list.h"

static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *myList = list_create(sizeof(int), compare_ints);
    int values[] = {1, 2, 3, 4, 5};

    list_assign(myList, values, 5); // Assign values to list
    for (Node* node = list_begin(myList); node != list_end(myList); node = node->next){
        int* value = (int*)node->value;
        fmt_printf("%d\n", *value);
    }

    list_deallocate(myList);
    return 0;
}

Example 15: Merge Two Lists with list_merge

#include "list/list.h"


static int compare_ints(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

int main() {
    List *list1 = list_create(sizeof(int), compare_ints);
    List *list2 = list_create(sizeof(int), compare_ints);
    int value1 = 10, value2 = 20;

    list_push_back(list1, &value1);
    list_push_back(list2, &value2);
    list_merge(list1, list2); // Merge list2 into list1

    list_deallocate(list1);
    list_deallocate(list2);
    return 0;
}

Example 16 : Storing Strings in a List and Sorting

// Function to compare two strings in the list
#include "fmt/fmt.h"
#include "list/list.h"
#include "string/string.h"

static int compare_strings(const void* a, const void* b) {
    String* strA = *(String**)a;
    String* strB = *(String**)b;

    return string_is_less(strA, strB) ? -1 : string_is_greater(strA, strB);
}

int main() {
    List* stringList = list_create(sizeof(String*), compare_strings);
    String* str1 = string_create("Apple");
    String* str2 = string_create("Banana");
    String* str3 = string_create("Cherry");

    list_push_back(stringList, &str1);
    list_push_back(stringList, &str2);
    list_push_back(stringList, &str3);
    list_sort(stringList); // Sort the list of strings

    for (Node* node = list_begin(stringList); node != list_end(stringList); node = node->next) {
        String* str = *(String**)node->value;
        fmt_printf("%s\n", string_c_str(str));
    }

    string_deallocate(str1);
    string_deallocate(str2);
    string_deallocate(str3);
    list_deallocate(stringList);

    return 0;
}

Example 17: Merging Two Lists of Strings

#include "string/string.h"

#include "fmt/fmt.h"
#include "list/list.h"
#include "string/string.h"

int main() {
    List* list1 = list_create(sizeof(String*), NULL);
    List* list2 = list_create(sizeof(String*), NULL);
    String* str1 = string_create("Hello");
    String* str2 = string_create("World");
    String* str3 = string_create("Example");
    String* str4 = string_create("Text");

    list_push_back(list1, &str1);
    list_push_back(list1, &str2);
    list_push_back(list2, &str3);
    list_push_back(list2, &str4);
    list_merge(list1, list2); // Merge list2 into list1

    for (Node* node = list_begin(list1); node != list_end(list1); node = node->next) {
        String* str = *(String**)node->value;
        fmt_printf("%s\n", string_c_str(str));
    }

    string_deallocate(str1);
    string_deallocate(str2);
    string_deallocate(str3);
    string_deallocate(str4);
    list_deallocate(list1);
    list_deallocate(list2);

    return 0;
}

Example 18: Filtering Strings from a List

#include "fmt/fmt.h"
#include "list/list.h"
#include "string/string.h"

// Condition function to filter out short strings
static bool filter_short_strings(void* value) {
    String* str = *(String**)value;
    return string_length(str) < 5;
}

int main() {
    List* stringList = list_create(sizeof(String*), NULL);
    String* str1 = string_create("Apple");
    String* str2 = string_create("Banana");
    String* str3 = string_create("Kiwi");

    list_push_back(stringList, &str1);
    list_push_back(stringList, &str2);
    list_push_back(stringList, &str3);
    list_remove_if(stringList, filter_short_strings); // Remove short strings

    for (Node* node = list_begin(stringList); node != list_end(stringList); node = node->next) {
        String* str = *(String**)node->value;
        fmt_printf("%s\n", string_c_str(str));
    }

    string_deallocate(str1);
    string_deallocate(str2);
    string_deallocate(str3);
    list_deallocate(stringList);

    return 0;
}

Example 19: Concatenating All Strings in a List

#include "fmt/fmt.h"
#include "list/list.h"
#include "string/string.h"

int main(){
    List* stringList = list_create(sizeof(String*), NULL);
    String* concatenated = string_create("");
    String* str1 = string_create("Hello, ");
    String* str2 = string_create("world");
    String* str3 = string_create("!");

    list_push_back(stringList, &str1);
    list_push_back(stringList, &str2);
    list_push_back(stringList, &str3);

    for (Node* node = list_begin(stringList); node != list_end(stringList); node = node->next){
        String* str = *(String**)node->value;
        string_append(concatenated, string_c_str(str));
    }
    fmt_printf("Concatenated String: %s\n", string_c_str(concatenated));

    string_deallocate(str1);
    string_deallocate(str2);
    string_deallocate(str3); 
    string_deallocate(concatenated);
    list_deallocate(stringList);

    return 0;
}

Example 20: Reversing Each String in a List

#include "fmt/fmt.h"
#include "list/list.h"
#include "string/string.h"

int main() {
    List* stringList = list_create(sizeof(String*), NULL);
    String* str1 = string_create("Hello");
    String* str2 = string_create("World");
    String* str3 = string_create("Example");

    list_push_back(stringList, &str1);
    list_push_back(stringList, &str2);
    list_push_back(stringList, &str3);

    // Reverse each string
    for (Node* node = list_begin(stringList); node != list_end(stringList); node = node->next) {
        String* str = *(String**)node->value;
        String* reversed = string_create(""); 

        for (int i = string_length(str) - 1; i >= 0; --i) {
            string_push_back(reversed, string_c_str(str)[i]);
        }
        fmt_printf("Reversed String: %s\n", string_c_str(reversed));
        string_deallocate(reversed);
    }

    string_deallocate(str1);
    string_deallocate(str2);
    string_deallocate(str3);
    list_deallocate(stringList);

    return 0;
}

Example 21 : Relational operators in List

#include "fmt/fmt.h"
#include "list/list.h"

// Function to compare integers for the list
static int int_compare(const void* a, const void* b) {
    int int_a = *(const int*)a;
    int int_b = *(const int*)b;
    return (int_a > int_b) - (int_a < int_b);
}

// Function to add elements to a list
void add_elements_to_list(List* list, int* elements, size_t numElements) {
    for (size_t i = 0; i < numElements; ++i) {
        list_push_back(list, &elements[i]);
    }
}

int main() {
    List* list1 = list_create(sizeof(int), int_compare);
    List* list2 = list_create(sizeof(int), int_compare);
    int elements1[] = {1, 2, 3, 4, 5};
    int elements2[] = {1, 2, 3, 4, 6};

    add_elements_to_list(list1, elements1, 5);
    add_elements_to_list(list2, elements2, 5);

    // Perform relational comparisons
    fmt_printf("List 1 is less than List 2: %s\n", list_is_less(list1, list2) ? "true" : "false");
    fmt_printf("List 1 is greater than List 2: %s\n", list_is_greater(list1, list2) ? "true" : "false");
    fmt_printf("List 1 is equal to List 2: %s\n", list_is_equal(list1, list2) ? "true" : "false");
    fmt_printf("List 1 is less than or equal to List 2: %s\n", list_is_less_or_equal(list1, list2) ? "true" : "false");
    fmt_printf("List 1 is greater than or equal to List 2: %s\n", list_is_greater_or_equal(list1, list2) ? "true" :"false");
    fmt_printf("List 1 is not equal to List 2: %s\n", list_is_not_equal(list1, list2) ? "true" : "false");

    list_deallocate(list1);
    list_deallocate(list2);

    return 0;
}

Example 22 : add and remove child

#include "list/list.h"
#include "fmt/fmt.h"
#include "string/string.h"
#include <stdlib.h>


typedef struct {
    const char* name;
    Node registry_links;
} Child;

Child* create_child(const char* name) {
    Child* new_child = (Child*)malloc(sizeof(Child));
    if (!new_child) {
        fmt_fprintf(stderr, "Error: Memory allocation failed for new Child.\n");
        exit(-1);
    }

    new_child->name = string_strdup(name); 
    new_child->registry_links.next = NULL;
    new_child->registry_links.prev = NULL;
    new_child->registry_links.value = new_child;

    return new_child;
}

void child_unlink(List* list, Child* c) {
    list_remove(list, c);
}

static int compare_nodes(const void* a, const void* b) {
    const Child* Child_a = (const Child*)a;
    const Child* Child_b = (const Child*)b;

    return string_strcmp(Child_a->name, Child_b->name);
}

void deallocate(List* children_registry, Child** children, size_t num_children) {
    for (size_t i = 0; i < num_children; ++i) {
        free((void*)children[i]->name);
        free(children[i]);
    }

    list_deallocate(children_registry);
}

int main() {
    const char* names[] = {"Marry", "Bob", "Sally"};
    size_t num_children = sizeof(names) / sizeof(names[0]);

    List* children_registry = list_create(sizeof(Child), compare_nodes);
    Child* children[num_children];

    for (size_t i = 0; i < num_children; ++i) {
        children[i] = create_child(names[i]);
        list_push_back(children_registry, children[i]);
    }

    child_unlink(children_registry, children[1]);

    for (Node* node = list_begin(children_registry); node != list_end(children_registry); node = node->next) {
        Child* c = (Child*)node->value;
        fmt_printf("%s\n", c->name);
    }

    deallocate(children_registry, children, num_children);

    return 0;
}