With the blockchain project about to fork from libeom, it is appropriate to merge the current status of the working branch into main. Before the merge, some documentation and cleanup needs to be done.

I may be wrong, but I think that in your BinarySearchingTree.c file in binary_search_tree_destructor you should use pointer to the tree as an argument instead of actual tree. It causes the thing, that you are not actually destroying actual tree. Besides that you make a copy of your tree in that function and destroys it, but not the actual tree you wanted. I may be wrong because of pointer copies in that function, but to make sure you are destroying the tree correctly and to make it cleaner, I think that's would be better.

And thank you for the lib and for videos, sorry if I'm wrong!

Terminal Applications

Applications such as Python, MongoDB, and PostgreSQL come with an interactive terminal interface that allows real-time processing of commands one after another. Since these shell interfaces are so common and useful, it would be useful to add a generic one to the library.

Generic Terminal

The result would be a terminal function that takes argc and argv from main and passes them off to a user-defined interpreter. Since the command syntax and resulting actions are unknown to the generic function, the purpose of the function is to switch between two activation conditions:

1. Launching with no arguments:

> $ ./application

This should open an interactive shell where the user may enter repeated commands to pass to the interpreter.

2. Launching with arguments:

> $ ./application arg1 arg2

This should simply pass the two arguments to the interpreter and close.

Data Pipes

While designing a terminal application, it is important to remember that commands may come from data pipes rather than direct user input. A robust implementation of an interactive terminal should be capable of receiving input through a pipe rather than user input.

Goals

We are building the base functionality to read, create, share, and collect blocks within a peer-to-peer network. With this application, it will be easy to install client and server based applications that extend its functionality, allowing you to use the blockchain in any way you like.

Single or Multiple Applications?

On a given node, how dependent is either the client or server section on the other? If the client utilizes the server to query local storage, then their usage is heavily integrated and every instance of the application will require both client and server functionality; however, these two functionalities could also be designed as stand-alone applications, allowing users to install blockchain-client or blockchain-server depending on their needs. Either way, we may want to allow users to configure the allocation of resources to client and server functionalities.

Discussion

How should we implement the raw materials present in the library into a final product? Should we create separate or integrated client and server applications?

This issue was brought to my attention by @camel-cdr

Hashes and Raw Bytes

When transferring blocks over the network, the first test a node will run over a foreign block to validate its integrity will be the network-standard hashing algorithm. Should the resulting hash satisfy the network-prescribed proof-of-work difficulty, we can begin treating the object as a block; however, there may be discrepancies in how a given machine stores the desired data structures. As a result, the raw bytes that one node sends will not fit into the same structure on the recipient node architecture due to a concept called padding. While the hash generated from those raw bytes would satisfy the difficulty requirement, the data would not cast correctly into the expected data type.

Padding

The CPU does not read data by the bit, nor by the byte, but by the word. The size of a word is dependent on the architecture, but generally a 32 bit CPU will have a 4 byte word while a 64 bit CPU will have an 8 byte word. When the compiler defines the memory layout of a struct, it does so depending on the architecture's word size. The following struct, for example, would require a total of 8 bytes of memory on a 32 bit machine, despite being only 6 bytes of data:

struct example 
{
    char a;
    char b;
    int c;
};

The problem is that the int data type requires four bytes of memory, and it will save CPU cycles to access that member in a single word. The structure is then padded such that the field begins where the CPU may access it in a single cycle. So instead of storing the struct like this:

Word:    |_          _            _            _           |_          _            _            _           |

Data:     char     char          int----------------------------------------------- empty-----------------------

The structure is padded so that the int falls at the beginning of a word:

Word:    |_          _            _            _           |_          _            _            _           |

Data:     char     char          empty-----------------------int-----------------------------

Data Integrity

While this is a more efficient layout in terms of CPU cycles at a small cost in memory, it makes maintaining the integrity of data when handled by multiple nodes difficult. Fortunately, we may override this behavior to designate that all blocks on the network are to be created, stored, and transferred in an unpadded schema:

struct BlockHeaders
{
    unsigned char previous_hash[64];
    unsigned long nonce;
    unsigned char fingerprint[64];
    unsigned char timestamp[20];
    unsigned long size;
} __attribute__((packed));

The packed attribute designates this struct to be created without padding, which will allow the casting of raw bytes sent across a network between nodes with incompatible architectures.

So I've done some reading through the source code of the linked list implementation, and I'm laying them out some of my thoughts here.

One does not simply index a linked list

It's important to notice, that the complexity of random access to a linked list is O(n), that means that 1 if you need to do a lot of random access you shouldn't be using a linked list and that you should always prefer iteration to indexing. Using iterate_ll to implement sort_ll and search_ll automatically results in very slow code.

search_ll

