Skip to content

Reference Sheet

Jump to bottom
Braedon edited this page Jan 13, 2019 · 7 revisions

Reference Sheet

This is made for you to refer to.

TOC

Collections

Arrays

/* Create a new array with a given name and size */
Array array_new(char *name, size_t size);

/* Free the array */
void array_free(Array array);

/* Get the array node at the given index */
ArrayNode array_at(Array array, size_t index);

/*
   Create a new array node for use in the other functions 
   Could use NEW_NODE(array, data) instead! 
*/
struct _array_data_t array_new_node(Data data, TypeTag type);

/*
   Resize the array to the new size keeping the old elements.
*/
void array_resize(Array array, size_t new_size);

/*
   Set a specific index to a node value.
*/
void array_set(Array array, size_t index, struct _array_data_t node);

/*
   Get the array length.
*/
size_t array_length(Array array);

Linked Lists

Note: each node has a next pointer and the LL itself has a head and a tail.

/*
    Create a new list with a given name and a default type.
*/
LL ll_new(char *name);

/*
    Clears and frees list.
*/
void ll_free(LL list);

/*
    Frees the given node.
*/
void ll_free_node(LL_Node n);

/*
    Creates a new node with the data given.
    Could use NEW_NODE(ll, data)
*/
LL_Node ll_new_node(Data data, TypeTag type);

/*
    Prints out the node data.
*/
void ll_default_print_data(LL_Node n);

/*
    Free all nodes in collection.
*/
void ll_clear(LL list);

/*
    Inserts the given node after the LL_Node 'at'.
*/
void ll_insert_after(LL list, LL_Node node, LL_Node at);

/*
    Inserts the given node before the LL_Node 'at'.
*/
void ll_insert_before(LL list, LL_Node node, LL_Node at);

/*
    Removes the given node from the list, returning the node removed.
*/
LL_Node ll_remove_node(LL list, LL_Node node);

/*
    Returns true if the list is empty.
*/
bool ll_is_empty(LL list);

/*
    List can be null in some cases.  Will find the previous node to the given one.
*/
LL_Node ll_find_prev(LL list, LL_Node at);

/*
    List can be null in some cases.  Will find the next node to the given one.
*/
LL_Node ll_find_next(LL_Node n);

/*
    Returns the length of the list.
*/
size_t ll_length(LL list);

/*
    Pushes node to top of list.
*/
void ll_push(LL list, LL_Node n);

/*
    Pops top node from list.
*/
LL_Node ll_pop(LL list);

/*
    Adds node to end of list.
*/
void ll_append(LL list, LL_Node n);

Doubly Linked Lists

Note: each node has a next and a prev pointer and the LL itself has a head and a tail.

/*
    Create a new list with a given name and a default type.
*/
DLL dll_new(char *name);

/*
    Clears and frees list.
*/
void dll_free(DLL list);

/*
    Frees the given node.
*/
void dll_free_node(DLL_Node n);

/*
    Creates a new node with the data given.
    Could use NEW_NODE(dll, data)
*/
DLL_Node dll_new_node(Data data, TypeTag type);

/*
    Prints out the node data.
*/
void dll_default_print_data(DLL_Node n);

/*
    Free all nodes in collection.
*/
void dll_clear(DLL list);

/*
    Inserts the given node after the DLL_Node 'at'.
*/
void dll_insert_after(DLL list, DLL_Node node, DLL_Node at);

/*
    Inserts the given node before the DLL_Node 'at'.
*/
void dll_insert_before(DLL list, DLL_Node node, DLL_Node at);

/*
    Removes the given node from the list, returning the node removed.
*/
DLL_Node dll_remove_node(DLL list, DLL_Node node);

/*
    Returns true if the list is empty.
*/
bool dll_is_empty(DLL list);

/*
    List can be null in some cases.  Will find the previous node to the given one.
*/
DLL_Node dll_find_prev(DLL_Node at);

/*
    List can be null in some cases.  Will find the next node to the given one.
*/
DLL_Node dll_find_next(DLL_Node n);

/*
    Returns length of list.
*/
size_t dll_length(DLL list);

/*
    Pushes node to top of list.
*/
void dll_push(DLL list, DLL_Node n);

/*
    Pops top node from list.
*/
DLL_Node dll_pop(DLL list);

/*
    Adds node to end of list.
*/
void dll_append(DLL list, DLL_Node n);

Lists

/*
    Create a new list with the given name.
    By default uses `poly_grow_function` with factor 2.
*/
List list_new(char *name);

/*
    Frees the list.
*/
void list_free(List list);

/*
    Grows the list linearly.
    i.e. increases by factor each time.
    if factor == 0 then just is always min_new_len i.e. no growth.
    for factor == 2 => 2 -> 4 -> 6 -> 8 -> 10...
*/
size_t linear_grow_function(size_t old_len, size_t min_new_len, double factor);

/*
    Grows the list polynomially.
    i.e. doubles each time if factor == 2.
    2 -> 4 -> 8...
*/
size_t poly_grow_function(size_t old_len, size_t min_new_len, double factor);

/*
    y = x^factor such that min_new_len <= y(old_len).
    Will effectively find the smallest multiple such that it'll fit the min_new_len.

    2 -> 4 -> 16... for a factor of 2
    2 -> 8 -> 512... for a factor of 3
*/
size_t exponential_grow_function(size_t old_len, size_t min_new_len, double factor);

/*
    Get the node at the index given.
*/
ListNode list_at(List list, size_t index);

