Forem: Lautaro Jayat

Implementing a hash table with separate chaining for collisions resolution

Lautaro Jayat — Wed, 05 Jul 2023 22:20:22 +0000

Table of contents

What is a hash table?
A collision resolution strategy
Implementing the hash table
Linked list related operations
- Defining interfaces
- Creating a node
- Testing node creation
- Clearing the list
- Testing list deletion
- Removing a node from the list
- Testing node removal
Hash table related operations
- Creating a hash table
- Testing hash table creation
- Storing a key-value pair in our hash table
- Implementing a simple hash function
- Testing our hashing function
- Checking if we need to resize
- Doing the actual resizing
- Testing the resizing
- Getting a value from the hash table
- Removing a key-value pair from the hash table
- Testing a complete flow
- Link to source code

What is a hash table?

A hash table can be described as a collection of key-value pairs where:

Each key appears at most once.
Each key maps to only one value.
A function is used to consistently map the potentially infinite space of possible keys to finite domain of "hash codes" that we can handle.

In respect to the third bullet point mentioned above, the underlying problem the hash function solves is as follows:

If we have a limited number of keys, and time is not a problem, we could store key-value pairs in a linked list or an array. Then, if we want to look for a value, we just traverse the whole collection, comparing our input key with each key we have stored.

Although the approach is simple, it implies that the number of lookups needed to find a value might grow as the number of stored keys also grows. To avoid this, a function is used to convert a key into something that gives us a hint about where the key is located in memory, without needing to traverse the entire collection.

The functions that make this work are called "hashing functions."

A useful hashing function should be fast to compute without wasting too many resources. If it's not, each lookup may have a consistent time but could be slower than the entire traversing and comparing approach mentioned above.

It should also minimize the probability of outputting the same value for two different inputs, which is commonly called a "collision."

As we just mentioned, we are talking about "minimizing" collisions rather than trying to avoid them completely. This is because we are mapping an infinite set of possible keys to a finite set of possible outputs. Collisions will be inevitable at some point.

A collision resolution strategy

Collisions can be minimized, but they cannot be avoided. This means we need a way to handle these collisions.

For this article, we have chosen to start with what is called "separate chaining", which consists on using linked lists to store all key-value pairs where different key maps to the same output after being passed to our hash function. This way, every time we want to store a key-value pair, we first compute the hash, then we look for the head node corresponding to that hash and traverse the list, comparing each stored key with the input key.

The approach still implies a linear time complexity for the step where we traverse the entire linked list in search of the provided key, but now the universe of possible keys is reduced to a fraction of the original.

Furthermore, in the design, we can decide how many elements can be stored in a linked list or the limit for the ratio between available linked lists and overall elements stored, and resize the entire data structure accordingly.

Implementing the hash table

To present this data structure, we will first introduce the interfaces we are going to use. Then we will move on to the linked list-related operations. Each of them will have comments to guide the reader through the code, along with some quick tests to understand how they behave.

Finally, we will proceed to the hash table-related functions, providing implementation details and additional tests. The intention is to progress from bottom to top, from the lower level to the integration level.

Defining interfaces

Our hash table will consist of a struct containing:

the number of elements already stored
an array of pointers that leads to the head of a linked list
a number representing the size of the array above

typedef struct {
    Node** collection;
    unsigned int capacity;
    unsigned int storedElements;
} HashTable;

For the collection, we are using a pointer-to-pointer semantic just to simplify the process of changing the head of the linked list.

Then, for the nodes, we will use structs containing the following:

a pointer to where we will store the key
a pointer to where we will store the value
a pointer to the next element in the list

typedef struct Node_T {
    char key[MAX_KEY_LEN];
    char value[MAX_VALUE_LEN];
    struct Node_T* next;
} Node;

Apart from that, we will define certain numbers to constrain the behavior of the linked list:

#define MAX_KEY_LEN 256
#define MAX_VALUE_LEN 256
#define INITIAL_CAPACITY 10
#define GROWTH_FACTOR 2

For the API of our hash table, we will support the following operations:

creating a hash table
storing a key-value pair
removing a key-value pair
looking up a value for a given key.

The function signatures for these operations will be as follows:

HashTable* CreateHashTable(unsigned int capacity);
bool Store(HashTable** hashTable, char* key, char* value);
char* Get(HashTable* hashTable, char* key);
bool Remove(HashTable* hashTable, char* key);

For convenience, we will create a separate set of functions that handle linked list operations such as creating a node, removing a node, getting the value of a node, and clearing a whole list.
The function signatures for these operations will be as follows:

Node* CreateNode(char* key, char* value);
bool RemoveNode(Node** head, char* key);
unsigned int ClearList(Node** headNode);
char* GetNodeValue(Node* head, char* key);

Lastly, there are a couple of additional "internal" functions that will be needed for determining when to resize the hash table, computing the hash, and performing the actual resizing:

unsigned int _computeHash(char* key, unsigned int capacity);
bool _needsToResize(HashTable* hashTable);
HashTable* _resize(HashTable* hashTable);

Linked list related operations

We won't be providing a comprehensive explanation of linked lists here, as we have covered this topic in a previous chapter.
If you have never heard about this data structure, please follow this link.

Here, we will only cover the necessary operations to integrate linked lists within our hash table.

Creating a node

When creating a node, we want to check that both the key and the value are valid pointers to a string, and also that their lengths are within the bounds we want to handle.
Then, we will allocate memory for the struct and copy the key and value to the corresponding fields in the struct.
At this point, we don't care if the keys already exist in a node of our linked list. That will be handled at a higher scope.

// We accept the pointers to the strings and return a pointer to a node
Node* CreateNode(char* key, char* value) {
    // are the pointers valid?
    if (key == NULL || value == NULL) {
        printf("error: key and value must be string\n");
        return NULL;
    }

    // are the lengths of the strings valid?
    if (strlen(key) > MAX_KEY_LEN || strlen(value) > MAX_VALUE_LEN) {
        printf("error: key and value should not exceed max lengths\n");
        return NULL;
    }

    // At this point we can start asking for memory
    Node* newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("error: could not allocate memory for new node\n");
        return NULL;
    }
    // by default we set the next pointer to null
    // the calling function will take care of setting the correct value
    newNode->next = NULL;

    // then we copy the key and the value to their buffers in the struct
    strcpy(newNode->key, key);
    strcpy(newNode->value, value);

    // And we return the pointer to the new node
    return newNode;
};

Notice that we are using functions declared in string.h for string manipulation. Here we are using strlen to get the length of a string. It accepts a pointer to a string and returns a number representing the length. Then we are using strcpy to copy a string into a buffer.

Testing node creation

To test the function described above we will do the following:

void _testNewNode() {
    // we will use this as a temp variable to store a string
    char* s;
    // this will be used as a good input
    char* goodString = "hey how are you?";
    // here we will create a string that exceeds the limits for
    // our string length
    int i;
    char badString[MAX_KEY_LEN + 3000];
    for (i = 0; i < MAX_KEY_LEN + 20; i++) {
        badString[i] = *"!";
    }

    // We create a new node with correct inputs
    // and check everything was stored correctly
    Node* newNode = CreateNode(goodString, goodString);
    s = newNode->key;
    assert(*s == *goodString);
    s = newNode->value;
    assert(*s == *goodString);
    free(newNode);
    printf("Testing with good string: PASS\n");

    // Now we provide an invalid poiner and expect
    // the function to return NULL
    Node* newNode2 = CreateNode(NULL, goodString);
    assert(newNode2 == NULL);
    free(newNode2);
    printf("Testing with null string pointer: PASS\n");

    // Now we provide a long string and expect a NULL pointer
    Node* newNode3 = CreateNode((char*)badString, goodString);
    assert(newNode3 == NULL);
    free(newNode3);
    printf("Testing with bad string: PASS\n");
}

Clearing the list

To clear the list, we will take a pointer to a head node and then iterate over all its members. Each node will be freed, and then the head will be set to NULL.
To provide feedback, we will return the number of nodes that were removed.

// we receive the pointer of the head node
// and return an integer with the number of nodes that were deleted.
unsigned int ClearList(Node** headNode) {
    // we access the head node
    Node* head = *headNode;
    // and set a temporary node that will help us in the iteration
    Node* tmp;
    // we create a counter
    unsigned int deletedNodes = 0;
    // and start a loop that will end when the current node is NULL
    while (head != NULL) {
        // we store the current node ina  tmp variable
        tmp = head
        // we assign the next node as the current node
        head = tmp->next;;
        // free the current node
        free(head);
        // and update the counter
        deletedNodes++;
    }

    // finaly we update where the caller pointer is pointing to
    *headNode = NULL;
    printf("deleted %d nodes, linked list is now empty\n", deletedNodes);
    // and we return the counter
    return deletedNodes;
};

Testing list deletion

A simple test of the happy path can be done by creating a list with an arbitrary number of nodes and then passing the list into our function.
After that, we can assert if the returned value corresponds to the number of nodes we created.

void _testClearList() {
    // we create a valid stirng for input and output
    char goodString[] = "to delete";
    // we set the number of values we want our list to have
    unsigned int expectedNodes = 10;
    // start a counter
    unsigned int i;
    // we create the first node
    Node* head = CreateNode(goodString, goodString);
    // and we add loop to generate the rest of the nodes
    for (i = 1; i < expectedNodes; i++) {
        // we store the current head
        Node* tmp = head;
        // assign which should be the new head
        head = CreateNode(goodString, goodString);
        // and update the next node with the old head
        head->next = tmp;
    };
    // we clear the list and store the result
    unsigned int clearedNodes = ClearList(&head);
    // the result should be equal to the nodes we created
    assert(clearedNodes == expectedNodes);
}

Removing a node from the list

To remove a node from the list, we need to access the list using the head node. Then, we traverse the list until we find the key we are looking for.
When we find the key, we free that node and make the previous node point to the node that comes after the deleted one.
If the target node is the head node, we simply delete the head and assign the next node as the new head.
In our implementation, we will return a boolean value to indicate whether the process succeeded or not.