Ok, let's get this out of the way search_ll should be called bsearch_ll or binarysearch_ll, the name search doesn't tell the user that the linked list needs to be sorted to search for elements. Note that using binary search on a linked isn't a good idea in the first place, as you need to traverse almost the entire list anyways (if iterate_ll wasn't used, otherwise it does literally quadratic work). It's only useful if you need to reduce the calls to compare, which is something you might want to do, but this should definitely be done explicitly and not be the default search.

Also, why are you calling the compare function twice instead of storing the result? I'd also return int instead of short, but that's just nitpicking now.

sort_ll

sort_ll also has the problem of using iterate_ll, so I transformed the bubble sort algorithm to work without it:

void sort_ll(struct LinkedList *linked_list, int (*compare)(void *a, void *b))
{
    for (struct Node *i = linked_list->head; i; i = i->next)
    {
        for (struct Node *j = i->next; j; j = j->next)
        {
            if (compare(i->data, j->data) > 0)
            {
                // Swap them.
                void *temporary = j->data;
                j->data = i->data;
                i->data = temporary;
            }
        }
    }
}

Note that I also changed the comparison from == 0 to > 0, this allows you to e.g. implement the compare function for integers using a - b, which is commonly done.

Now the complexity has been reduced from O(n^3) to O(n^2). Bubble sort itself isn't the best sorting algorithm, and I'd suggest actually using something like merge sort.

Getting rid of the indexes

Generally when working with linked lists you should pass around node pointers instead of indexes. To illustrate that let's say you'd like to remove a node. To delete a node you firstly need to know where the node currently is. The current implementation requires you to iterate over each element of the list with indexes, so you automatically have a complexity of O(n) and then when you've found the correct element iterate over the entire list again (at least this time in O(n)), to find the element at the index. An alternative solution, which is preferable when working with liked lists, is to traverse the linked list using pointers for (Node *i = list; i; i = i->next) and then pass the current node pointer to the delete function.

On ownership and pointers

Another thing I've noticed is that you're linked list owns pointers, as in allocates and frees them. This isn't automatically wrong, but I'd say that it isn't a good design decision. For one, how would you only use a shallow copy, so inserting e.g.

struct Str {
         size_t len;
         char *str;
};

wouldn't copy str and now you've got two references to str and you'd somehow need to decide who frees str (I'm assuming that str is heap allocated). I suggest that instead of doing the allocation inside insert_ll the user would call it with a pointer allocated from the user, this would also get rid of the problem of constructing a node with data of size zero. Having a node with a null pointer should be totally allowed.

How I would do it

This isn't for everyone's taste, but I like to use a Node as a base class for the elements of the list. This allows you to basically do whatever you want to, and you don't have an extra indirection between the node and the data, which is more cache friendly.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

struct Node {
        struct Node *next;
        struct Node *previous;
};

struct IntNode {
        struct Node node;
        int i;
};

static struct Node *
sort_ll_merge(struct Node *a, struct Node *b, int (*cmp)(void *a, void *b));

/* mergesort */
struct Node *
sort_ll(struct Node *head, int (*cmp)(void *a, void *b))
{
	struct Node *a, *b;

	if (!head || !head->next)
		return head;

	{
		struct Node *fast, *slow;
		slow = head;
		fast = head->next;

		/* Advance 'fast' two nodes, and advance 'slow' one node */
		while (fast != NULL) {
			fast = fast->next;
			if (fast != NULL) {
				slow = slow->next;
				fast = fast->next;
			}
		}

		/* 'slow' is before the midpoint in the list, so split it in
		 * two at that point. */
		a = head;
		b = slow->next;
		slow->next = NULL;
	}

	a = sort_ll(a, cmp);
	b = sort_ll(b, cmp);
	return sort_ll_merge(a, b, cmp);
}

struct Node *
sort_ll_merge(struct Node *a, struct Node *b, int (*cmp)(void *a, void *b))
{
	struct Node* res = NULL;

	/* Base cases */
	if (a == NULL)
		return (b);
	else if (b == NULL)
		return (a);

	/* Pick either a or b, and recur */
	if (cmp(a, b) > 0) {
		res = a;
		res->next = sort_ll_merge(a->next, b, cmp);
	} else {
		res = b;
		res->next = sort_ll_merge(a, b->next, cmp);
	}
	return res;
}


int
cmp_intnode(void* a, void* b)
{
	struct IntNode *ia = a, *ib = b;
	return ia->i - ib->i;
}

int
main(void)
{
	/* just on way to construct an linked list,
	 * you could use malloc instead. */
	struct IntNode nodes[30] = {0};
	for (int i = 0; i < 29; ++i) {
		nodes[i].node.next = &nodes[i+1];
		nodes[i+1].node.previous = &nodes[i];
		nodes[i].i = rand();
	}

	struct IntNode *newhead = sort_ll(nodes, cmp_intnode);

	for (struct IntNode *i = newhead; i; i = i->node.next) {
		printf("%d\n", i->i);
	}
}