Linked-List-x86-64-ASM ·

linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence

In contrary to other available implementations... This is written in assembly with its interface exposed to C

An example

#include <stdio.h>
#include <linked_list>


int compare(void * lhs, void * rhs) {
    int l = *(int *)lhs;
    int r = *(int *)rhs;
    if (l == r) {
        return 0;
    } else if (l > r) {
        return 1;
    } else {
        return -1;
    }
}

int main() {
  // allocate list with the comparison function
  linked_list * list = ll_alloc(&compare);

  // check if the list is empty
  ll_empty(list)

  // create an iterator
  iterator * it = lli_alloc();

  // point the iterator at the head of the list
  lli_begin(it, list);

  // declare an element
  int element = 10;

  // add the element to the list
  ll_insert(list, it, (void *)&element)

  // after insertion the iterator is no longer valid
  // set it once again at the beginning of the list
  lli_begin(it, list);

  // get the value from the iterator
  printf("%d\n", *(int *)lli_dereference(it));

  // delete the value
  ll_delete(list, it);

  // release after using the iterator;
  lli_release(it);

  // release the list
  ll_release(list);
}

Convention

All functions of the library start with ll prefix, as you might guess it stands for linked list. Each linked list has an associated compare function. It is used to search and check for existence of an element. Do not store objects of different types in the list

What is going on under the hood?

Linked list structure

Variable name	Size	Description
head	8 bytes	Pointer to the first node
last	8 bytes	Pointer to the last node
compare_function	8 bytes	Function used to compare elements against each other
size	8 bytes	Amount of elements in the list

Node structure

Variable name	Size	Description
value	8 bytes	Pointer to the stored value
next	8 bytes	Pointer to the next node

Iterator structure

Variable name	Size	Description
current	8 bytes	Pointer to the current node
previous	8 bytes	Pointer to the node before current

Supported platforms

Library works only on 64-bit systems

• macOS
• linux

Dependencies

• nasm (tested on 2.13.03)
• gtest (tested on 1.8.1)
• gcc with C++14 support (tested on 9.1.0)
• cmake (tested on 3.0.7)

Running tests

Build docker image firstly, execute the command from the root folder of repository

docker build -f ./tests/Dockerfile -t linked_list_tests .

Run the container

docker run --rm -it linked_list_tests all

Installing

Configure the project

cmake . -DCMAKE_BUILD_TYPE=Release

Then, install the library and its headers. It is going to be a static lib.

make install