// we accept a pointer to a pointer to the head node
// and a pointer that holds a reference to the key we
// are loking for
bool RemoveNode(Node** headP, char* key) {
    // first we check if the pointers are valid
    if (headP == NULL || *headP == NULL) {
        printf("could not remove node, the list is empty\n");
        return false;
    }
    // then we dereference to access the actual head
    Node* currentNode = *headP;

    // we check if the head node is the one we are looking for
    if (strcmp(currentNode->key, key) == 0) {
        // in case it is, we assign the next node as the new head
        *headP = currentNode->next;
        // we free the one we want to remove
        free(currentNode);
        // and return a success
        return true;
    }
    // at this point we know we need to traverse the list
    // so we store a reference to the next node
    Node* nextNode = currentNode->next;
    // and start looping and checking until we reach the end
    while (nextNode != NULL) {
        // if the next node is the node we are looking for
        if (strcmp(nextNode->key, key) == 0) {
            // make the previous (currentNode) point to
            // the next node of the one we are going to remove
            currentNode->next = nextNode->next;
            // then we remove the one we found
            free(nextNode);
            // and return
            return true;
        }
        // if not, we just move one step
        // and update the pointers for the next iteration
        currentNode = nextNode;
        nextNode = nextNode->next;
    }
    // if we reach this point, that means the key was not in any
    // of the stored pointers
    printf("node of key %s could not be found\n", key);
    return false;
};

Testing node removal

To test if the node removal is working, we will assert for success or failure by using the boolean output of our function.

void _testRemoveNode() {
    // We will use this string for key-values we dont want to delete
    char notToDelete[] = "do not delete me";
    // we will use this to mark a node to delete
    char toDelete[] = "to delete";

    int i;
    printf("Testing deletion of the last node\n");
    // We create the head node, this will end up at the tail
    Node* head = CreateNode(toDelete, toDelete);
    // we prepend 3 more nodes that we dont want to delete
    for (i = 1; i < 4; i++) {
        Node* tmp = head;
        head = CreateNode(notToDelete, notToDelete);
        head->next = tmp;
    };
    // we decide to remove the last node
    bool success = RemoveNode(&head, toDelete);
    // and assert
    assert(success == true);

    printf("Testing deletion of node in the middle\n");
    // now we will delete a node in the middle
    Node* deleteMeNode = CreateNode(toDelete, toDelete);
    deleteMeNode->next = head;
    head = deleteMeNode;
    // and make a sandwich prepending 3 more nodes
    for (i = 1; i < 4; i++) {
        Node* tmp = head;
        head = CreateNode(notToDelete, notToDelete);
        head->next = tmp;
    };
    // we remove the node
    success = RemoveNode(&head, toDelete);
    // and everything went OK
    assert(success == true);

    printf("Testing deletion of the head node\n");
    // now we prepend one node and delete it
    deleteMeNode = CreateNode(toDelete, toDelete);
    deleteMeNode->next = head;
    head = deleteMeNode;
    // we try to remove it
    success = RemoveNode(&head, toDelete);
    // and everything
    assert(success == true);

    printf("Testing early return when providing empty lists\n");
    Node* badPointer = NULL;
    success = RemoveNode(NULL, toDelete);
    assert(success == false);
    success = RemoveNode(&badPointer, toDelete);
    assert(success == false);
    while (head != NULL) {
        Node* tmp = head->next;
        free(head);
        head = tmp;
    }
}

If desired, we could also traverse the list to assert that there is no node with the key we wanted to remove.

Getting a node value

To traverse the linked list and find a value by a key, we will accept a pointer to the head node and a key. We will validate that those pointers are not null pointers. If everything is fine, we will loop over each node, comparing the input string with each key of each node.
If we find a match, we will allocate memory for that string and return a pointer to that buffer.
If no match is found, we will return null.
It will be the responsibility of a higher scope to free that allocated memory.

// We receive a pointer to to the head
// a pointer to a string
// and we return a pointer to a copy of the string
char* GetNodeValue(Node* head, char* key) {
    // we check if the pointers are valid
    if (head == NULL) {
        printf("could not find node because the list was empty\n");
        return NULL;
    }

    if (key == NULL) {
        printf("cant check for node value due to nil key\n");
        return NULL;
    }
    Node* tmp = head;

    // if so, we start iterating over each node
    // we will stop if the key the same as our input
    // or if we reach the last
    while (tmp != NULL && strcmp(tmp->key, key) != 0) {
        tmp = tmp->next;
    }

    // at this point, if tmp is null is because we exited the loop
    // after checking the last node and we didn't find anything
    if (tmp == NULL) {
        // so we return
        return NULL;
    }

    // if we reach this line, this mean we found something
    // so we ask for a block of memory of the size we need
    char* buff = malloc(strlen(tmp->value) * sizeof(char*));
    // but we exit if we could not allocate that memory
    if (buff == NULL) {
        return NULL;
    }
    // in the best case scenario we copy the key to our buffer
    strcpy(buff, tmp->value);
    // and return the buffer
    return buff;
}

Hash table related operations

To simplify things, we can say that our hash table is essentially a dynamic array of pointers to the head of a linked list.
To determine in which linked list a key-value pair should be stored, we pass the key to a hash function that outputs a number between 0 and the number of slots in our array.
Here's a conceptual example:

# each key maps to a given index
hash(k1) -> 0
hash(k2) -> 2
hash(k3) -> 3

[   0   ,   1   ,   2   ,   3   ,   4   ]
    |       |       |       |       |
  k1-v1    NULL   k2-v2   k3-v3    NULL

Then, if a new key maps to an index where the linked list already has a value, we link the new node to it:

# a new value maps to an index where
# the linked list already has a value
hash(k4) -> 0

# so we bind the new node
[   0   ,   1   ,   2   ,   3   ,   4   ]
    |       |       |       |       |
  k4-v4    NULL   k2-v2   k3-v3    NULL
    |
  k1-v1

Creating a hash table

As we presented above in the section on defining interfaces, our hash table is implemented as a struct that contains an array of pointers to linked lists, along with two numbers: one to keep track of the elements stored and the other to indicate the array capacity.

Creating an instance of this struct is straightforward. We provide a number representing the desired capacity, attempt to allocate the necessary memory, and set the defaults as shown in the following example:

// we return a pointer to the hash table
// and accept an int for the capacity
HashTable* CreateHashTable(unsigned int capacity) {
    // if capacity is less than an arbitrary number
    // we set a default capacity
    if (capacity < 4) {
        capacity = 10;
    }

    // we try to allocate an array of pointers to
    // linked lists head pointers
    Node** collection = calloc(capacity, sizeof(Node*));
    // And return if the operation failed
    if (collection == NULL) {
        printf("error: could not initialize underlying collection\n");
        return NULL;
    }
    // At this point we can try to allocate the memory for the hash table.
    HashTable* hashTable = malloc(sizeof(HashTable));

    // If we fail we free the array previously allocated
    if (hashTable == NULL) {
        printf("error: could not initialize hash table\n");
        free(collection);
        return NULL;
    }

    // now we set all the fields and return
    hashTable->collection = collection;
    hashTable->capacity = capacity;
    hashTable->storedElements = 0;
    return hashTable;
}

Testing hash table creation

We will include some simple assertions for the previous function. We want to verify if the capacity and defaults are correctly set.

void _testCreateHashTable() {
    // first we create a hash table with a capacity
    // that is lower than our min accepted value
    HashTable* hashTable = CreateHashTable(3);
    // so we expect it to be the default value
    assert(hashTable->capacity == 10);

    // we free everything
    free(hashTable->collection);
    free(hashTable);
    // and now we create one with an OK capacity
    hashTable = CreateHashTable(15);

    // and we assert it is using our input
    // to set this field
    assert(hashTable->capacity == 15);

    // as a final step we can iterate and see that
    // all slots are NULL pointers
    unsigned int i;
    for (i = 0; i < 15; i++) {
        assert(hashTable->collection[i] == NULL);

    }
    // and we clean everything up
    free(hashTable->collection);
    free(hashTable);
}

Storing a key-value pair in our hash table

Now we come to the part where we start performing useful operations with our hash table!
Please note that there are three steps that will be somewhat abstract for us at this point. These steps involve checking if we need to resize our hash table, the actual resizing process, and the operation where we compute the hash. These "private" functions will be presented after this section.

Note: Just for presentation purposes, we will include tests for storing, getting, and removing values at the end of the article.

To store a value, we need to follow the following flow:

check that our provided inputs are valid
check if we need to resize the hash table, and if so, perform the resizing
Compute the hash for the key to determine which linked list should store our value
Traverse the list and check if a node with the same key exists. If a matching node is found, update its value; otherwise, append a new node to the list.

Please find some guidance in the comments:

// we will return boolean to signal if the process succeeded
// and receive a pointer to a hash table, a key and a value
bool Store(HashTable** hashTableP, char* key, char* value) {
    // if some of the inputs is a NULL pointer, we return
    if (hashTableP == NULL || *hashTableP || key == NULL || value == NULL) {
        printf("error: bad values provided\n");
        return false;
    }
    // get our actual pointer in a handy variable
    HashTable* hashTable = *hashTableP;

    // we check if the hash table needs to be resized
    // and we do it if so
    if (_needsToResize(hashTable)) {
        printf("needs to resize\n");
        // try to resize
        HashTable* newHashtable = _resize(&hashTable);
        if (newHashTable != NULL) {
            // we replace everything if succeeded
            *hashTableP = newHashTable;
            hashTable = newHashTable;
        } // or print and error if not
        else printf("error: could not resize hash table, we will try on next Store operation\n");
    }

    // and now we compute the hash using the capacity of the array
    // used to store the number of buckets for our linked lists
    unsigned int position = _computeHash(key, hashTable->capacity);

    // and we get the head node of our hash table
    Node* head = hashTable->collection[position];

    // we traverse it and check our node key
    // with the provided key
    while (head != NULL) {
        if (strcmp(head->key, key) == 0) {
            // in case we find a node with the
            // same key, we exit the loop
            break;
        }
        // if not, we go to the next node
        head = head->next;
    }

    // at this point we migth have a node stored in
    // the "head" variable.
    if (head != NULL) {
        // if so, we copy our value to the "value"
        // field in the found node
        strcpy(head->value, value);
        return true;
    }

    // if we didn't find it, we create a new node
    Node* newNode = CreateNode(key, value);

    // if the node couldn't be created, we return
    if (newNode == NULL) {
        printf("error: could not alocate memory for node\n");
        return false;
    }
    // if everything went ok, we prepend the new node
    newNode->next = hashTable->collection[position];
    hashTable->collection[position] = newNode;
    return true;
}