/*
    Creates a new list node.
    Used for the other functions
*/
struct _list_data_t list_new_node(Data data, TypeTag type);

/*
    Makes sure the list can handle len amount of data.
*/
void list_reserve(List list, size_t len);

/*
    Clears list.  Will release memory if release_memory is true.
*/
void list_clear(List list, bool release_memory);

/*
    Pushes node to back of list, growing if needed.
*/
void list_push_back(List list, struct _list_data_t node);

/*
    Inserts node after index given.
*/
void list_insert_after(List list, size_t index, struct _list_data_t node);

/*
    Inserts node before index given.
*/
void list_insert_before(List list, size_t index, struct _list_data_t node);

/*
    Removes node at index.
*/
void list_remove(List list, size_t index);

/*
    Returns true if list is empty.
*/
bool list_is_empty(List list);

/*
    Returns length of list.
*/
size_t list_length(List list);

/*
    Returns capacity of list.
*/
size_t list_capacity(List list);

Stacks

Just a wrapper around LL.

/* Create a new stack with a given name */
Stack stack_new(char *name);

/* Free the stack */
void stack_free(Stack stack);

/* Frees the given node */
void stack_free_node(StackNode n);

/* Returns how many items are currently on the stack */
size_t stack_length(Stack stack);

/* Returns true if there are no items on the stack */
bool stack_is_empty(Stack stack);

/* Free all nodes in queue. */
void stack_clear(Stack stack);

/* 
   Create a new node in the stack 
   Could use NEW_NODE(stack, data);
*/
StackNode stack_new_node(Data data, TypeTag type);

/* Pushes a new node onto the top of the stack */
void stack_push(Stack stack, StackNode node);

/* Pops a node form the top of the stack */
StackNode stack_pop(Stack stack);

Queues

Just a wrapper around LL.

/* Create a new queue with a given name */
Queue queue_new(char *name);

/* Frees the queue and all the memory its allocated */
void queue_free(Queue queue);

/* Frees the given node */
void queue_free_node(QueueNode n);

/* Free all nodes in queue. */
void queue_clear(Queue queue);

/* Returns how many items are currently in queue */
size_t queue_length(Queue queue);

/* Returns true if there are no items in queue */
bool queue_is_empty(Queue queue);

/*
   Create a new node
   Could use NEW_NODE(queue, data)
*/
QueueNode queue_new_node(Data data, TypeTag type);

/*
    Adds a object to the end of the queue
*/
void queue_enqueue(Queue queue, QueueNode node);

/*
    Takes an object from the front of the queue.
*/
QueueNode queue_dequeue(Queue queue);

IO

  • update(int number_of_collections, ... collections) i.e. update(2, list1, list2) prints out the lists and then does a wait (either waits for LLV_SLEEP_TIME in ms or waits till enter if LLV_SLEEP_TIME == 0)
  • fmt_update(char *fmt, ...) similar to printf and scanf in some regards it reads a sequence of fmt specifiers from fmt and ignores everything that isn't preceded by a % (use %s if you want to embed strings in the format) so fmt_update("Hello World %l", list) is invalid and rather you should write fmt_update("%s %l", "Hello World", list)
    • %l a list/collection
    • %s a string
    • %n a singular node (prints out as if it was part of a list)
    • %i input from the user (followed by the input type i.e. %ii is an int) has to be at the end of the format specifiers
      • %ii int
      • %il long
      • %is char*
      • %ic char
      • %if double
      • Note: call like fmt_update("%s %l %il %is", "Hey", list, &long_int, &buf)
  • attach_ptr(void *node, char *ptr) i.e. attach_ptr(&node, "my node") to attach a visual representation of the pointer
    • The attached string works best when it is short (i.e. 3 characters)
    • Make sure to pass by ref
    • Call deattach_ptr(void *node, char *ptr) to free up the data associated with the visual node
    • SET_PTR(node, value) and UNSET_PTR(node) can be used for a one time set
  • print_out_single_box(void *n, fn_print_node printer, fn_sizeof_node sizeof_n, int height) to print out a single node.
  • print_out_single_box_using_defaults(void *n, Collection c) does above but uses the defaults from the collection (and uses LLV_PRINT_HEIGHT for height)

Variables

In our test matrix we have a series of bash sources that edit environmental variables (to edit things like terminal width/height, unicode/ascii, clearing and so on) you can use them to like $ export LLV_PRINT_HEIGHT=5

  • LLV_PRINT_HEIGHT (default 3) how vertically high each node is
  • LLV_PTR_HEIGHT (default 2) nodes can display pointers this refers to how many spots below a ndoe a pointer can be held in.
  • LLV_SLEEP_TIME (default 0) the time between each 'animation' frame if 0 it will require you to press enter to go to the next frame.
  • LLV_DISABLE_UNICODE (default 0) disables unicode (overrides force unicode)
  • LLV_FORCE_UNICODE (default 0) on systems where we can't detect unicode support still force unicode (i.e. Mac's notoriously have unicode issues with some versions like High Sierra so you may need this to be on).
  • LLV_CLEAR_ON_UPDATE (default 1) on each animation frame update clear the screen
  • LLV_INCLUDE_PTRS_ON_SINGLE_BOX (default 0) when printing out a single node by itself (with no associated list) include any pointers associated with it?
  • LLV_DEFAULT_TERM_WIDTH (default 80) the default terminal width (effects tests/gdb)
  • LLV_DEFAULT_TERM_HEIGHT (default 80) the default terminal height (effects tests/gdb)
  • LLV_TESTING (default 0) enable it before running tests
Clone this wiki locally