Implementing a simple hash function

NNow, let's focus on the function that takes a key and produces a number that will serve as an index for the underlying array used to store references to the heads of our linked lists. As the array grows, we need to be able to update the range within which this number should fall.
For our implementation we will be using a simplified version of a rolling hash strategy In this strategy, we iterate over each character of the key, producing a hash, and then use that hash to compute the next one. In each iteration, we will take the modulo operation to ensure that our results fall within the desired bounds.

// we accept a pointer to where our key lies and
// a number for the upper limit four our hash
unsigned int _computeHash(char* key, unsigned int capacity) {
    // our hash starts with 0
    unsigned int hash = 0;
    // as our counter
    unsigned int counter = 0;
    // and we select a multiplier
    unsigned int primeNumber = 31;
    //then we loop over the string
    while (key[counter] != '\0') {
        // we multiply our hash with and add the curren character
        hash = (hash * primeNumber) + key[counter];
        // and update the hash
        hash = hash % capacity;
        counter++;
    }
    // finally we return a number that will be between 0
    // and our upper limit (which happens to be our array capacity)
    return hash;
}

Testing our hashing function

Now, our goal is to test whether our hash function consistently produces the same output for a given key. We'll conduct a simple test to gauge the consistency of the results when we manipulate the upper limit of the hash value and repeat the operation multiple times with same key.

However, it's important to note that this test is not an absolute proof of consistency or a demonstration of homogeneous distribution of the hash values. To provide such proof, we would need a formal, logical, and mathematical demonstration, which exceeds the scope of this article.

void _testCreateHashConsistency() {
    // we will use a simple string
    char* string = "hey, how are you";
    // and two counters
    int i, j;
    // we will compute a hash for 990 different capacities
    for (j = 10; j < 1000; j++) {
        unsigned int hash = _computeHash(string, j);
        // and then generate the hash 100 times
        for (i = 0; i < 100; i++) {
            // and check those 100 times we received the same hash
            assert(hash == _computeHash(string, j));
        }
    }
}

Checking if we need to resize

Determining when to resize our hash table is somewhat arbitrary. A common approach is to calculate a ratio between the number of buckets or linked lists available and the number of elements stored in our data structure.

To implement this operation, we will accept a hash table as input and calculate whether adding one more element would cause the ratio to exceed our predetermined limit.

// We return a boolean and accept a hash table
bool _needsToResize(HashTable* hashTable) {
    // we calculate the ratio between the actual stored elements plus one
    // and the current capacity (the number of buckets for our linked lists)
    // as our numbers were int, we need to cast them to float first
    float ratio = (float)(hashTable->storedElements + 1) / (float)hashTable->capacity;
    // if the ratio is greater than 1.5 we know we need to resize
    if (ratio > (float)1.5) {
        return true;
    }
    // if less, we can continue adding nodes
    return false;
};

Doing the actual resizing

To resize our hash table, we follow a process of creating a new hash table with a larger capacity, which means more buckets for storing linked lists. We then traverse all the existing linked lists and attempt to store their elements in the new hash table. To simplify this process, we can use the same Store method that we implemented for our hash tables.

Once all elements have been copied to the new hash table, we can free the memory occupied by the old hash table and return a pointer to the new hash table. If we encounter any issues during the allocation process, we need to clean up all allocated memory and inform the upper scope to handle the failure appropriately.

// we accept a pointer to a hash table and return a pointer to a hash table
HashTable* _resize(HashTable* hashTable) {
    // We store the pointer to avoid mutating parameters
    HashTable* oldHashTable = hashTable;
    // we try to allocate memory for the new hash table
    HashTable* newHashTable = CreateHashTable(oldHashTable->capacity * GROWTH_FACTOR);
    // And return if we failed
    if (newhashtable == NULL){
        return NULL
    }

    unsigned int i;
    bool success = true;
    // then we will loop over all linked lists
    for (i = 0; i < oldHashTable->capacity; i++) {
        Node* currentNode = oldHashTable->collection[i];
        // And for each linked list, we will loop for all its nodes
        while (currentNode != NULL) {
            // we will try to store the node in the new linked lists
            // while keeping track if we succeeded
            success = Store(&newHashTable, currentNode->key, currentNode->value);
            // we return if there was a problem
            if (!success) break;
            // and continue with the next node if everything went ok
            currentNode = currentNode->next;
        }
        // if we exited the while loop with an error, we stop the outer loop too
        if (!success) {
            printf("error: could not complete sesizing\n");
            break;
        }
    }

    // if we succeeded we can clear the old hash table
    if (success) {
        int i;
        for (i = 0; i < oldHashTable->capacity; i++) {
            ClearList(&hashTable->collection[i]);
        }
        free(oldHashTable->collection);
        free(oldHashTable);
        printf("success!!\n");
        return newHashTable;
    }
    printf("cleaning up after resizing attempt\n");
    // at this point we know we failed and we need to clean the new hash table
    for (i = 0; i < newHashTable->capacity; i++) {
        Node* currentNode = newHashTable->collection[i];
        while (currentNode != NULL) {
            Node* tmp = currentNode->next;
            free(currentNode);
            currentNode = tmp;
        }
    }
    free(newHashTable->collection);
    free(newHashTable);
    return NULL;
};

Testing the resizing

To verify if the resizing operation is being performed correctly, we can do a simple check by attempting to store fifty key-value pairs in the hash table and then checking if the capacity has changed. This check can help us confirm if the resizing process is triggered and if the capacity of the hash table is updated accordingly.

void _testResizing() {
    // we create a buffer for our strings
    char input[256];
    // initialize some ints
    int i, INITIAL_CAP;
    INITIAL_CAP = 5;
    // create a little hash table
    HashTable* hashTable = CreateHashTable(INITIAL_CAP);
    // and assert the initial conditions
    assert(hashTable->capacity == INITIAL_CAP);
    // then we procedurally create some key-values
    // and try to store them in the hash table
    for (i = 0; i < 50; i++) {
        sprintf(input, "string_%d", i);
        bool success = Store(&hashTable, input, input);
        assert(success == true);
    }
    // at this point the capacity should be pretty higher
    // than te initial one
    assert(hashTable->capacity > INITIAL_CAP);
    // finally we clean everything up
    for (i = 0; i < hashTable->capacity; i++) {
        ClearList(&hashTable->collection[i]);
    }
    free(hashTable->collection);
    free(hashTable);
}

Getting a value from the hash table

To retrieve a value by its key from the hash table, we need to perform the following steps:

Validate that both the hash table and the key are valid inputs.
Calculate the hash of the key using our hash function. This will give us the index of the linked list where the value may be stored.
If the slot for that linked list is empty, it means the key is not present in our hash table. We return null to indicate the absence of a value.
If we find a linked list in that slot, we need to search for the key within the linked list. We delegate this search operation to our GetNodeValue function.
The GetNodeValue function will traverse the linked list, comparing each node's key with the input key. If a matching key is found, we return the corresponding value.
If we reach the end of the linked list without finding a matching key, we return null to indicate that the key is not present in our hash table.

//we get a pointer to a hash table, and a pointer to a string
char* Get(HashTable* hashTable, char* key) {
    // if the pointers are NULL, or the string is empty, we consider that an error
    if (hashTable == NULL || key == NULL || strlen(key) == 0) {
        printf("error: bad values were provided:\n%p\n%s\n%ld\n", hashTable, key, strlen(key));
        return NULL;
    }
    // at this point we can compute the hash
    unsigned int position = _computeHash(key, hashTable->capacity);
    // and get the correct linked list
    Node* head = hashTable->collection[position];
    // then we check if we need to return
    if (head == NULL) return NULL;
    // If not, we delegate the rest of the flow
    char* value = GetNodeValue(head, key);
    // and return what the GetNodeValue give us
    return value;
};

Remving a key-value pair from the hash table

To remove a key-value pair from the hash table, we need to follow these steps:

Validate the inputs to ensure they are valid (hash table and key).
Calculate the hash of the key using our hash function to determine the linked list where the pair may be stored.
If there is no linked list associated with the calculated hash, it means the key is not present in the hash table. We can return from the function at this point.
If a linked list is found at the calculated hash, we pass a pointer to the head pointer of the linked list to our RemoveNode function.
The RemoveNode function will traverse the linked list, searching for the node with a matching key. If found, it will remove the node from the linked list and update the head pointer if necessary.

//we get a pointer to a hash table, and a pointer to a string
bool Remove(HashTable* hashTable, char* key) {
    // if the pointers are NULL, or the string is empty, we consider that an error
    if (hashTable == NULL || key == NULL || strlen(key) == 0) {
        printf("error: bad values were provided:\n%p\n%s\n%ld\n", hashTable, key, strlen(key));
        return false;
    }
    // at this point we can compute the hash
    unsigned int position = _computeHash(key, hashTable->capacity);
    // if there is no linked list, we can return
    if (hashTable->collection[position] == NULL) return true;
    // if we find a linked list, we delegate the node removal
    bool success = RemoveNode(&hashTable->collection[position], key);
    // and output the result
    return success;
};

Testing a complete flow

Now we get to test a complete flow!
In it, we will try to:

create a hash table
store some key-value pairs
change their values
try to get a value for a non present key
remove a key and hen check it is not present in the hash table

void _testStoreGetAndRemove() {
    // we create some keys
    char* keys[] = { "key1","key2","key3","key4","key5","key6" };
    // we initialize a hash table
    HashTable* hashTable = CreateHashTable(5);
    int i;
    // we store all the keys
    for (i = 0; i < 6; i++) {
        bool success = Store(&hashTable, keys[i], keys[i]);
        // and check everything went ok
        assert(success == true);
    }
    // then we loop over all the keys and check they have a correct value
    for (i = 0; i < 6; i++) {
        char* value = Get(hashTable, keys[i]);
        assert(strcmp(value, keys[i]) == 0);
        free(value);
    }
    // we create a new expected string for all the values
    char* defaultValue = "default";
    // and change the values for all the keys
    for (i = 0; i < 6; i++) {
        bool success = Store(&hashTable, keys[i], defaultValue);
        assert(success == true);
    }
    // Then we get all the keys and assert their new values
    for (i = 0; i < 6; i++) {
        char* value = Get(hashTable, keys[i]);
        assert(strcmp(value, defaultValue) == 0);
        free(value);
    }
    // we try to get a value for a non present key
    assert(Get(hashTable, "missingKey") == NULL);
    // we remove one key
    bool success = Remove(hashTable, keys[1]);
    assert(success == true);
    // and assert there is no value for it now
    assert(Get(hashTable, keys[1]) == NULL);
    // and now we clean everything up
    for (i = 0; i < hashTable->capacity; i++) {
        Node* n = hashTable->collection[i];
        ClearList(&n);
    }
    free(hashTable->collection);
    free(hashTable);
}

Checking if parentheses are balanced in a string

Lautaro Jayat — Wed, 14 Jun 2023 19:45:35 +0000

Table of contents:

The strategy
The Implementation
Performing some tests
Link to the source

This is an interesting example of how a stack can be used to solve a real problem. If you have programming experience or familiarity with a programming language, you likely have an intuition about what balanced parentheses are. We say that a string has balanced parentheses when each opening parenthesis has a corresponding closing parenthesis in the right position. For example, the following strings are balanced:

(hey)(how)are(you?)

(((hey))) how are (you)?

((hey))(how)(are(you)?)

But, the following strings are unbalanced:

# it has the correct number of pairs but in bad order
)(hey) how are you(

# it has one closing parentheses with no opening counterpart
(hey) how are (you)) ?

# it is the lamest string of all
(((( hey how are you?

we might be interested in performing these kinds of checks to ensure that homologous syntactic rules are correct. For example, we may want to verify if a string has been closed correctly or if our Lisp program will work properly. These checks are essential for maintaining the integrity and correctness of our code and programs.

The strategy

The strategy we will employ is quite straightforward.
For each parenthesis encountered, we will perform the following steps:

If it is an opening parenthesis, we will push it onto the stack.
If it is a closing parenthesis, we will peek at the element on the top of the stack:

If the top element is an opening parenthesis, we will pop it, discarding both the popped element and the current element.
If the top element is a closing parenthesis, we will push the current element onto the stack.

In the end, we need to check if the stack is empty. If it is empty, it means that each parenthesis had its counterpart in the right place. However, if there are remaining elements in the stack, it implies that the string was not properly balanced.

To illustrate this example:

string = "((hey))"
stack = []

# we start checking character by character in the string
# the first one is "(" si we push it
Push(stack, "(") #=> stack contains ["("]

# then we encounter another opening parentheses so we push it
Push(stack, "(") #=> stack contains ["(", "("]

# then the next 3 elements are discarded as they
# are meaningless

# but the 4th one is ")"
# so it cancels the last element we added
Pop(stack,...)  #=> stack contains ["("]

# we repeat the operation and out stack is now empty
Pop(stack,...)  #=> stack contains ["("]

if (stack->length > 0){
    return unbalanced
}

return balanced

The implementation

For the implementation we will be using the same stack we implemented in chapter 01.
The only difference will be the type of data to be stored in the underlying array:

typedef struct {
// we use "int" to represent our characters
    int* collection;
    uint32_t capacity;
    uint32_t size;
} Stack;

Again, we will be using almost the same operations shown in the example of chapter 01:

// the signature of our functions
Stack* CreateNewStack(uint32_t capacity);
void DestroyStack(Stack** stackp);
bool Is_Empty(Stack* stack);
bool Push(Stack* stack, int item);
bool Pop(Stack* stack, int* poppedItem);
bool Peek(Stack* stack, int* peekedItem);

First, we will define certain constants to prevent code errors caused by mistyping characters. Subsequently, in the code, we will reference their values using the names assigned to these variables:

const int OPEN_BRACE = '(';
const int CLOSING_BRACE = ')';
const int END_OF_STRING = 0;

The actual operations we will perform are as follows:

Accept a pointer to a string.
Count the characters to determine the required space for the stack.

If the string is empty, we return early.
If not, we continue.

Create a new stack.
Loop over each character and:

If the character is an opening parentheses, store it in the stack.
If the character is a closing parentheses, check if the element at the top is an opening parentheses. If it is, pop the opening one and discard both. If it is not, push the closing one.

After checking all characters, exit the loop and assign the size to a variable.
Destroy the stack.
If the size is 0, return true; otherwise, return false.

The implementation can be seen in the following snippet:

// We receive the string
bool IsABalancedString(char* input) {
    int stringLength = 0;
    // we loop over the string until the end and count each iteration
    while (input[stringLength] != END_OF_STRING) {
        stringLength++;
    }

    // if the counter is 0, there was no character in the string
    if (stringLength == 0) {
        printf("empty string provided");
        return true;
    }

    // We create the stack
    Stack* stack = CreateNewStack(stringLength);
    int i = 0;

    // And loop over all the string
    for (i = 0; i < stringLength; i++) {

        // we store the open parentheses
        if (input[i] == OPEN_BRACE) {
            Push(stack, input[i]);
            continue;
        }

        if (input[i] == CLOSING_BRACE) {
            int item = 0;
            // we check what the last element was
            Peek(stack, &item);

            if (item == OPEN_BRACE) {
                // pop if we can cancel it out
                Pop(stack, &item);
                continue;
            }
            // push it if we cant cancel them out
            Push(stack, input[i]);
        }
    }

    // we store the size because we are going to free the stack
    int finalSize = stack->size;
    DestroyStack(&stack);

    // If all elements were cancelled, it was balanced
    if (finalSize == 0) {
        printf("the string was balanced\n");
        return true;
    }

    // at this point, we know it wasn't balanced at all
    printf("the string was unbalanced\n");
    return false;
}

Performing some tests

As we have tested the stack in chapter 01, we can now focus on testing this checker function.

The simplest way is to come up with some correct strings, and other bad strings.
And then just assert whether they are balanced or not:

int main() {
    char* balancedStrings[5];
    balancedStrings[1] = "hey";
    balancedStrings[2] = "(hey there)";
    balancedStrings[3] = "(hey (there) pal)";
    balancedStrings[4] = "(((dude (((how are (((you?)))))))))";
    balancedStrings[5] = "()()()()()()()()()()()";

    int i;
    for (i = 0; i < 5; i++) {
        bool result = IsABalancedString(balancedStrings[i]);
        assert(result == true);
    }

    char* unbalancedStrings[5];
    unbalancedStrings[0] = "(hey";
    unbalancedStrings[1] = "(hey )there)";
    unbalancedStrings[2] = "(hey (there) pal))";
    unbalancedStrings[3] = "(((dude (((how are ()((you?)))))))))";
    unbalancedStrings[4] = "()()()()()()()()()())()";

    for (i = 0; i < 5; i++) {
        bool result = IsABalancedString(unbalancedStrings[i]);
        assert(result == false);
    }
    return 0;
}

Implementing a dynamic array

Lautaro Jayat — Wed, 14 Jun 2023 14:58:08 +0000

Dynamic arrays are similar to static arrays in the sense that they allow easy reading, insertion, or modification of elements by referring to them using their index within the array. However, unlike static arrays, dynamic arrays implement a mechanism to dynamically increase or decrease their memory as needed.

Table of contents

Basic Operations
1. Creating a dynamic array
2. Destroying a dynamic array
3. Pushing to a dynamic array
4. Popping an element from a dynamic array
Testing the happy path
Source code of this example

Basic operations

To implement a basic dynamic array, we need to maintain information about the maximum reserved space, the number of elements already stored, and a resizing strategy for the underlying data structure.

A struct that includes a pointer to an array, along with two integers representing the capacity and number of elements, is sufficient to start. The following snippet shows the aforementioned structure and the function signatures for the essential operations we need to support.

typedef struct
{
    int32_t* collection;
    u_int32_t capacity;
    u_int32_t size;
} D_array;

D_array* CreateDynamicArray(uint32_t capacity);

bool DestroyDynamicArray(D_array**);

bool Push(D_array* array, int32_t val);

bool Pop(D_array* array, int32_t* returnValue);

bool IsEmpty(D_array* array);

In this example, we will focus on supporting the Push and Pop. operations for the dynamic array. Directly accessing data using array->collection[i].
will be allowed, although it is considered unsafe. It's worth noting that more advanced implementations of dynamic arrays may include additional functions such as getSlice, filter, map, getElement. However, these functionalities are beyond the scope of this article.

Creating a dynamic array

To create a dynamic array, we will utilize a constructor function that encapsulates the underlying implementation, ensuring safety and consistency across instantiations.

The constructor function will receive the size of the array as a parameter. It will attempt to create an array and check if the creation is successful. Subsequently, the appropriate size will be allocated for the remaining struct components. Finally, we will set up the struct to ensure it is ready for use. The implementation is as follows:

// The capacity will be given by the caller context
D_array* CreateDynamicArray(uint32_t capacity) {

    // We will start trying to allocate thearray first
    int32_t* collection = (int32_t*)calloc(capacity, sizeof(int32_t));

    // If the step above couldn't be done, we will not procceed
    if (collection == NULL) {
        return NULL;
    }

    // If the array was allocated, we continue with the struct
    D_array* array = (D_array*)malloc(sizeof(D_array));

    // Same as the array, we check if everything went ok
    if (array == NULL) {
        // in case it didn't we free the collection and return
        free(collection);
        return NULL;
    }

    // If everything went ok, we continue assigning each field
    array->collection = collection;
    array->size = 0;
    array->capacity = capacity;
    return array;
}

Destroying a dynamic array

In order to destroy the array, we need to free both the underlying collection and the struct. To maintain a clean and tidy process, we will begin by freeing the space that was reserved for the underlying collection. If we were to free the struct first, there is a possibility of losing the reference to the array and causing a memory leak.

In the following snippet, you can find a possible implementation:

// We pass a pointer to a pointer to the dynamic array
bool DestroyDynamicArray(D_array** array) {
    // as we want to free the original pointer, we dereference it
    D_array* arr = *array;

    // if it was null, we can return
    if (arr == NULL) {
        return false;
    }

    // if the underlying collection exists we just free it
    if (arr->collection != NULL) {
        free(arr->collection);
    }

    // finally we free the array
    free(arr);
    return true;
}

Since arguments are passed by value, we don't accept just a pointer to a dynamic array; instead, we accept a pointer to a pointer to that array. If we were to only receive a pointer to a dynamic array, the operation free(arr) would not affect the original pointer itself. By accepting a pointer to a pointer, we ensure that we can modify the original pointer and free the memory correctly.

Pushing to a dynamic array

To push to a dynamic array, we first confirm that the struct and the collection exist. Next, we check if a resize is necessary, perform the resize if needed, and finally update the array and counters accordingly. Here's an example implementation:

// we receive the array and the value we want to store
bool Push(D_array* array, int32_t val) {
    // we check if the struct and the underlying collecition exists
    if (array == NULL || array->collection == NULL) {
        return false;
    }
    // Check if we need to resize
    if (_needsToResize(array)) {
        // resize if needed
        bool ok = _resize(array);
        if (!ok) return false;
    }
    // At this point we can update the underlying collection
    array->collection[array->size] = val;
    // and update the counter
    array->size++;
    return true;
}

The function that determines if a resize is needed for our array is quite simple. It checks if the dynamic array is not a null pointer and compares the size to the capacity. In our case, we want to resize the array when we reach half of the capacity.

// we pass the pointer to the struct
bool _needsToResize(D_array* array) {
    // we check if it is a null pointer
    if (array == NULL) {
        return false;
    }
    // check if the double of the size + 1 is still less than the capacity
    return  (array->size + 1) * 2 < array->capacity;
}

If we need to resize the underlying array, we can utilize the realloc function, which takes two arguments: the original memory space and the desired final memory size. With realloc, a new memory space will be reserved, the old values will be copied into the new section, and the original space will be freed.

To determine the growth factor, we will simply double the space each time we reach half of the capacity.

// We accept a pointer to the array
bool _resize(D_array* array) {
    // we check everything is in place
    if (array == NULL || array->collection == NULL) {
        return false;
    }

    // We calculate the new capacity
    uint32_t newCapacity = 2 * array->capacity;

    // and then reasign which our collection is
    array->collection = (int32_t*)realloc(array->collection, sizeof(int32_t) * newCapacity);

    // after this, we check everything went ok
    if (array->collection == NULL) {
        return false;
    }

    // and we update the new capacity
    array->capacity = newCapacity;

    return true;
}

Popping an element from a dynamic array

To pop an element from our dynamic array, we will accept a pointer to the array and a pointer to an integer. If the operation is successful, we will update the value that the integer pointer points to. Then, we will update the size field and return a boolean indicating the success of the operation.


// we accept a pointer to an int
bool Pop(D_array* array, int32_t* returnValue) {
    // check if we can continue
    if (array == NULL || array->collection == NULL) {
        return true;
    }
    // we decrease out poinert
    array->size--;
    // And we assign the value so the caller context can make use of it
    *returnValue = array->collection[array->size];;
    return true;
}

Testing the happy path

To test the happy path we will do the following:

Create a dynamic array and assert it was correctly created.
Push elements until we reach the limit where one more element will trigger the resize operation
Assert the capacity didn't changed
Push one more element and assert the capacity changed
Pop each element and check if it is what we expected
Check if the array is empty
destroy the array and check everything went ok

// We receive the initial capacity we desire
void _testHappyPath(uint32_t capacity) {
    // we create a dynamic array
    D_array* array = CreateDynamicArray(capacity);
    // and we check the correct memory alocation
    assert(array != NULL)

    int32_t i = 0;
    // we start looping until we reach the half of the array
    while ((array->size + 1) * 2 < array->capacity) {
        Push(array, i);
        i++;
    }
    // We asert that the capacity didn't changed
    assert(array->capacity == capacity);

    // We push another element
    Push(array, i);

    // Check if the array grew as we wanted
    assert(array->capacity == capacity * 2);
    int32_t* returnValue = (int32_t*)malloc(sizeof(int32_t));

    // Now we pop each element
    while (!IsEmpty(array)) {
        Pop(array, returnValue);
        // and we assert is the element we want
        assert(*returnValue == (int32_t)array->size);
    }
    assert(IsEmpty(array) == true);
    _cleanup(array);
}

Implementing a linked list

Lautaro Jayat — Mon, 12 Jun 2023 13:46:10 +0000

Table of contents

The linked list as an abstract data structure
Implementing the data structure
1. Create a linked list
2. Insert a value to the head of the linked list
3. Remove a value from an arbitrary position
4. Destroy a linked list
5. Insert a value in an arbitrary position
6. Print all the elements in the linked list
Performing some tests
Source Code

The linked list as an abstract data structure

A linked list is a linear collection of data where the order of the elements is not determined by their physical location in memory, unlike the array used in the previous implementation of the stack.

This data structure consists of units known as "nodes," which, in its simplest form, are structures containing the stored data and a reference to the next node in the list.

Since we rely on references to connect each node in a chain, adding or removing an element from the list is a relatively straightforward operation. It involves simply changing the reference of a node to point to the appropriate node.

This approach eliminates the need to determine the overall memory size of the collection in advance, dynamically resize the collection, or perform bound checks and reordering operations.

However, these benefits come at a cost. As the elements are not stored contiguously in memory, one cannot rely on sizes and offsets to directly access a specific node. Instead, to access a node, one must traverse the entire list up to the desired element. Consequently, accessing a particular element may require iterating through the list for the same number of iterations as the index of the element being searched.

Implementing the data structure

In this example, we will implement a linked list where each node will have a reference to the next node. We will not support multiple references from one node to another.

The following operations will be supported:

Create a linked list
Insert a value to the head of the linked list
Remove a value from an arbitrary position
Destroy a linked list
Insert a value in an arbitrary position
Print all the elements in the linked list

After these examples, performing other operations such as replacing a value in a node or counting the number of elements should be straightforward.

Let's begin by writing the header file that will act as our interface.

#pragma once
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

typedef struct Node_T
{
    int32_t data;
    struct Node_T* next;
} Node;

Node* CreateNewNode();

void InsertToHead(Node** head, int32_t number);

int InsertAtNthPosition(Node** head, int32_t number, int32_t position);

int RemoveFromNthPosition(Node** head, int32_t position);

void PrintAll(Node* head);

As we can see, each node in the linked list is simply a struct that holds an integer and a pointer to the next element.

The collection is not stored in one contiguous place like an array. This means we need to be cautious when creating a node or rearranging the linked list to avoid any memory leaks. Losing track of a node may result in being unable to free that memory from the heap.

Create a linked list

In this example, to create a node, we don't need to pass any arguments to our "constructor" function. The chosen semantics imply that the data stored in the first node will be set in the caller's context. The constructor will only handle error checking and memory manipulation.

The implementation can be seen in the following snippet:

Node* CreateNewNode() {
    // we just call malloc and ask for a space in memory
    // of the size of our struct
    return (Node*)malloc(sizeof(Node));
}

To make use of the constructor we can make something like:

// we create the node
Node* newNode = CreateNewNode();

// we check if the pointer is null
if (newNode == NULL){
    return 1
}
// we dereference the poiner and assign data
newNode->data = 69;
// as this is the only node, we assign NULL as the next node
newNode->next = NULL;

Insert a value to the head of the linked list

To insert something at the begining of the linked list we need to perform this sequence of operations:

create a node
assign some data to it
make it point to the node that is currently at the head

To ilustrate this idea:

// we ask for the value to store as data
// and a reference to the head (which is a pointer)
// this is important because in our function
// we will replace the head
void InsertToHead(Node** pointerToHead, int32_t number){

    //We create a new node
    Node* newNode = CreateNewNode();

    // we asign new data
    newNode->data = number;

    // we make it point to the old head
    newNode->next = *pointerToHead;

    // we replace the head with our new node
    *pointerToHead = newNode;
};

It might be tricky to understand this double pointer at first. But Node** pointerToHead is needed so the calling context can do the following operation:

// the head is a pointer already
Node* head = CreateNewNode()
head->data = 69
head->next = NULL
// we pass a pointer to the head so the function can update the actual head
InsertToHead(&head)

If we were to pass just the pointer to the head instead of the pointer to a pointer to the first node, the InsertToHead function would receive a copy of the pointer. It would change where the copy points to, but the modification would be discarded when the function's stack frame is destroyed, without affecting the caller's context.

To overcome this, we can pass a reference to the pointer we want to modify as an argument to the function.

Remove a value from an arbitrary position

To remove from an arbitrary position we will handle two cases:

The case where we are removing the first node
The case where we are removing any other node

There are other smarter ways to handle this operation, but this may be usefull to ilustrate the internals of this data structure.

The implementation can be seen in the following snippet, please find guidance in the comments:

// We will be returining 0 or 1 to signal if the operation succeeded
// Again, we accept an integer for the position and a reference to the head node
int RemoveFromNthPosition(Node** head, int32_t position) {

    // if for some reason they give us a null pointer, we return with an error
    if (*head == NULL) {
        return 1;
    }

    // We initialize a variable to store the pointer we want to free
    Node* toDelete;

    // if we are freeing at the begining
    if (position == 0) {
        // we access the actual head pointer
        toDelete = *head;

        // we asign re-asign which node is now the head
        *head = (*head)->next;
        // we free the node we had stored
        free(toDelete);

        // then we return
        return 0;
    }

    // if we want to remove other node rather the first one
    // we will say that the head is our "previous" node
    Node* prevNode = *head;

    // we initialize a counter
    int32_t i;

    // and we start looping up to the position we want to remove
    for (i = 1; i < position ; i++) {

        // if the position is greater than the actual number of nodes
        // we will end up with the last node, wich points to NULL
        if (prevNode->next == NULL) {
            // and we return with an error
            return 1;
        }

        // the current node is now the previous of the next iteration
        prevNode = prevNode->next;
    }

    // At this point prevNode is the actual previous node
    // the next one will be our target
    // we assign our target to our "toDelete" variabe
    toDelete = prevNode->next;

    // and we make close the chain
    prevNode->next = toDelete->next;

    // then we clean our target node
    free(toDelete);
    return 0;
}

If we are removing a node other than the first one, the process is relatively straightforward. We locate the target node, remove it from the linked list, and then link the previous node to the next node.

However, removing the first node requires some attention. We need to change the actual head of the linked list, and this process depends on the strategy or semantics we have chosen for our implementation.

Destroy a linked list

To destroy a linked list, we need to traverse the entire collection and free the memory allocated for each node.

We accomplish this by jumping from one node to the next, repeating the freeing operation until we reach the end of the linked list. This process is demonstrated in our _cleanUp implementation within the test suites, which can be found in the source code of this example.

// test.c
void _cleanUp(Node** head) {
    // we initialize a variable to keep track of the result
    int shouldStop = 0;

    // we keep looping until we get a signal to stop
    while (shouldStop == 0) {
        // we use our previous implementation to remove
        // the head node
        shouldStop = RemoveFromNthPosition(head, 0);
    }
}

Insert a value in an arbitrary position

Inserting a new node is quite similar to removing a node from an arbitrary position and may even be easier. The steps involved are as follows:

If the caller function passes a null pointer as the head pointer, we need to return.
If we are inserting at the head, we can use our previous implementation.
If we are inserting a node at any other position, we traverse from one node to another until we find the node at position n - 1, where n is the desired position for insertion. Then, we make the new node point to the node the previous one was pointing to. Finally, we make the previous node point to the new node.

The procedure is illustrated in the following snippet:

int InsertAtNthPosition(Node** head, int32_t number, uint32_t position) {
    // We check if the linked list is empty
    if (head == NULL) {
        return 1;
    }
    // we check if we are adding to the head
    if (position == 0) {
        // we use the previous implementation
        InsertToHead(head, number);
        return 0;
    }

    // we start a counter
    int32_t i;
    // we write down which is the first node
    Node* prevNode = *head;

    // we start jumping from one node to the other
    for (i = 1; i < position; i++) {
        prevNode = prevNode->next;
    }
    // at this point, prevNode is the node before our target position

    // we create the node as we want
    Node* newNode = CreateNewNode();
    newNode->data = number;
    // we make it point to the old "next"
    newNode->next = prevNode->next;

    // we make the "prevNode" point to the new node
    prevNode->next = newNode;
    return 0;
}

Print all the elements in the linked list

The simplest approach to print all the elements in a linked list is to iterate over it and call printf for each element. If desired, we can add characters to indicate the start and end of the list, as well as a separator between elements. For example, to print something like [ 1 2 3 69 ], we can use the following function:

void PrintAll(Node* head) {
    // we reasign that pointer to avoid messing with the arguments
    Node* currentNode = head;

    // We first print a string to inform what the user is seeing
    printf("The current values of the linked list are: [ ");

    // we loop over the whole list until the end of if
    while (currentNode != NULL) {
        // we print the data of each node and a space
        printf("%d ", currentNode->data);

        // we update which should be the current node for the next iteration
        currentNode = currentNode->next;
    };
    // And we close the string
    printf("]\n");
}

Please note that this is a naive approach, and we are not optimizing anything. We could calculate the buffer size of our string in advance, populate the buffer with the elements, and then make a single printf call, reducing the number of system calls. Such optimizations may be covered in a separate chapter.

Performing some tests

The whole test suite can be found this file.
Here, we will demonstrate a test to verify the correct order of elements in the list when inserting at the head.

The testing function is as follow


// We will accept a number indicating how many nodes we want
int _testLinkedListOrdering(int32_t desiredNodeNumber) {
    // to avoid messing with the arguments we will reasign
    int32_t nodeNumbers = desiredNodeNumber;
    // and initialize a counter
    int32_t i;
    // we will initialize a new linked list
    Node* head;
    head = NULL;
    for (i = 0; i < nodeNumbers; i++) {
        // and then we will insert to head
        // the value of each node will be in decreasing order
        InsertToHead(&head, nodeNumbers - 1 - i);
    }
    // then we will loop over the list and check if the the value is correct
    Node* currentNode = head;
    for (i = 0; i < nodeNumbers; i++) {
        assert(currentNode->data == i);
        // we set which is the currentNode for the next iteration
        currentNode = currentNode->next;
    }
    // We cleanup using the function shown in the "Destroy the linked list" subtitle
    _cleanUp(&head);
    // and we assert the head is now NULL
    assert(head == NULL);
}

Setting up a lab to play with the C language

Lautaro Jayat — Thu, 08 Jun 2023 14:07:17 +0000

This is just a prelude of a work in progress that will be posted here. Please follow the link if you want to see the whole project and play with some examples.

Table of contents

GCC
Installing Docker
Creating a container that has all what we need
How to use this containers

GCC

There are numerous ways to start developing and compiling C. On one hand, you could consider using an IDE like Visual Studio or Visual Studio Code, along with some helpful extensions. On the other hand, you can opt for the reliable combination of GCC and other free and open-source tools, which perform exceptionally well. However, it's worth noting that this latter approach may not be compatible with all operating systems due to potential missing tools or libraries. Nevertheless, there are simple and effective solutions available for this issue

GCC, short for GNU Compiler Collection, is a versatile tool for compiling various programming languages. According to the official website:

The GNU Compiler Collection includes front ends for C, C++, Objective-C, Fortran, Ada, Go, and D, as well as libraries for these languages (libstdc++,...).

The easiest way to get started with GCC in a controlled environment, without risking any conflicts or having to install multiple components that may raise concerns, is to utilize Docker and virtualize the entire setup.

Installing Docker

We typically use the term "Docker" to refer to a tool or a collection of tools that enable us to build, run, and manage containers.

Likewise, we commonly use the term "containers" to denote an implementation of virtualization technology that allows us to isolate environments and processes, simulating separate machines with their own operating systems, programs, configurations, and more.

For installing Docker, the best guides can be found on their official website.

I would recommend installing only the CLI tools, although Docker Desktop is also a suitable option. Here are some useful resources to assist you with the installation process:

Creating a container that has all what we need

Using Docker might be tricky at the beginning, but if you've seen The Matrix, you'll grasp it quite quickly.

The main task here is to create this virtual world. It should look like a Debian machine, having all the tooling we need.

For this, lets firts create the so called "Dockerfile" to instruct docker what do we want.

# ./Dockerfile

# 1. start from debian
FROM debian:latest

# 2. update the package manager
RUN apt update -y

# 3. install this package that contains GCC
#    and everything we would need for this project
RUN apt install build-essential -y

This content can be placed inside a file named "Docker".

Next, we should open a terminal in the same folder where we have previously placed our Dockerfile. This will allow us to build the container image based on the instructions provided above:

# hey docker, please build the Dockerfile in this folder and tag it with "clab"
docker build -t clab .

Now we have a Docker image that we can refer to using the tag "clab," which represents our lab for conducting experiments with the C language.

To run this container, simply type:

docker run -v $(pwd)/:/app -it clab

The -it flag will instruct Docker to attach an interactive terminal to the container, enabling us to continue working inside the container. This allows us to operate within the container context, akin to being inside the matrix.

The -v $(pwd)/:/app portion instructs Docker to map the current working directory of your host (the real world) to a folder inside the container located at /app.

You will observe a change in the terminal's color scheme, indicating that you are now logged in as root.

To verify, let's start experimenting with GCC by requesting its version.

gcc --version
# gcc (Debian 10.2.1-6) 10.2.1 20210110
# Copyright (C) 2020 Free Software Foundation, Inc.
# This is free software; see the source for copying conditions.  There is NO
# warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

How to use this container

I suggest creating a folder for each example and starting the Docker container from there.

Then, navigate to the /app folder inside the container by using the command cd /app.

Keep in mind that you can use your preferred text editor to create or modify files in your project folder on your host machine. All changes made in this "real world" context will be visible and reflected inside the container.

This way, you can write code as usual, while performing compilations within the isolated environment provided by Docker.

Implementing a stack using a simple array

Lautaro Jayat — Thu, 08 Jun 2023 13:57:21 +0000

Table of contents

The stack as an abstract data structure
Now yes, on implementation details
1. Create a stack
2. Destroy a stack
3. Check if the stack is full
4. Put an element at the top of the stack
5. Check if the stack is empty
6. remove the element at the top of the stack
7. Peek the element at the top of the stack but without removing it
Creating some tests
Source Code

The stack as an abstract data structure

Conceptually, the stack acts as a container that preserves the order of elements in the same sequence they were added.

When removing an element, one can only retrieve the last element placed on the stack, commonly referred to as the element at the top.

The fundamental operations are commonly known as Push, which adds an element to the stack, and Pop, which retrieves the last element.

The order in which elements are placed into or removed from the stack is commonly known as "last in, first out" or LIFO.

To illustrate the idea:

# 1. the stack is empty
[]

# 1. I want to put X in the stack

[ X ]

# 2. I want to put Y in the stack

[ X , Y ]

# 3. I want to put Z in the stack

[ X , Y , Z ]

# 4. Now I want to remove an element

[ X , Y ] # --> and you got Z because it was the latest element placed in there.

In addition to the fundamental operations, there are additional operations that can be performed on a stack, commonly referred to as non-essential operations.

One such operation is called Peek, which allows us to observe the last element added to the stack without removing it. As this behavior can be achieved by temporarily removing the element and subsequently adding it back to the top of the stack, it is not considered essential.

Similarly, other examples of non essential operations includes checking whether the stack is empty or full. These checks could serve to prevent executing operations that migth cause system crashes in a real implementation.

Now yes, on implementation details

In this example, we will implement the stack using a simple array.

Note that resizing our underlying array at runtime will be beyond the scope of the current example.

For our implementation, we will support the following operations:

Create a stack
Destroy the stack
Put an element at the top of the stack
Remove the element at the top of the stack
Peek the element at the top of the stack but without removing it
Check if the stack is full
Check if the stack is empty

To start, let's create a headers file that will serve as our interface:

// stack.h
#pragma once
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>


typedef struct {
    int32_t* collection;
    uint32_t capacity;
    uint32_t size;
} Stack;

Stack* CreateNewStack(uint32_t capacity);
void DestroyStack(Stack** stackp);
bool Is_Empty(Stack* stack);
bool Is_Full(Stack* stack);
bool Push(Stack* stack, int32_t item);
bool Pop(Stack* stack, int32_t* poppedItem);

At the top, we include all the necessary libraries that we will need.

Then we are defining the struct that will act as our stack. Inside this struct, we have three components:

collection, which is a pointer to a place in memory that will be allocated for the underlying array.
capacity, which will store a unsigned integer that indicates the maximum number of elements that our array can hold.
size, which will keep track of the actual number of elements that the stack contains.

Finally, at the bottom, we present the function signatures for the operations that will enable us to interact with the stack.

1. Create a stack

By encapsulating the stack creation process within a dedicated function, we can isolate the implementation details associated with instantiating the stack.

This practice offers several benefits. Firstly, it aids in debugging as the entire process remains consistent and centralized in one place. Additionally, it allows us to avoid the manual allocation of memory, casting pointers, and the repetitive setup required for each stack instance. This reduces cognitive load and minimizes the potential for introducing errors in multiple locations.

Let's explore the implementation approach with some guidance provided in the comments:

// We will receive an integer representing the number of elements we want to store
// The function will output a pointer where our Stack was placed in the heap
Stack* CreateNewStack(uint32_t capacity) {

    // We use the "malloc" function as our allocator and we ask
    // to reserve a place in memory with the size of a Stack
    Stack* stack = malloc(sizeof(Stack));

    // We check if the stack is a null pointer
    // this can occur when malloc fails to allocate
    if (stack == NULL) {
        // I this is the case, we shouldn't continue with the process
        return stack;
    }

    // Now we are asking for a place in memory to store the size of our
    // array type, but multiplied by our capacity
    // and we store the pointer in our "collection" field
    stack->collection = malloc(sizeof(int32_t) * capacity);

    // Again, if we fail we shouldn't continue
    if (stack->collection == NULL) {
        // so we free the previously allocated memory for the stack
        free(stack);
        // And we return just a null pointer that the caller should check
        return NULL;
    }

    // If everything turned out OK,
    // we keep track of the capacity of our stack
    stack->capacity = capacity;

    // And, because there is nothing stored yet
    // we set the size as 0
    stack->size = 0;

    // lastly, we return this pointer to the stack
    return stack;
}

The crucial aspect here is to verify whether the memory allocation was successful. This is what will might change the flow of our program and enables us to properly clean up any necessary resources.

2. Destroy the stack

Destroying the stack involves freeing all the memory that was allocated for the stack. Depending on the chosen semantics, it may involve returning a null pointer to allow the caller to handle the memory replacement or delegating that responsibility to our function.

In this example, we will adopt the latter approach.

Lets see the code. Again, please find some guidance in the comments:

// we will receive a pointer to the actual pointer that holds the address
// of the already allocated stack
void DestroyStack(Stack** stackp) {

    // to ease some things, we will de-reference the pointer
    // so we can start working with the stack.
    Stack* stack = *stackp;

    // If it happens that the caller sent us a reference
    // to a null pointer, we should return
    if (stack == NULL) {
        return;
    }

    // Now, we check if the pointer to the underlying array
    // actually points to something
    if (stack->collection != NULL) {
        // If so, we free that memory
        free(stack->collection);
    }
    // Then we free the memory reserved for the struct
    free(stack);

    // and lastly, we say
    // "that reference to a struct is now a reference to a null pointer"
    *stackp = NULL;
}

It is worth noting that we are freeing the memory in the reverse order of its allocation:

first the underlying array
then the stack

If we were to free the memory in the same order it was allocated, we would end up freeing the stack and losing the reference to the location where the array was stored.

3. Check if the stack is full

Before adding an element to the array, it is advisable to check if we have sufficient space available. Neglecting this step could potentially corrupt memory that might be used by other parts of the program, which would lead to undesirable consequences.

The code for this check is trivial and it assumes that we are maintaining a record of the number of elements in the stack. The operation simply verifies if the size is equal to the capacity and returns a boolean value to the caller's context.

bool Is_Full(Stack* stack) {
    return stack->capacity == stack->size;
}

4. Put an element at the top of the stack

Putting an element at the top of the stack is a straightforward process.
In our implementation example, we assume that the position of the last element is at index size - 1. The remaining steps can be achieved with the following code snippet:

// We receive a pointer to the stack we will be working with
// and also the element we want to store.
// The return value will be a boolean indicating if
// the operation succeeded or not
bool Push(Stack* stack, int32_t item) {
    // We check if there is something stored there
    if (stack == NULL) return false;
    // we check if there is some place to store the element
    if (Is_Full(stack)) return false;

    // then we assign the item on top the last element
    stack->collection[stack->size] = item;
    // And we update the current size of the stack
    stack->size += 1;

    // And we tell the caller "everything went ok :)"
    return true;
}

5. Check if the stack is empty

Similar to the Push operation, it is good practice to check if there is an element to pop before performing the operation.

The implementation is quite simple; we only need to check if the size is zero.

bool Is_Empty(Stack* stack) {
    return  stack->size == 0;
}

6. Remove the element at the top of the stack

Popping an element is quite similar to pushing one. In our implementation, we have made two decisions:

First, we will not be returning the popped element itself; instead, we will return a boolean value indicating whether the operation was successful or not. The value of the popped element will be stored in an pointer to an integer that the caller passes to us as the second argument of our function.

Second, we will not be "cleaning" or setting a "zero value" in the position of the popped element. Although we could do it, in our case, since we used malloc to reserve space for the underlying array, none of the original elements are zeros. However, if we were storing sensitive data, it would be advisable to perform such cleaning.

// They give us the pointer to the stack and a place
// to reference the returned value
// we send back a boolean indicating if everything went ok
bool Pop(Stack* stack, int32_t* poppedItem) {
    // We check if the pointer is valid
    if (stack == NULL) return false;
    // we check if there is something to return
    if (Is_Empty(stack)) return false;
    // we decrease the size
    stack->size -= 1;
    // and we assign the value to the place in memory
    // that pointer is pointing to
    *poppedItem = stack->collection[stack->size];
    // and we are ready to go
    return true;
}

Remember: we are decreasing the size of the array before getting the item because, at this point, the size is one number bigger than the position of the last element.

7. Peek the element at the top of the stack but without removing it

Peeking is essentially the same as popping, with the difference that it does not decrease the size of the stack or clean any elements.

In other words, peeking allows us to observe the topmost element of the stack without removing it or modifying the stack in any way.

// All the same operations as in the example above
bool Peek(Stack* stack, int32_t* peekedItem) {
    if (stack == NULL) return false;
    if (Is_Empty(stack)) return false;
    // But we subtract one in place
    *peekedItem = stack->collection[stack->size - 1];
    return true;
}

Creating some tests

To test the happy path we will do the following:

we create a stack
we will try to Push all elements we can until it is at it's maximum capacity and check if, indeed, it full.
then we will pop all the elements while checking if the operation succeeded, and if the elements are in the right order.
we check if the stack is empty
we clean everything

void _testHappyPath(uint32_t capacity) {
    Stack* stack = CreateNewStack(capacity);

    // we could also assert(stack != NULL) here

    int32_t i;
    // we loop and assign the index to each position
    for (i = 0; i < capacity; i++) {
        Push(stack, i);
    }
    // we check if it is full
    assert(Is_Full(stack) == true);

    int32_t j;
    bool result;

    // we loop again while popping each element
    for (i = 0; i < capacity; i++) {
        result = Pop(stack, &j);

        // we check if the value is the the expected one
        // using capacity - 1 - i, because we are going from
        // the biggest element to the lowest element
        assert(j == capacity - 1 - i);

        // and we also check if each operation succeeded
        assert(result == true);
    }
    // finally, we verify if the stack is empty
    assert(Is_Empty(stack) == true);

    // then se clean everything up
    _cleanup(stack);
}

Our cleanup function also can give us some hints on whether some auxiliary operations are OK

void _cleanup(Stack* stack) {
    // we pass a reference to our stack pointer
    DestroyStack(&stack);

    // by the semantics we are using, we now can
    // check if the original pointer is pointing to NULL
    assert(stack == NULL);
}

For more testing examples and the full source code, please follow this link

Listening to OS signals in Golang

Lautaro Jayat — Thu, 27 May 2021 22:07:13 +0000

No server, application, script or binary stuff is something isolated from the rest of the computer. Being aware of what is happening behind the scenes is useful, because lot of things can happen.

For this reason, Golang offers a simple way to manage this, without any black magic.

Lets suppose we have just a simple main function that starts a simple http server.

package main

func main{
    StartServer()
}

Maybe this works fine, but this is not aware of anything about the underlying OS. This means that, if something signals the main process to stop, this will just stop or crash without the possibility of gracefully shut down the server and it’s child gorutines.

Imagine now that we could pass a a context with cancellation this function as an argument like StartServer(ctx).
Now imagine that we could start a new routine that is aware of any signal of our interest and then cancel this context.

Lets check out the following piece of code and then we will unravel it.

package main

import (
    "context"
    "log"
    "os"
    "os/signal"
)

func listenAndCancel(c chan os.Signal, cancel context.CancelFunc) {
    oscall := <-c
    log.Printf("system call:%+v", oscall)
    cancel()
}

func main(){

    // Making a channel and ctx to comunicate signInt to server
    c := make(chan os.Signal, 1)
    signal.Notify(c, os.Interrupt)
    ctx, cancel := context.WithCancel(context.Background())

    // Spawn a gorutine to cancel root context if signInt occurs
    go listenAndCancel(c, cancel)

    // Starting server with previous context
    StartServer(ctx)

}

First, try to focus on the main function. We start creating a channel with the built in make function. This give us a channel that accepts os.Signals and only can store one of them at a time.

Those signals are a type that Golgang provides in the os package and they represents operative system signals for the runtime.

Then, we have a super useful function: signal.Notify. Intuitively, we can thing that this function is waiting for any os.Interrupt and then pass it through the channel.

If we wanted to look more deep, we can check the documentation:

“Notify causes package signal to relay incoming signals to c. If no signals are provided, all incoming signals will be relayed to c. Otherwise, just the provided signals will.”

So now, we have automated the way in which the runtime listents for interrupt signals, and then pass them to the channel.

Then, we create a context with cancellation. The context will go to StartServer as an argument, where it will be used to give context for any further request or gorutine; and the cancel part will go to the listenAndCancel function used as a gorutine.

What does this last function? Easy: it receives the channel and the cancel, then blocks until an interrupt signal comes out the channel. Then it cancel the context, making the server aware of this OS signaling.

Auth reverse proxy in Golang

Lautaro Jayat — Tue, 11 May 2021 23:20:39 +0000

Let’s suppose that we have a monolith that needs to do lot of things, like process data, read and write to the DB, spawn an HTTP server for an API and also authenticate it’s incoming request.

There are scenarios where it would be nice to decouple some responsibilities. This could be because we have a team that can put all it’s effort into maintain that part of the system, or maybe there is a need to migrate the back end logic from one framework to another, etc.

In this case, this article proposes an example on how to make an HTTP server that stands in front the main server, authorize the incoming requests and then it forwards them to the back end or returns a response with a 401 status code.

Making our target server

In our target we have only two main blogs: our main function and a welcome handler that will be used for all of the incoming request. The first one just makes a new Mux for an HTTP server and then starts listening in port 8080.
The handler is also simple:

First, it checks if the incoming request comes from certain port (like a white list). If not, it gives a 401 response and return.

Then, if we have have an exported environment variable named SECRET, it checks if the incoming request has any header with that secret, and if it matches the one we have exported. If not, it respond with another 401 status code and return.

If everything is OK, it adds 3 headers and returns a body that says “hi from target server”.

Making our proxy server

We want something simple that could be extensible, so we will be having a main function that will instantiate our reverse proxy, the main server and it’s handlers:

In our reverse proxy we call a function that will return a function with the following signature: func (*http.Request), this will be our director function.

The Director in the httputil.ReverseProxy struct is just a function that can access the request and make modifications like adding headers, change the URL, host, cookies depending on our forwarding logic.

For example, in director/director.go we have this:

Basically, we have a function that access two environment variables and then returns a function that modifies the request to froward to the new host.

In our case, the HOST variable will be the host of our target server. This means that any incoming request served by the reverse proxy will be mapped to the target server.

For example, in our case http://localhost:8081/hi will be passed to http://localhost:8080/hi.

Now lets see what is happening in our router package.

In line 25 of our main.go file we had r := rt.NewRouter(&rp). So there is a function that receives a pointer to the reverse proxy and then it returns a router from the github.com/julienschmidt/httprouter package.

If we go to our router/router.go file we have the following:

There we instantiate a router and assign some handlers for each desired method.

At first view it appears that we check for an authorization header in the most common HTTP verbs and we just forwards the OPTIONS verb.

Although it appears simple, this design allow us to plug and play different auth strategies depending on the structure and path of the URL, making it extensible and easy to maintain.
Now is time for the strategies.

Our strategies must be of the type httprouter.Handler because is what our router uses. This is just a function with the following signature:

func (http.ResponseWriter, *http.Request, httprouter.Params)

In our example, the FwdOptionsReq function is the most simple case.

As we can see, each strategy is a a function that receives the reverse proxy and then returns a function that can access the response writer, the request, the params, etc. In this case, the returned handler just serve the HTTP request using the reverse proxy and then pass the response from the target to the client.

Is interesting to notice that we are using high order functions but we could be using other things like structs that had a pointer to the reverse proxy and a methods which represents the handlers. This is just one implementation.

Let’s see now how the strategy/checkAuthHeader.go file looks like:

In this case, we first load two environment variables so we can use it in the handler. Then, in the returned function, we check if there is any secret. If there is one, we enrich the headers with it.

Then we get the “Auth” header and compare it with the value we got from the “AUTH” environment variable.

If both do not match, we use the provided ResponseWriter and make an early response. Only if everything is OK we continue and forward the request to the target server.

A tiny demo

In order to follow this demo you can get the code cloning this github repo:

LautaroJayat / go_auth_proxy_example

Golang Auth proxy example

This is just an example on how to use the httputil.ReverseProxy type provided in the golang standard library.

Open a terminal in the root folder and run go run target/main.go. This will start the target server. It will only respond to request from localhost:8081
Open another terminal in the root folder and run the following commands:

# first export some env variables
export SCHEMA="http"
export HOST="localhost:8080"
export Auth="123456"

# then run proxy server
run go proxy/main.go

This will start our auth proxy in localhost:8081 and will redirect traffic to http://localhost:8080 only if there is an header like "Auth: 123456"

Open another terminal and start making some requests
Have fun

View on GitHub

First let’s run the target server opening a terminal and running:

go run target/main.go
# outputs: Starting target server

Then we need to open another terminal and let’s export some variables:

export SCHEME="http"
export HOST="localhost:8080"
export AUTH="123456"

And then let’s just start the reverse proxy running the following command:

go run proxy/main.go
# outputs:
#
# SCHEME http
# HOST localhost:8080
# Auth 123456
# Starting proxy server
# Routes Registered

Now let’s try to CURL our target server:

curl -X GET -i  http://localhost:8081
# outputs: 
# 
# HTTP/1.1 403 Forbidden
# Date: Mon, 10 May 2021 17:16:57 GMT
# Content-Length: 12
# Content-Type: text/plain; charset=utf-8
#
# Auth needed

But, if we provide that header:

curl -X GET -H "Auth: 123456" -i  http://localhost:8081
# outputs: 
# 
# HTTP/1.1 200 OK
# Content-Length: 23
# Content-Type: text/plain; charset=utf-8
# Date: Mon, 10 May 2021 17:17:56 GMT
# X-Host: localhost:8082
# X-Method: GET
# X-Url: /
#
# hi from target server!

Thanks for reading. This was just a little example on how to use the provided reverse proxy provided the standard Go library.

If you have some improvements or corrections, please feel free to make a comment (or a pull request to the repo).

If you liked this post, please share it :)

The code for this example can be found here: https://github.com/LautaroJayat/go_auth_proxy_example

Javascript Interview Question: Select only the numbers in the array (with strange cases).

Lautaro Jayat — Tue, 11 May 2021 12:24:51 +0000

In this article we will try to solve something that looks like a simple problem but can scale and become very strange deal. The problem is the following one:

let array = [1, 2, 3, '4', undefined, 'a', [], null];

If you have an array make a function that returns other array wich contains only numbers. The array is the following one:

But now they change the question and says: “Oh! but could you please also include numbers that were written as strings, like '2' or '404'?

First we could tryisNaN() , because is a higher function built-in Javascript that can tell us if something is not a number. It returns true or false, and also evaluates strings of numbers as numbers.

So we try the following:

Ouch! We forgot that they are asking for an array of Numbers!
But… there is something more.

Curious, an empty array and null are both numbers.
It happens that Javascript is a Dynamic Type programing language so, different from C, the language has it’s own parser and protocols to know if a variable is a number, a string, and so on.

It seems that this behavior was intended that way so back in the 1995 the future developers of the newborn internet could applay their coding patterns (from a lot of different programing languages) into Javascript. But of course, no one could ever know that the community will push the language to the extreme.

If you want to know more about this weird behaivors, I recomend this excelent repository called “What the f*ck Javascript?”.

denysdovhan / wtfjs

🤪 A list of funny and tricky JavaScript examples

What the f*ck JavaScript?

A list of funny and tricky JavaScript examples

JavaScript is a great language. It has a simple syntax, large ecosystem and, what is most important, a great community.

At the same time, we all know that JavaScript is quite a funny language with tricky parts. Some of them can quickly turn our everyday job into hell, and some of them can make us laugh out loud.

The original idea for WTFJS belongs to Brian Leroux. This list is highly inspired by his talk “WTFJS” at dotJS 2012:

Node Packaged Manuscript

You can install this handbook using npm. Just run:

$ npm install -g wtfjs

You should be able to run wtfjs at the command line now. This will open the manual in your selected $PAGER. Otherwise, you may continue reading on here.

The source is available here: https://github.com/denysdovhan/wtfjs

Translations

Currently, there are…

View on GitHub

So now that we know a little more about this, lets find a way to solve our original problem.

If you remember, the problem was that our function can’t distinguish between a number, null and an empty array.

One solution could be changin isNaN() to something that only works well with strings and numbers, like the function parseInt(string|number, base), another higher-order function tries to convert everithing into an integer.

So, if we arrange our code, it will look like this:

Although it would be a very strange scenario, this code will also work fine if we have the following arrays:

let array1 = [1, 1.2, "3", 0, "0x" undefined, []]
let array2 = ["undefined, null, NaN, "0f"]
LET ARRAY3 = [number.POSITIVE_INFINITY, true, false]

But, now that we are talking about wierd cases, lets make this code fail.

The first case I could think is one in wich, for one reason, someone puts stufs like ["20x", "5f", "1f"]. For this cases, the code will output NaN for each element.

To solve this we first need to make sure that they are not asking us to parse numbers in hexadecimal (base 16), because in that case 20F is 527 base 10, and we would need to do a lot more of stuff that is out of the scope of this article.
Once we know that they are just looking for every number in our decimal world, we need change the expression that we are testing for the condition:
Instead of if (parseInt(e)){...} we need something like:

if (parseInt(e) && parseInt(e) !== NaN) {...}

Bonus tip:

Because beeing a Dynamic Typed language, Javascript has a lot of weird stuffs. One that could mess with this approach to the problem is the following:

let a = [true + true];
console.log(a[0].toString()) // Will Output '0';
console.log(isNaN(a[0]))     // Will Output False
console.log(true + true);    // Will Output 2
console.log(null + null);    // Will Output 0
console.log(typeof (a[0]));  // Will Output 'number'

So in this case, if we had this array [false, true + true, false] our function will output [0].

It seems that there is no way in Javascript to distinguish expressions that are additions of booleans and numbers. But, to encounter with a problem in a Javascript job that requires to select only numbers in an array that also has operations with booleans and positive infinities seems a little unreal.

One could ask: how you guys end up with such weird looking way of storing all this heteroclite data?
Given this problem, the first meassure could be try to avoid repeating this problem by fixing the functions so we only have sets of data that we could easily manage… maybe this is why they invented Typescript.