/*
Compile:
make readme-ex04-added-functionality
*/
/** @file */
/** @brief Needed for Doxygen. */
#define _BSD_SOURCE /* snprintf() */
#include <string.h> /* memmove(), strerror() */
#include <stdio.h> /* printf() */
#include <stdlib.h> /* calloc() */
#include <errno.h> /* errno */
#define MAXSIZE 8192
/* Generic node struct, using a void pointer for data */
typedef struct node_t
{
struct node_t *next;
void *data;
} node_t;
/* Definitions for the struct example */
/* HTML header levels */
typedef enum header_level
{
h1 = 1,
h2,
h3,
h4,
h5,
h6
} header_level;
/* HTML header typedef */
typedef struct html_header
{
header_level level;
char *title;
} html_header;
/* Definition for the double array example */
typedef struct double_arr_t
{
double *arr_data;
size_t arr_len;
} double_arr_t;
/* Error codes */
typedef enum err_code
{
WARNING = -2,
ERROR = -1,
OK = 0
} err_code;
/* Matching codes */
typedef enum match_code
{
NO_MATCH = -1,
MATCH = 0,
MATCH_EVEN,
MATCH_ODD
} match_code;
/* Compare codes */
typedef enum cmp_code
{
CMP_NOT_EQUAL = -2,
CMP_LESS_THAN = -1,
CMP_EQUAL = 0,
CMP_GREATER_THAN = 1
} cmp_code;
/* Sort flags */
typedef enum sort_flag
{
SORT_ASC,
SORT_DESC
} sort_flag;
/* Typedef:s for function pointers */
typedef size_t (*add_func_t)(void **dest, const void *src);
typedef size_t (*copy_func_t)(void **dest, const void *src);
typedef size_t (*set_func_t)(void **dest, const void *src, const void *aux);
typedef void (*print_func_t)(void *data);
typedef match_code (*match_func_t)(const void *data1, const void *data2);
typedef cmp_code (*cmp_func_t)(void *data1, void *data2);
typedef err_code (*sort_func_t)(node_t **head, cmp_func_t cmp_func);
typedef match_code (*map_func_t)(void **dest, const void *src1, const void *src2);
typedef void (*del_func_t)(void *data);
/* Prototypes */
node_t *node_get(const node_t *head, int index);
void list_del(node_t **head, del_func_t del_func);
err_code node_append(node_t **head, void *data, add_func_t add_func);
node_t *list_split(node_t **head1, int index);
node_t *list_join(node_t **head1, node_t *head2);
/* -------------------------------------------------------------------------------- */
/* Data functions */
/* -------------------------------------------------------------------------------- */
/* Init data - basically allocate memory */
static void *data_init(size_t data_size)
{
void *data = calloc(1, data_size);
if (!data)
fprintf(stderr, "ERROR: data_init(): calloc() failed: %s\n", strerror(errno));
return data;
}
/* -------------------- */
/* Data - Set functions */
/* -------------------- */
/*
These functions are used both by node_add() and node_set()
The only difference between assigning new data and existing data is that memory has to be
allocated for node_add(), while this is not needed when called from node_set().
As these data functions do not know which one is the parent call, simply check if data has been allocated or not.
The 'int' type does not use the 'aux' argument, but it may be useful for other data types.
For example, when node data is an array, 'aux' may be used for accessing a given array index.
When node data is a string, 'aux' may be used as a string index.
*/
/* Set int */
size_t set_int(void **dest, const void *src, const void *aux)
{
size_t data_size = sizeof(int);
/* First check if this is append()/insert() (first-time assignment), or set() (modify existing data). */
if (*dest == NULL)
{
*dest = data_init(data_size);
if (*dest == NULL) return ERROR;
}
memmove(*dest, src, data_size);
(void)aux;
return OK;
}
/* Add int (alias) */
size_t add_int(void **dest, const void *src) {return set_int(dest, src, NULL);}
size_t add_int_size_only(void **dest, const void *src) {(void)dest; (void)src; return sizeof(int);}
/* Set int, just return size */
size_t set_int_size_only(void **dest, const void *src, const void *aux) {(void)dest; (void)src; (void)aux; return sizeof(int);}
/* Set "stringified" integer */
size_t set_string_from_int(void **dest, const void *src, const void *aux)
{
char buf[MAXSIZE] = {0};
size_t data_size = 0;
int i = *(int *)src;
snprintf(buf, MAXSIZE, "%d", i);
data_size = sizeof(char) * (strlen(buf) + 1);
*dest = data_init(data_size);
if (*dest == NULL) return ERROR;
memmove(*dest, buf, data_size);
(void)aux;
return OK;
}
size_t add_string_from_int(void **dest, const void *src) {return set_string_from_int(dest, src, NULL);}
/*
Init dest and copy src to dest.
Call this function only if dest is NULL.
*/
static err_code set_string(void **dest, const void *src)
{
/* dest is NULL, so just copy src to dest. */
size_t data_size = sizeof(char) * (strlen(src) + 1);
*dest = data_init(data_size);
if (*dest == NULL) return ERROR;
memmove(*dest, src, data_size);
return OK;
}
/*
Realloc dest and copy temp buffer.
Call this function only if dest is not NULL.
*/
static err_code set_string_realloc(void **dest, const char *buf)
{
size_t data_size = sizeof(char) * (strlen(buf) + 1);
if (data_size)
{
/* realloc() dest so the concatenated strings will fit. */
void *dest_realloced = realloc(*dest, data_size);
if (dest_realloced == NULL) return ERROR;
*dest = dest_realloced;
memmove(*dest, buf, data_size);
}
return OK;
}
/*
Concat two strings str1 + str2 into buf, realloc dest to fit buf, copy buf to dest.
Call this function only if dest is not NULL.
*/
static err_code set_string_concat(void **dest, const char *str1, const char *str2)
{
char buf[MAXSIZE] = {0};
snprintf(buf, MAXSIZE, "%s%s", str1, str2);
if (set_string_realloc(dest, buf) == ERROR) return ERROR;
return OK;
}
/*
Insert a string str2 at the given index of string str1, save result in buf, realloc dest to fit buf, copy buf to dest.
Example: if dest is 8 characters long and index is 5: dest = str1[0-4] + str2 + str1[5-7]
Call this function only if dest is not NULL.
*/
static err_code set_string_insert(void **dest, const char *str1, const char *str2, size_t index)
{
char buf[MAXSIZE] = {0};
size_t str1_len = strlen(str1);
if (index >= str1_len) return ERROR;
snprintf(buf, MAXSIZE, "%.*s%s%.*s", (int)index, str1, str2, (int)(str1_len-index), str1 + index);
if (set_string_realloc(dest, buf) == ERROR) return ERROR;
return OK;
}
/*
set_string_prepend():
Prepend a string to an existing string, i.e. dest = src + dest
*/
size_t set_string_prepend(void **dest, const void *src, const void *aux)
{
if (src == NULL) return OK;
else
{
if (*dest == NULL)
{
if (set_string(dest, src) == ERROR) return ERROR;
}
else
{
if (set_string_concat(dest, *(char **)src, (char *)*dest) == ERROR) return ERROR;
}
}
(void)aux;
return OK;
}
/*
set_string_append():
Append a string to an existing string, i.e. dest = dest + src
*/
size_t set_string_append(void **dest, const void *src, const void *aux)
{
if (src == NULL) return OK;
else
{
if (*dest == NULL)
{
if (set_string(dest, src) == ERROR) return ERROR;
}
else
{
if (set_string_concat(dest, (char *)*dest, *(char **)src) == ERROR) return ERROR;
}
}
(void)aux;
return OK;
}
/*
set_string_insert_at():
Insert a string at the given index of another string, i.e. if dest is 8 characters long and index is 5: dest = dest[0-4] + src + dest[5-7]
*/
size_t set_string_insert_at(void **dest, const void *src, const void *index)
{
if (src == NULL) return OK;
else
{
if (*dest == NULL)
{
if (set_string(dest, src) == ERROR) return ERROR;
}
else
{
if (set_string_insert(dest, (char *)*dest, *(char **)src, *(size_t *)index) == ERROR) return ERROR;
}
}
return OK;
}
/* Set struct */
size_t set_struct(void **dest, const void *src, const void *aux)
{
html_header *header = NULL;
char buf[MAXSIZE] = {0};
size_t data_size = 0;
int i = *(int *)src;
header_level level = h1 + i % h6;
char *title = NULL;
snprintf(buf, MAXSIZE, "This is title %d", i);
data_size = sizeof(char) * (strlen(buf) + 1);
title = data_init(data_size);
if (title == NULL) return ERROR;
memmove(title, buf, data_size);
header = data_init(sizeof(*header));
if (header == NULL)
{
free(title);
return ERROR;
}
header->level = level;
header->title = title;
*dest = header;
(void)aux;
return OK;
}
size_t add_struct(void **dest, const void *src) {return set_struct(dest, src, NULL);}
/* Set array of double */
size_t set_double_arr(void **dest, const void *src, const void *aux)
{
double_arr_t *arr = NULL;
double arr_data[] = {0, 97.0, 33.0, 31.0, 96.0, 30.0, 36.0, 92.0};
size_t arr_len = sizeof(arr_data)/sizeof(arr_data[0]);
int i = *(int *)src;
arr_data[0] = (double)i;
arr = data_init(sizeof(*arr));
if (arr == NULL) return ERROR;
arr->arr_data = data_init(sizeof(arr_data));
if (arr->arr_data == NULL)
{
free(arr);
return ERROR;
}
memmove(arr->arr_data, arr_data, sizeof(arr_data));
arr->arr_len = arr_len;
*dest = arr;
(void)aux;
return OK;
}
size_t add_double_arr(void **dest, const void *src) {return set_double_arr(dest, src, NULL);}
/* --------------------------- */
/* Data - Arithmetic functions */
/* --------------------------- */
/* Sum src + dest as integers, store result in dest */
/* Note: if this function is called on uninitialized node data (*dest is NULL), it works as dest = 0 */
size_t sum_int(void **dest, const void *src, const void *aux)
{
size_t data_size = sizeof(int);
/* First check if this is a first-time assignment, or if we are modifying existing data. */
if (*dest == NULL)
{
*dest = data_init(data_size);
if (*dest == NULL) return ERROR;
/* *dest wasn't initialized, so just copy src to dest */
memmove(*dest, src, data_size);
}
else
{
int sum = *(int *)*dest + *(int *)src;
memmove(*dest, &sum, data_size);
}
(void)aux;
return OK;
}
/* ---------------------- */
/* Data - Match functions */
/* ---------------------- */
/*
These functions are used both by node_get(), node_set() and node_del()
A 'match' function must return 0 for a matching criteria, otherwise non-zero.
*/
/* Match int */
/* Dummy function, returning MATCH for non-NULL node values in the range outside 6-8 */
match_code match_int_6_8(const void *data1, const void *data2)
{
if ((!data1) || (!data2))
{
return NO_MATCH;
}
else
{
int i = *(int *)data1;
(void)data2;
return ((i >= 6) && (i <= 8)) ? NO_MATCH : MATCH;
}
}
/* A more generic match function for integers: Match if > (greater than) */
match_code match_int_gt(const void *data1, const void *data2)
{
/* Return MATCH if data2 > data1 */
return ((!data1) || (*(int *)data1 <= (*(int *)data2))) ? NO_MATCH : MATCH;
}
/* Match integer if odd or even, depending on 'match_flag' */
match_code match_int_odd_or_even(const void *data, const void *match_flag)
{
if ((data == NULL) || (match_flag == NULL)) return NO_MATCH;
else
{
int rem = (*(int *)match_flag == MATCH_ODD ? 1 : 2);
/* Return MATCH if data % 2 = 0 | 1 */
return (*(int *)data % 2 == rem) ? MATCH : NO_MATCH;
}
}
/* -------------------- */
/* Data - Map functions */
/* -------------------- */
/*
These functions are used by list_map().
The resulting list may include some or all of the original list nodes, with the same or different values.
The return value is the same for a 'match' function, where MATCH means that the current node will be included in the resulting list.
*/
match_code map_int_sum(void **dest, const void *src1, const void *src2)
{
if ((dest == NULL) || (src1 == NULL) || (src2 == NULL)) return NO_MATCH;
else
{
int sum = *(int *)src1 + *(int *)src2;
size_t data_size = sizeof(int);
*dest = data_init(data_size);
if (*dest == NULL) return NO_MATCH;
memmove(*dest, &sum, data_size);
}
return MATCH;
}
/* ------------------------ */
/* Data - Compare functions */
/* ------------------------ */
/*
These functions are used for comparing two values.
One example of a similar function could be strcmp(3), which returns
CMP_LESS_THAN = -1,
CMP_EQUAL = 0,
CMP_GREATER_THAN = 1
These return values are used by functions such as node_sort(), which needs to distinguish between
equal, less-than, and greater-than values.
Other functions, such as list_del_dup(), only needs to distinguish between equal and non-equal values:
CMP_NOT_EQUAL = -2,
CMP_EQUAL = 0,
*/
/* Compare int */
cmp_code cmp_int(void *data1, void *data2)
{
/* Dummy function, returning MATCH for non-NULL node values in the range outside 6-8 */
if ((data1 == NULL) || (data2 == NULL)) return CMP_NOT_EQUAL;
else
{
int i1 = *(int *)data1, i2 = *(int *)data2;
return (i1 == i2) ? CMP_EQUAL : ((i1 > i2) ? CMP_GREATER_THAN : CMP_LESS_THAN);
}
}
/* --------------------- */
/* Data - Copy functions */
/* --------------------- */
/*
These functions are used by "result" functions, where nodes (and thus data) are copied.
As these data functions do not "know" the parent call, simply check if data has been allocated or not.
*/
/* Copy int (alias for set_int) */
size_t copy_int(void **dest, const void *src) {return set_int(dest, src, NULL);}
/* ---------------------- */
/* Data - Print functions */
/* ---------------------- */
/* Print int */
void print_int(void *data) {if (data) {printf("data=%d\n", *(int *)data);}}
/* Print string */
void print_string(void *data) {if (data) {printf("data='%s'\n", (char *)data);}}
/* Print struct */
void print_struct(void *data)
{
if (data)
{
printf("data->level=%d, \t", ((html_header *)data)->level);
printf("data->title='%s'\n", ((html_header *)data)->title);
}
}
/* Print array of double */
void print_double_arr(void *data)
{
if (data)
{
int i = 0;
printf("data={");
for (i = 0; i < (int)((double_arr_t *)data)->arr_len; ++i)
{
if (i) printf(", ");
printf("%.1f", (double)((double_arr_t *)data)->arr_data[i]);
}
printf("}\n");
}
}
/* ----------------------- */
/* Data - Delete functions */
/* ----------------------- */
/* Delete functions are not needed for simple types like int and char * */
/* typedef void (*del_func_t)(void *data); */
/* Delete functions are used only for more complex data structures */
void del_struct(void *data)
{
html_header *header = (html_header *)data;
/* Free data, assume calloc() was called both for node data and struct member */
if ((header) && (header->title)) free(header->title);
}
void del_double_arr(void *data)
{
double_arr_t *arr = (double_arr_t *)data;
/* Free data, assume calloc() was called both for node data and the array struct member */
if ((arr) && (arr->arr_data)) free(arr->arr_data);
}
/* -------------------------------------------------------------------------------- */
/* Node functions */
/* -------------------------------------------------------------------------------- */
/* ----------------------- */
/* Node - Helper functions */
/* ----------------------- */
/* Init node - basically allocate memory */
static node_t *node_init(void)
{
node_t *node = calloc(1, sizeof(*node));
if (!node)
fprintf(stderr, "ERROR: node_init(): calloc() failed: %s\n", strerror(errno));
return node;
}
/* Get number of nodes */
int list_count(const node_t *node)
{
int count = 0;
while (node)
{
++count;
node = node->next;
}
return count;
}
/*
Validate a node index.
Valid index range: -list_count() < index < list_count()
Convert negative values to positive values before validation.
Corner case: Valid indices for a NULL node (empty list): 0, -1, returns 0
*/
static int node_index(const node_t *node, const int index)
{
/* Corner cases */
if ((node == NULL) && ((index == 0) || (index == -1))) return 0;
/* Common cases */
else
{
int count = list_count(node);
int valid_index = (index < 0) ? count + index : index;
return (valid_index < count) ? valid_index : ERROR;
}
}
/*
Corner cases:
a. Empty list: Calling this function with *head=NULL and index=0 or index=-1 is interpreted as "add as first and last and only node".
b. Last node: Calling this function with *head!=NULL and index=-1 or count()-1 is interpreted as "append as last node".
This is identical to calling node_append() on for an empty list.
*/
static int node_corner_case(node_t **head, int valid_index)
{
return
(((*head == NULL) && (valid_index == 0)) ||
((*head != NULL) && (valid_index == list_count(*head) - 1)));
}
/* -------------------- */
/* Node - Add functions */
/* -------------------- */
/*
node_add()
Add a node at a specified node index.
Valid index range: -list_count() < index < list_count()
Valid indices for an empty list: 0, -1
Index:
0 => Add as first/head node.
1 => Add as second node. May be read as: "when added, there will be 1 node before this node in the list"
2 => Add as third node. May be read as: "when added, there will be 2 nodes before this node in the list"
-1 => Add as last node; same as node_add(list_count()-1) or node_append()
-2 => Add as 2nd last node; same as node_add(list_count()-2)
Before:
---- ---- ---- ---- ----
| |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ----
After (index = 3):
---- ---- ---- ----- ---- ----
| |--> | |--> | |--> |NEW|--> | |--> | |--> NULL
---- ---- ---- ----- ---- ----
*/
err_code node_add(node_t **head, void *data, add_func_t add_func, int index)
{
/* Validate index; node_index() returns a non-negative value on success */
int valid_index = node_index(*head, index);
if (valid_index == ERROR)
{
return ERROR;
}
else
{
/* Corner-cases (see above) */
int corner_case = node_corner_case(head, valid_index);
/* Create and set data to the new node to be inserted */
node_t *new_node = node_init();
if (!new_node)
{
return ERROR;
}
if (add_func)
{
/* If data allocation fails, either in set_func() or in data_init(), free() the node and return. */
int rc = 0;
if ((rc = add_func(&(new_node->data), data)) == ERROR)
{
free(new_node);
return ERROR;
}
else if (rc > 0)
{
/* If 'set_func' returns a size, copy data of that size here. */
size_t data_size = (size_t)rc;
new_node->data = data_init(data_size);
if (new_node->data == NULL)
{
free(new_node);
return ERROR;
}
memmove(new_node->data, data, data_size);
}
}
if (corner_case)
{
if (!*head)
{
/* First node, add to new list */
*head = new_node;
}
else
{
/* Append as last node to existing list */
node_t *node = *head;
while (node->next) node = node->next;
/* Append after last node */
node->next = new_node;
}
}
else
{
/* Insert new_node where index is pointing at. This is equivalent to append-after-previous-node. */
/* Note: No need to treat "new list case" here, as corner case was treated above */
node_t *prev_node = node_get(*head, valid_index - 1);
new_node->next = prev_node->next;
prev_node->next = new_node;
}
}
return OK;
}
/* Add node with explicit data size, return error code */
err_code node_add_size(node_t **head, void *data, size_t data_size, int index)
{
/* Validate index; node_index() returns a non-negative value on success */
int valid_index = node_index(*head, index);
if (valid_index == ERROR)
{
return ERROR;
}
else
{
/* Corner-cases */
int corner_case = node_corner_case(head, valid_index);
/* Create and set data to the new node to be inserted */
node_t *new_node = node_init();
if (!new_node)
{
return ERROR;
}
new_node->next = NULL;
/* Allocated memory for node data, copy data */
new_node->data = data_init(data_size);
if (new_node->data == NULL)
{
free(new_node);
return ERROR;
}
new_node->data = memmove(new_node->data, data, data_size);
if (corner_case)
{
if (!*head)
{
/* First node, add to new list */
*head = new_node;
}
else
{
/* Append as last node to existing list */
node_t *node = *head;
while (node->next) node = node->next;
/* Append after last node */
node->next = new_node;
}
}
else
{
/* Insert new_node where index is pointing at. This is equivalent to append-after-previous-node. */
/* Note: No need to treat "new list case" here, as corner case was treated above */
node_t *prev_node = node_get(*head, valid_index - 1);
new_node->next = prev_node->next;
prev_node->next = new_node;
}
}
return OK;
}
/*
node_appendp():
Append a pointer to an existing node at the end of a list.
Before:
---- ---- ---- ---- ----
| |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ----
----
| |--> NULL
----
After:
---- ---- ---- ---- ----
| |--> | |--> | |--> | |--> | |---
---- ---- ---- ---- ---- |
|
----------------------------------
|
| ----
--> | |--> NULL
----
*/
/* https://pastebin.com/VT6UBBZD */
err_code node_appendp(node_t **head, node_t *existing)
{
if (existing == NULL) return ERROR;
else
{
node_t *curr = *head;
if (curr == NULL)
{
curr = existing;
curr->next = NULL;
*head = curr;
}
else
{
while (curr->next) curr = curr->next;
curr->next = existing;
existing->next = NULL;
}
}
return OK;
}
/*
node_prependp():
Prepend a pointer to an existing node at the beginning of a list.
Used internally by qsort.
Before:
----
| |--> NULL
----
---- ---- ---- ---- ----
| |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ----
After:
----
| |---
---- |
|
-----------------
|
| ---- ---- ---- ---- ----
->| |--> | |--> | |--> | |--> | |--- NULL
---- ---- ---- ---- ----
*/
/* https://pastebin.com/VT6UBBZD */
err_code node_prependp(node_t **head, node_t *existing)
{
if (existing == NULL) return ERROR;
existing->next = *head;
*head = existing;
return OK;
}
/*
node_insertp():
Insert a pointer to an existing node at a given index of a list.
Internally:
- if valid_index = 0, return node_prepend()
- if valid_index = -1, return node_append()
- call list_split() to split the lists
- call node_prependp() on second list
- call list_join() to join the lists
Before:
----
| |--> NULL
----
---- ---- ---- ---- ----
| |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ----
After (insert at index=3):
----
-->| |--------------
| ---- |
| |
----------------- |
| |
---- ---- ---- | | ---- ----
| |--> | |--> | |-- --> | |--> | |--- NULL
---- ---- ---- ---- ----
*/
err_code node_insertp(node_t **head, node_t *existing, int index)
{
if (existing == NULL) return ERROR;
else
{
int valid_index = node_index(*head, index);
if (valid_index == ERROR) return ERROR;
else
{
/* if valid_index = 0, prepend node and return */
if (valid_index == 0)
{
node_prependp(head, existing);
return OK;
}
/* if valid_index = -1, append node and return */
else if (valid_index == (list_count(*head) - 1))
{
node_appendp(head, existing);
return OK;
}
else
{
/* Split lists */
node_t *tail = list_split(head, index);
/* Prepend exisitng node to tail */
existing->next = NULL;
node_prependp(&tail, existing);
/* Join head and tail */
list_join(head, tail);
}
}
}
return OK;
}
/* Get a node by index */
/* Index may be negative, but not out of range, i.e. -list_count() < index < list_count() */
node_t *node_get(const node_t *head, const int index)
{
int valid_index = node_index(head, index);
if (valid_index == ERROR)
{
return NULL;
}
else
{
node_t *node = (node_t *)head;
int i = 0;
for (i = 0; i < valid_index; ++i)
{
node = node->next;
}
return node;
}
}
/*
list_copy_range():
Get a result, a subset of nodes given by an index range
Internally, create an empty list, and call node_append() for each node in range.
As all "result functions", a new list is created, and returned on the stack.
*/
node_t *list_copy_range(const node_t *head, const int index_from, const int index_to, const copy_func_t copy_func, del_func_t del_func)
{
int valid_index_from = node_index(head, index_from);
int valid_index_to = node_index(head, index_to);
if ((valid_index_from == ERROR) || (valid_index_to == ERROR)) return NULL;
else
{
node_t *result = NULL;
node_t *curr = node_get(head, index_from);
int index = valid_index_from;
int rc = OK;
for (index = valid_index_from; index <= valid_index_to; ++index)
{
if (curr == NULL)
{
rc = ERROR;
fprintf(stderr, "ERROR: list_copy_range(): unexpected NULL node at index %d\n", index);
}
if ((rc = node_append(&result, curr->data, copy_func)) == ERROR)
{
rc = ERROR;
fprintf(stderr, "ERROR: list_copy_range(): couldn't append node %d to result\n", index);
}
if (rc == ERROR)
{
/* If an error occurred in the middle of creating the result list, cleanup the result. */
list_del(&result, del_func);
return NULL;
}
curr = curr->next;
}
return (rc == OK) ? result : NULL;
}
}
/*
list_copy_matching():
Similar to list_copy_range(), with the range replaced by a matching condition,
defined in the 'match_func' callback
*/
node_t *list_copy_matching(const node_t *head, const match_func_t match_func, const void *match_data,
const copy_func_t copy_func, del_func_t del_func)
{
node_t *result = NULL;
node_t *curr = (node_t *)head;
int rc = OK;
int i = 0;
if (match_func == NULL) return NULL;
while (curr)
{
if (match_func(curr->data, match_data) == MATCH)
{
if ((rc = node_append(&result, curr->data, copy_func)) == ERROR)
{
fprintf(stderr, "ERROR: list_copy_matching(): couldn't append original node %d to result\n", i);
list_del(&result, del_func);
return NULL;
}
}
++i;
curr = curr->next;
}
return (rc == OK) ? result : NULL;
}
/*
node_set():
Set a node value, node selected by index.
The new value is set by the 'set_func' callback, which takes both the 'data' argument and the current
node data as arguments, so the value may be either a constant or a value based on a function.
Index may be negative, but not out of range, i.e. -list_count() < index < list_count().
While node_set() has much in common with node_add(), node_set() does not accept a NULL head (empty list).
*/
err_code node_set(node_t **head, const set_func_t set_func, const void *set_data, const void *set_aux_data, const int index)
{
/* Corner case: Calling this function with *head=NULL and index=0 is interpreted as "insert as first node". */
/* This is identical to calling node_append() on for an empty list. */
if (*head == NULL) return ERROR;
else
{
/* Validate index; node_index() returns a non-negative value on success */
int valid_index = node_index(*head, index);
if (valid_index == ERROR) return ERROR;
else
{
/* Create and set data to the new node to be inserted */
node_t *curr = node_get(*head, valid_index);
if (!curr) return ERROR;
if (set_func)
{
int rc = 0;
if ((rc = set_func(&(curr->data), set_data, set_aux_data)) == ERROR) return ERROR;
else if (rc > 0)
{
/* If 'set_func' returns a size, copy data of that size here. */
size_t data_size = (size_t)rc;
memmove(curr->data, set_data, data_size);
}
}
}
}
return OK;
}
/*
node_set_size():
Set node value with explicit data size, return error code.
This function is similar to node_add_size(), but this function does not accept a NULL head.
*/
err_code node_set_size(node_t **head, void *data, size_t data_size, int index)
{
if (*head == NULL) return ERROR;
else
{
node_t *curr = node_get(*head, index);
memmove(curr->data, data, data_size);
}
return OK;
}
/*
list_set_range():
Calls node_set() internally.
*/
err_code list_set_range(node_t **head, const set_func_t set_func, const void *set_data, const void *set_aux_data,
const int index_from, const int index_to)
{
int valid_index_from = node_index(*head, index_from);
int valid_index_to = node_index(*head, index_to);
if ((valid_index_from == ERROR) || (valid_index_to == ERROR)) return ERROR;
else
{
int index = index_from;
int rc = OK;
for (index = valid_index_from; index <= valid_index_to; ++index)
{
if ((rc = node_set(head, set_func, set_data, set_aux_data, index)) == ERROR)
{
fprintf(stderr, "ERROR: list_set_range(): node_set() failed for node %d\n", index);
break;
}
}
return rc;
}
}
/*
list_set_matching():
Calls node_set() internally.
Optionally, 'match_data' may be used as an extra argument to 'match_func'.
Optionally, 'set_data' may be used as an extra argument to 'set_func'.
*/
err_code list_set_matching(node_t **head, const set_func_t set_func, const void *set_data, const void *set_aux_data,
const match_func_t match_func, const void *match_data)
{
node_t *curr = *head;
int rc = OK;
int index = 0;
if ((set_func == NULL) || (match_func == NULL)) return ERROR;
while (curr)
{
if (match_func(curr->data, match_data) == MATCH)
{
if ((rc = node_set(head, set_func, set_data, set_aux_data, index)) == ERROR)
{
fprintf(stderr, "ERROR: list_set_matching(): node_set() failed for node %d\n", index);
break;
}
}
++index;
curr = curr->next;
}
return rc;
}
/*
node_copy():
Create a copy of a node.
Internally, get the original node, and then pass the data and the copy callback to node_append()
The node and its data has to be free():ed afterwards.
*/
node_t *node_copy(const node_t *head, int index, const copy_func_t copy_func)
{
node_t *orig = node_get(head, index);
node_t *copy = NULL;
if (node_append(©, orig->data, copy_func) == ERROR) return NULL;
return copy;
}
/*
node_move():
Move a node from one position to another within the same list, or from a position in one list to a position in another list.
If the second argument (head2) is NULL, the node will be moved within the same list (head1).
If head2 is NULL and index1 = index2, a warning will be shown (trying to move a node
to the same index within the same list just doesn't make sense).
Note:
It is tricky to keep track of the current index in this function,
as the node count remains the same when moving within a list, while the node count
changes when moving a node between lists.
1 list: Before (index = 2):
---- ---- ------ ---- ---- ---- ----
| |--> | |--> |CURR|--> | |--> | |--> | |--> | |--> NULL
---- ---- ------ ---- ---- ---- ----
1 list: After (index = 5):
---- ---- ---- ---- ---- ------ ----
| |--> | |--> | |--> | |--> | |--> |CURR|--> | |--> NULL
---- ---- ---- ---- ---- ------ ----
2 lists: Before (index = 2 in list 1):
---- ---- ------ ---- ---- ---- ----
LIST 1: | |--> | |--> |CURR|--> | |--> | |--> | |--> | |--> NULL
---- ---- ------ ---- ---- ---- ----
---- ---- ---- ---- ---- ----
LIST 2: | |--> | |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ---- ----
After - move between lists (index = 5 in list 2):
---- ---- ---- ---- ---- ----
LIST 1: | |--> | |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ------ ----
LIST 2: | |--> | |--> | |--> | |--> | |--> |CURR|--> | |--> NULL
---- ---- ---- ---- ---- ------ ----
*/
err_code node_move(node_t **head1, node_t **head2, int index1, int index2)
{
if (*head1 == NULL) return ERROR;
else
{
int valid_index1 = node_index(*head1, index1);
int valid_index2 = (head2 == NULL) ? node_index(*head1, index2) : node_index(*head2, index2);
if ((valid_index1 == ERROR) || (valid_index2 == ERROR)) return ERROR;
if ((head2 == NULL) && (valid_index1 == valid_index2))
{
fprintf(stderr, "WARNING: node_move(): trying to move a node within the same list from index %d to the same index %d does not make sense.\n", index1, index2);
return WARNING;
}
else
{
/* Nodes before and after from: prev_from, from = prev_from->next, next_from = from->next */
/* Nodes before and after to: prev_to, to = prev_to->next, next_to = to->next */
/* Join: prev_from->next = next_from */
/* Split and join: prev_to->next = from, from->next = next_to */
node_t *prev_from = (valid_index1 == 0) ? *head1 : node_get(*head1, valid_index1 - 1);
node_t *prev_to =
((head2 != NULL) ?
((valid_index2 == 0) ?
*head2 :
node_get(*head2, valid_index2-1)) :
node_get(*head1, valid_index2));
node_t *from = prev_from->next;
node_t *to = prev_to->next;
/* Join from's prev and next nodes */
prev_from->next = from->next;
/* Split and join to's prev and next nodes */
from->next = to;
prev_to->next = from;
}
}
return OK;
}
/*
node_swap():
This is basically node_move() applied twice, with the inverse indices.
If second argument 'head2' is NULL, swap nodes within list 'head1' (which cannot be NULL).
If second argument 'head2' is not NULL, swap nodes between lists 'head1' and 'head2'.
1 list: Before swap (index = 2,5):
---- ---- ---- ---- ---- ---- ----
| |--> | |--> |N2|--> | |--> | |--> |N5|--> | |--> NULL
---- ---- ---- ---- ---- ---- ----
1 list: After (index = 5,2):
---- ---- ---- ---- ---- ---- ----
| |--> | |--> |N5|--> | |--> | |--> |N2|--> | |--> NULL
---- ---- ---- ---- ---- ---- ----
2 lists: Before swap (index = 2 in list 1, index = 5 in list 2):
---- ---- ---- ---- ---- ---- ---- ---- ----
LIST 1: | |--> | |--> |N2|--> | |--> | |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ----
LIST 2: | |--> | |--> | |--> | |--> | |--> |N5|--> NULL
---- ---- ---- ---- ---- ----
After swap (index = 5 in list 1, index = 2 in list 2):
---- ---- ---- ---- ---- ---- ---- ---- ----
LIST 1: | |--> | |--> |N5|--> | |--> | |--> | |--> | |--> | |--> | |--> NULL
---- ---- ---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ----
LIST 2: | |--> | |--> | |--> | |--> | |--> |N2|--> NULL
---- ---- ---- ---- ---- ----
*/
err_code node_swap(node_t **head1, node_t **head2, int index1, int index2)
{
err_code rc = ERROR;
int valid_index1 = node_index(*head1, index1);
int valid_index2 = (head2 == NULL) ? node_index(*head1, index2) : node_index(*head2, index2);
if (head2 == NULL)
{
if (valid_index1 == valid_index2)
{
fprintf(stderr,
"WARNING: node_swap(): trying to swap two nodes within the same list with the same indices %d and %d does not make sense.\n",
index1, index2);
return WARNING;
}
else if (valid_index2 < valid_index1)
{
/* Swap indices if within the same list */
int tmp = valid_index2; valid_index2 = valid_index1; valid_index1 = tmp;
}
}
/* Move the first node to the index for the second node */
if (node_move(head1, head2, valid_index1, valid_index2) == ERROR) return ERROR;
/* The first node has been inserted into the list for the position of the second node. The second node's position has been incremented by 1. */
rc = (head2 == NULL) ?
node_move(head1, NULL, valid_index2-1, valid_index1-1) :
node_move(head2, head1, valid_index2+1, valid_index1);
return rc;
}
/* Print node data - any formatting takes place in the 'print_data' callback */
typedef void (*data_print_t)(void *data);
void node_print(node_t *node, data_print_t print_data)
{
print_data(node->data);
}
/* Print all nodes */
typedef void (*data_print_all_t)(void *data, int n);
void list_print(node_t *node, data_print_t print_data)
{
while (node)
{
print_data(node->data);
node = node->next;
}
}
/* Delete a node, by index */
/* Index may be negative, but not out of range, i.e. -list_count() < index < list_count() */
/* Optionally, use the 'del_func' callback to free data. The callback may be NULL for simple data types. */
err_code node_del(node_t **head, del_func_t del_func, int index)
{
/* Deleting from an empty list is considered an error. */
if (*head == NULL) return ERROR;
else
{
/* Validate index; node_index() returns a non-negative value on success */
int valid_index = node_index(*head, index);
if (valid_index == ERROR) return ERROR;
else
{
node_t *prev = NULL, *curr = NULL;
if (valid_index == 0)
{
curr = *head;
}
else
{
prev = node_get(*head, valid_index-1);
if (!prev) return ERROR;
curr = prev->next;
}
/* Delete node data before deleting the node itself */
if (del_func) del_func(curr->data);
else if (curr->data) free(curr->data);
/* Corner case: Head node */
if (valid_index == 0)
{
*head = (*head)->next;
}
else
{
prev->next = curr->next;
}
curr->next = NULL;
free(curr);
}
}
return OK;
}
/* Delete a range of nodes */
/*
TODO:
This function calls node_del() for each index, which isn't optimized,
as node_del() "joins" the previous eith the next node when deleting the current node.
This "join action" is repeated for each node deletion.
A faster solution would be to delete all nodes in a range,
and then "join" the node previous to the first node in range with the next node after the last node in range.
*/
err_code list_del_range(node_t **head, del_func_t del_func, int index_from, int index_to)
{
int valid_index_from = node_index(*head, index_from);
int valid_index_to = node_index(*head, index_to);
if ((valid_index_from == ERROR) || (valid_index_to == ERROR)) return ERROR;
else
{
int index = 0;
for (index = valid_index_from; index <= valid_index_to; ++index)
{
if (node_del(head, del_func, valid_index_from) == ERROR)
{
fprintf(stderr, "ERROR: list_del_range(): couldn't delete node at index %d\n", index);
return ERROR;
}
}
}
return OK;
}
/* Delete matching node(s) */
/* The 'del_func' callback may be NULL for simple data types */
/* In this function, the 'first node corner case' applies for all matching nodes at the beginning of the list. */
err_code list_del_matching(node_t **head, match_func_t match_func, void *match_data, del_func_t del_func)
{
node_t *curr = *head;
/* Corner case(s): remove initial matching element(s) */
while (*head)
{
match_code match = match_func ? match_func((*head)->data, match_data) : NO_MATCH;
if (match != MATCH) break;
else
{
node_t *tmp = *head;
*head = (*head)->next;
if (del_func) del_func(tmp->data);
else if (tmp->data) free(tmp->data);
free(tmp);
}
}
/* remove non-initial matching elements */
/* loop invariant: "current != NULL && current->data != key" */
for (curr = *head; curr != NULL; curr = curr->next)
{
while (curr->next != NULL)
{
match_code match = match_func ? match_func(curr->next->data, match_data) : NO_MATCH;
if (match != MATCH) break;
else
{
node_t *tmp = curr->next;
if (del_func) del_func(tmp->data);
else if (tmp->data) free(tmp->data);
curr->next = tmp->next;
free(tmp);
}
}
}
return OK;
}
/* Delete duplicated node(s) */
/*
This function uses 2 callbacks:
1. The 'cmp_func', which "compares anything", that is up to the callback to define.
2. The 'del_func', which may do additional cleanup. If set to NULL, free(node->data) is called.
Algorithm:
Split list into two lists:
1. Resulting list, appending unique nodes. Initialize with head node.
2. Original list, check each node against resulting list.
If found in resulting list (duplicate), delete node.
If not found in resulting list (unique), move to resulting list.
The StackOverflow solution (see below) is similar, but keeps the last found node instead of the first one.
Not a big issue, but it may delete the head node. With this solution, the head node is never deleted.
Best case:
Original list has N nodes, and all node values are equal, so the resulting list will have only 1 element.
As we check each node against the resulting list, there will be N comparisions.
Worst case:
The original list has N nodes, and all node values are different, so the resulting list will also have N elements.
This means that there will be N + (N-1) + (N-2) + .. + 1 = N(N+1)/2 comparisions.
TODO:
Performance may be improved using a temporary hash table, as it only requires one iteration through the original list.
Each node value from the original list is stored in a hash table, and if the hash table entry is empty,
the node is added to the resulting list.
This alternative algorithm is definitely faster for big lists,
but it requires additional memory and additional operations due to
the hash table operations, so it is not automagically a faster alternative for small lists.
*/
err_code list_del_dup(node_t **head, cmp_func_t cmp_func, del_func_t del_func)
{
/* Lists with 0 or 1 nodes never have duplicates. */
if ((*head == NULL) || ((*head)->next == NULL)) return OK;
/* If the cmp_func=NULL, simply do not remove duplicates */
/* TODO: Consider passing NULL for cmp_func as an error, maybe??? */
if (cmp_func == NULL) return OK;
else
{
/* Original list, exclude head */
node_t *orig = (*head)->next;
/* Resulting list (start with head node, which is always unique, and thus needs no check) */
/* We also keep track of the last node in the resulting list. */
node_t *res = *head;
node_t *res_last = *head;
res->next = NULL;
/* Loop through original list */
while (orig)
{
/* Rewind resulting list */
res = *head;
/* Loop through resulting list to detect a duplicate */
while (res)
{
if (cmp_func(orig->data, res->data) == CMP_EQUAL) break;
res_last = res;
res = res->next;
}
/*
If we hit the end of the resulting list (res is NULL), there was no match, so we have a unique node.
In that case, move the orig node to the end of res, after the last node in the resulting list.
Otherwise, delete the orig node.
*/
if (res == NULL)
{
/* Node is unique: Move orig node to res, move forward in orig list to check next node. */
node_t *tmp = orig;
orig = orig->next;
tmp->next = NULL;
res_last->next = tmp;
}
else
{
/* Node is duplicate: Delete orig node, move forward in orig list. */
node_t *tmp = orig;
orig = orig->next;
/* Delete duplicated original node */
if (del_func) del_func(tmp->data);
else if (tmp->data) free(tmp->data);
free(tmp);
}
}
}
return OK;
}
/* https://stackoverflow.com/questions/42953034/c-remove-duplicates-from-unsorted-linked-list */
/* This StackOverflow version compares head against other nodes, but deletes from the beginning, including head if duplicates are found */
err_code list_del_dupSO(node_t **head, cmp_func_t cmp_func, del_func_t del_func)
{
node_t *tmp = NULL;
while (*head)
{
/* Look below *head, to see if it has any duplicates */
for (tmp = (*head)->next; tmp; tmp = tmp->next)
{
/* if (tmp->data == (*head)->data) break; */
if (cmp_func(tmp->data, (*head)->data) == CMP_EQUAL) break;
}
/* Hit end of list; found no duplicate, advance head */
if (!tmp)
{
head = &(*head)->next;
continue;
}
/* Duplicate found; delete *head */
tmp = (*head)->next;
if (del_func) del_func((*head)->data);
else if ((*head)->data) free((*head)->data);
free(*head);
*head = tmp;
}
return OK;
}
/*
This version is very similar to list_del_matching(), except the "corner case" with
head node(s) may be omitted, as a head node never is a duplicate.
*/
err_code list_del_dupBUGGY(node_t **head, cmp_func_t cmp_func, del_func_t del_func)
{
/* Deleting duplicates from an list with 0 or 1 nodes is not considered an error. */
if ((*head == NULL) || ((*head)->next == NULL)) return OK;
/* If the cmp_func callback is NULL, simply do not remove any duplicates */
/* Consider cmp_func=NULL an error, maybe??? */
if (cmp_func == NULL) return OK;
else
{
node_t *node1 = NULL;
node_t *node2 = NULL;
node_t *prev2 = NULL;
/* remove non-initial matching elements */
/* loop invariant: "current != NULL && current->data != key" */
for (node1 = (*head);
node1 != NULL;
node1 = node1->next)
{
for (node2 = node1->next;
node2 != NULL;
prev2 = node2, node2 = node2->next)
if (cmp_func(node1->data, node2->data) == CMP_EQUAL)
{
node_t *dup = node2;
if (del_func) del_func(dup->data);
else if (dup->data) free(dup->data);
prev2->next = node2->next;
node2 = node2->next;
free(dup);
/* If last node was deleted, the "for increment" 'node2 = node2->next' will fail, so break */
if (node2 == NULL) break;
}
}
}
return OK;
}
/* void ListDelete(nodeT **listP, elementT value) */
err_code list_del_dupEDU(node_t **head, cmp_func_t cmp_func, del_func_t del_func)
{
node_t *curr, *prev;
/* For 1st node, indicate there is no previous. */
prev = NULL;
/*
* Visit each node, maintaining a pointer to
* the previous node we just visited.
*/
for (curr = (*head)->next;
curr != NULL;
prev = curr, curr = curr->next)
{
/* if (cmp_func(node1->data, node2->data) == CMP_EQUAL) */
(void)cmp_func;
/* if (curr->element == value) */
if (1)
{
if (prev == NULL) {
/* Fix beginning pointer. */
*head = curr->next;
}
else
{
/* Found it. */
/*
* Fix previous node's next to
* skip over the removed node.
*/
/* if (del_func) del_func(curr->data); */
(void)del_func;
/* else if (curr->data) free(curr->data); */
prev->next = curr->next;
}
/* Deallocate the node. */
free(curr);
/* Done searching. */
}
}
return OK;
}
/* -------------------------------------------------------------------------------- */
/*
list_map():
Similar to list_copy_matching().
The big difference is while list_copy_matching() uses a 'match_func' to only filter out nodes,
list_map() calls a 'map_func', which may both filter out nodes, but also change node values in the resulting list.
This means that 'map_func' callback may allocate memory for node data, so .
*/
node_t *list_map(const node_t *head, const map_func_t map_func, const void *map_data, const add_func_t add_func, del_func_t del_func)
{
node_t *result = NULL;
node_t *curr = (node_t *)head;
int rc = OK;
int i = 0;
if (map_func == NULL) return NULL;
while (curr)
{
void *result_data = NULL;
/* Use the resulting data for the new list */
if (map_func(&result_data, curr->data, map_data) == MATCH)
{
/* Append matching nodes to result */
if ((rc = node_append(&result, result_data, add_func)) == ERROR)
{
fprintf(stderr, "ERROR: list_map(): couldn't append original node %d to result\n", i);
list_del(&result, del_func);
if (result_data) free(result_data);
return NULL;
}
}
if (result_data) free(result_data);
++i;
curr = curr->next;
}
return (rc == OK) ? result : NULL;
}
/* Delete all nodes - generic */
void list_del(node_t **head, del_func_t del_func)
{
node_t *current = *head, *next = NULL;
while (current)
{
/* The 'del_func' call is only needed for complex data structures, such as the 'node_struct' and 'node_double_arr' lists */
if (del_func) del_func(current->data);
if (current->data) free(current->data);
next = current->next;
free(current);
current = next;
}
/* Set variable to NULL *before* free(). */
/* Valgrind doesn't like it the other way around! */
*head = NULL;
/* head = NULL; */
free(*head);
}
/* https://rosettacode.org/wiki/Singly-linked_list/Element_removal#C */
node_t *node_del_index(node_t *head, int pos)
{
int i=1;
node_t *temp, *iter;
if (head)
{
iter = head ;
if (pos == 1)
{
head = head->next;
iter->next = NULL;
free(iter);
}
else
{
while (i++ != pos-1)
iter = iter->next;
temp = iter->next;
iter->next = temp->next;
temp->next = NULL;
free(temp);
}
}
return head;
}
/* List functions */
/*
reverse a linked list
*/
err_code list_rev(node_t **head)
{
node_t *prev = NULL;
node_t *current = *head;
node_t *next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
return OK;
}
/*
list_split():
Split a list at a given index.
The original list is truncated, and the new list is returned on the stack.
Returns NULL if an error occurred.
Corner cases: index == 0 => head1 = NULL, head2 = entire list
*/
node_t *list_split(node_t **head1, int index)
{
node_t *head2 = node_get(*head1, index);
if (head2 == NULL) return NULL;
if (index == 0)
{
*head1 = NULL;
}
else
{
node_t *head1_last = node_get(*head1, index-1);
if (head1_last == NULL) return NULL;
head1_last->next = NULL;
}
return head2;
}
/* https://pastebin.com/VT6UBBZD */
/*
* Append a list at the end of another list
* Head list is passed by address, so the content of the caller
* variable can be updated to point to the new head
* if the original list was empty (NULL)
*
* Complexity: O( len(l0) )
*/
node_t *list_join(node_t **head1, node_t *head2)
{
/* Go to the end of the first list */
while (*head1) head1 = &((*head1)->next);
/* Append the second list's head as last node to first list. */
*head1 = head2;
return *head1;
}
/*
list_copy():
Get a deep copy of a list. The new list has to be deallocated with list_del().
Internally, call list_copy_range() with the entire range for a list.
*/
node_t *list_copy(node_t *orig, const copy_func_t copy_func, del_func_t del_func)
{
return (orig == NULL) ? NULL : list_copy_range(orig, 0, list_count(orig) - 1, copy_func, del_func);
}
/* Quicksort */
/* https://en.wikipedia.org/wiki/Quicksort */
static err_code list_qsort(node_t **head, cmp_func_t cmp_func)
{
/* A list with 0 or 1 elements doesn't need to be sorted. */
if ((*head == NULL) || ((*head)->next == NULL)) return OK;
else
{
/* Extract the pivot */
node_t *pivot = *head;
/* int data = pivot->data; */
node_t *p = pivot->next;
/* Construct left and right lists in place in a single pass */
node_t *left = NULL;
node_t *right = NULL;
node_t *result = NULL;
pivot->next = NULL;
while (p)
{
node_t *curr = p;
p = p->next;
if (cmp_func(curr->data, pivot->data) == CMP_LESS_THAN)
{
node_prependp(&left, curr);
}
else
node_prependp( &right, curr);
}
/* We now sort left and right */
/* If left and right are of vastly different lengths, the complexity won't be O(n log n) */
list_qsort(&left, cmp_func);
list_qsort(&right, cmp_func);
/* We now concatenate lists [this is inefficient, but doesn't hurt complexity] */
list_join(&result, left);
list_join(&result, pivot);
list_join(&result, right);
*head = result;
}
return OK;
}
/* Insertion Sort */
/* https://en.wikipedia.org/wiki/Insertion_sort */
static err_code list_isort(node_t **head, cmp_func_t cmp_func)
{
/* zero or one element in list */
if (!*head || !(*head)->next) return OK;
else
{
/* build up the sorted array from the empty list */
node_t *sorted = NULL;
node_t *curr = *head;
/* take items off the input list one by one until empty */
while (curr != NULL)
{
/* remember the previous */
node_t *prev = curr;
/* trailing pointer for efficient splice */
node_t **trailing = &sorted;
/* pop head off list */
curr = curr->next;
/* splice head into sorted list at proper place */
while (!(*trailing == NULL || cmp_func(prev->data, (*trailing)->data) == CMP_LESS_THAN))
{
/* does head belong here? */
/* if not - continue down the list */
trailing = &(*trailing)->next;
}
prev->next = *trailing;
*trailing = prev;
}
*head = sorted;
return OK;
}
}
/*
list_sort():
Generic sort.
The 'sort_func' callback should point to a sort algorithm function.
The 'cmp_func' callback is used internally by the the sort function to compare any two values.
If sort flag is SORT_ASC (or set to 0), return sorted list.
If sort flag is SORT_DESC (or != 0), return sorted and reversed list.
*/
err_code list_sort(node_t **head, sort_func_t sort_func, cmp_func_t cmp_func, sort_flag flag)
{
if (sort_func(head, cmp_func) == ERROR) return ERROR;
/* If flag is DESC, reverse list. If ASC, do nothing. */
return (flag != SORT_ASC) ? list_rev(head) : OK;
}
/* ------------------------ */
/* Node functions - aliases */
/* ------------------------ */
/* ALIAS: node_prepend() -> node_add(0) */
err_code node_prepend(node_t **head, void *data, add_func_t add_func)
{
return node_add(head, data, add_func, 0);
}
/* ALIAS: node_prepend_size() -> node_add_size(0) */
err_code node_prepend_size(node_t **head, void *data, size_t data_size)
{
return node_add_size(head, data, data_size, -1);
}
/* ALIAS: node_append() -> node_add(-1) */
err_code node_append(node_t **head, void *data, add_func_t add_func)
{
return node_add(head, data, add_func, -1);
}
/* ALIAS: node_append_size() -> node_add_size(-1) */
err_code node_append_size(node_t **head, void *data, size_t data_size)
{
return node_add_size(head, data, data_size, -1);
}
/* ALIAS: node_get_head() -> node_get(0) */
node_t *node_get_head(node_t *head)
{
return head;
/* return node_get(head, 0); */
}
/* ALIAS: node_get_tail() -> node_get(-1) */
node_t *node_get_tail(node_t *head)
{
while (head->next) head = head->next;
return head;
}
/* ALIAS: node_set_head() -> node_set(0) */
err_code node_set_head(node_t **head, const set_func_t set_func, const void *set_data, const void *set_aux_data)
{
return node_set(head, set_func, set_data, set_aux_data, 0);
}
/* ALIAS: node_set_tail() -> node_set(-1) */
err_code node_set_tail(node_t **head, const set_func_t set_func, const void *set_data, const void *set_aux_data)
{
return node_set(head, set_func, set_data, set_aux_data, -1);
}
/* ALIAS: node_del_head() -> node_del(0) */
err_code node_del_head(node_t **head, del_func_t del_func)
{
return node_del(head, del_func, 0);
}
/* ALIAS: node_del_tail() -> node_del(-1) */
err_code node_del_tail(node_t **head, del_func_t del_func)
{
return node_del(head, del_func, -1);
}
/* ------------------------ */
/* List functions - aliases */
/* ------------------------ */
err_code list_set(node_t **head, const set_func_t set_func, const void *set_data, const void *set_aux_data)
{
return list_set_range(head, set_func, set_data, set_aux_data, 0, -1);
}
/* TODO: list_del_range() isn't optimized, so list_del() is implemented as a standalone function, instead of an alias. */
/* err_code list_del(node_t **head, del_func_t del_func) */
/* { */
/* return list_del_range(head, del_func, 0, -1); */
/* } */
/* ALIAS: list_del_from(pos) -> list_del_range(pos, -1) */
err_code list_del_from(node_t **head, del_func_t del_func, int pos)
{
return list_del_range(head, del_func, pos, -1);
}
/* ALIAS: list_del_to(pos) -> list_del_range(0, pos) */
err_code list_del_to(node_t **head, del_func_t del_func, int pos)
{
return list_del_range(head, del_func, 0, pos);
}
/* -------------------------------------------------------------------------------- */
/* MAIN */
/* -------------------------------------------------------------------------------- */
int
main(int argc, char *argv[])
{
node_t *node_int = NULL;
node_t *result_range_int = NULL;
node_t *result_map_int = NULL;
node_t *node_int_copy[3] = {NULL, NULL, NULL};
node_t *node_string = NULL;
node_t *node_struct = NULL;
node_t *node_double_arr = NULL;
/* Head references for all lists */
node_t *head_int = NULL;
node_t *head_int_copy = NULL;
node_t *head_int_split = NULL;
node_t *head_string = NULL;
node_t *head_struct = NULL;
node_t *head_double_arr = NULL;
node_t *node = NULL;
int i = 0;
err_code rc = ERROR;
printf("\nREADME EX04\n");
printf("----------------------------------------\n");
printf("\nint list: add 100 nodes to empty list, with values 0-99, calling 'node_append_size()':\n");
printf("----------------------------------------------------------------------------------------\n");
for (i = 0; i < 100; ++i)
{
/* Error handling */
if ((rc = node_append_size(&node_int, &i, sizeof(i))) == ERROR)
{
fprintf(stderr, "ERROR: node_append_size(): couldn't append 'int' node, index %d\n", i);
break;
}
/* Store list head in separate variable for future use. */
if (i == 0) head_int = node_int;
}
printf("node count [100]: %d\n", list_count(head_int));
printf("The 'head_int' list, node 0: [0] "); node_print(head_int, print_int);
printf("The 'head_int' list, node 1: [1] "); node_print(head_int->next, print_int);
printf("The 'head_int' list, node 2: [2] "); node_print(head_int->next->next, print_int);
/* Print node 42 of 100 - should print 42 */
node = node_get(head_int, 42);
node_print(node, print_int);
/* Print last node of 100 - should print 99 */
node = node_get(head_int, list_count(head_int)-1);
node_print(node, print_int);
printf("\nint list: append 100 new nodes after 100 existing nodes, with values 1000-1099, calling 'size-only' node_append():\n");
printf("--------------------------------------------------------------------------------------------------------------------\n");
for (i = 1000; i < 1100; ++i)
{
/* Error handling */
if ((rc = node_append(&head_int, &i, add_int_size_only)) == ERROR)
{
fprintf(stderr, "ERROR: node_append(): couldn't append 'int' node, index %d\n", i);
break;
}
}
printf("node count [200]: %d\n", list_count(head_int));
printf("The 'node_int' list, node 100: [1000] "); node_print(node_get(head_int, 100), print_int);
printf("The 'node_int' list, node 101: [1001] "); node_print(node_get(head_int, 101), print_int);
printf("The 'node_int' list, node 102: [1002] "); node_print(node_get(head_int, 102), print_int);
/* Print node 142 of 200 - should print 1042 */
node = node_get(head_int, 142);
node_print(node, print_int);
/* Print last node of 200 - should print 1099 */
node = node_get(head_int, list_count(head_int)-1);
node_print(node, print_int);
/* Delete range of nodes */
{
int index_from = 10;
int index_to = 179;
printf("\nint list: delete 170 nodes %d-%d calling list_del_range():\n", index_from, index_to);
printf("---------------------------------------------------------------\n");
printf("Node count before list_del_range() [200]: %d\n", list_count(head_int));
if ((rc = list_del_range(&head_int, NULL, index_from, index_to)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_range() failed when deleting 'int' nodes at %d-%d\n", index_from, index_to);
}
printf("Node count after list_del_range() [30]: %d\n", list_count(head_int));
printf("The 'node_int' list, node 9: [9] "); node_print(node_get(head_int, 9), print_int);
printf("The 'node_int' list, node 10: [1080] "); node_print(node_get(head_int, 10), print_int);
printf("The 'node_int' list, node 11: [1081] "); node_print(node_get(head_int, 11), print_int);
}
printf("\nint list: append 100 nodes with values 2000-2099, calling 'complete' node_append():\n");
printf("-------------------------------------------------------------------------------------\n");
for (i = 2000; i < 2100; ++i)
{
/* Error handling */
if ((rc = node_append(&head_int, &i, add_int)) == ERROR)
{
fprintf(stderr, "ERROR: node_append(): couldn't append 'int' node, index %d\n", i);
break;
}
}
printf("node count [130]: %d\n", list_count(head_int));
printf("The 'node_int' list, node 127: "); node_print(node_get(head_int, 127), print_int);
printf("The 'node_int' list, node 128: "); node_print(node_get(head_int, 128), print_int);
printf("The 'node_int' list, node 129: "); node_print(node_get(head_int, 129), print_int);
printf("\nint list: insert 100 nodes between 100 first and 30 last nodes, with values 3000-3099, calling 'complete' node_add():\n");
printf("----------------------------------------------------------------------------------------------------------------------\n");
for (i = 100; i < 200; ++i)
{
int data = i + 2900;
/* Error handling */
if ((rc = node_add(&head_int, &data, add_int, i)) == ERROR)
{
fprintf(stderr, "ERROR: node_add(): couldn't add 'int' node at index %d\n", i);
break;
}
}
printf("node count [230]: %d\n", list_count(head_int));
printf("The 'node_int' list, node 99 [data=2069]: "); node_print(node_get(head_int, 99), print_int);
printf("The 'node_int' list, node 100 [data=3000]: "); node_print(node_get(head_int, 100), print_int);
printf("The 'node_int' list, node 101 [data=3001]: "); node_print(node_get(head_int, 101), print_int);
/* Print last node of 400 - should still print 1099 */
node = node_get(head_int, list_count(head_int)-1);
node_print(node, print_int);
printf("\nint list: insert 100 nodes before all other nodes, with values 4000-4099, calling 'node_add_size()':\n");
printf("---------------------------------------------------------------------------------------------------\n");
for (i = 0; i < 100; ++i)
{
int data = i + 4000;
/* Error handling */
if ((rc = node_add_size(&head_int, &data, sizeof(data), i)) == ERROR)
{
fprintf(stderr, "ERROR: node_add_size(): couldn't add node at index %d\n", i);
break;
}
}
printf("node count [330]: %d\n", list_count(head_int));
printf("The 'node_int' list, node 0 [data=0]: "); node_print(node_get(head_int, 0), print_int);
printf("The 'node_int' list, node 1 [data=1]: "); node_print(node_get(head_int, 1), print_int);
printf("The 'node_int' list, node 2 [data=2]: "); node_print(node_get(head_int, 2), print_int);
/* Delete single nodes */
{
int index = 1;
printf("\nint list: delete node %d calling node_del():\n", index);
printf("----------------------------------------------------------------------------------------------------------------------\n");
printf("0 deleted nodes:\n");
node = node_get(head_int, 0); printf("node 0: "); node_print(node, print_int);
node = node_get(head_int, 1); printf("node 1: "); node_print(node, print_int);
node = node_get(head_int, 2); printf("node 2: "); node_print(node, print_int);
if ((rc = node_del(&head_int, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_del(): couldn't delete 'int' node at index %d\n", index);
}
printf("1 deleted node:\n");
node = node_get(head_int, 0); printf("node 0: "); node_print(node, print_int);
node = node_get(head_int, 1); printf("node 1: "); node_print(node, print_int);
node = node_get(head_int, 2); printf("node 2: "); node_print(node, print_int);
index = 0;
printf("\nint list: delete node %d (head node) calling node_del():\n", index);
printf("----------------------------------------------------------------------------------------------------------------------\n");
if ((rc = node_del(&head_int, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_del(): couldn't delete 'int' node at index %d\n", index);
}
printf("2 deleted nodes:\n");
node = node_get(head_int, 0); printf("node 0: "); node_print(node, print_int);
node = node_get(head_int, 1); printf("node 1: "); node_print(node, print_int);
node = node_get(head_int, 2); printf("node 2: "); node_print(node, print_int);
}
printf("node count [328]: %d\n", list_count(head_int));
/* Modify existing nodes */
{
int index = 0;
printf("\nint list: modify nodes calling node_set():\n");
printf("----------------------------------------------------------------------------------------------------------------------\n");
for (index = 0; index <= 2; index++)
{
const int set_data = 8 - index;
if ((rc = node_set(&head_int, set_int, &set_data, NULL, 6 + index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set(): couldn't set 'int' node, index %d\n", index);
}
}
for (index = 20; index <= 22; index++)
{
int set_data = 7;
if ((rc = node_set(&head_int, set_int, &set_data, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set(): couldn't set 'int' node, index %d\n", index);
}
}
}
node = node_get(head_int, 0); printf("node 0: "); node_print(node, print_int);
node = node_get(head_int, 1); printf("node 1: "); node_print(node, print_int);
node = node_get(head_int, 2); printf("node 2: "); node_print(node, print_int);
printf("node count [328]: %d\n", list_count(head_int));
/* Delete nodes using list_del_matching(), matching a criteria defined in a callback */
{
printf("\nint list: delete all nodes outside the range 6-8 (defined in the 'match_int_6_8' callback), calling list_del_matching():\n");
printf("-----------------------------------------------------------------------------------------------------------------\n");
printf("Node count before list_del_matching() [328]: %d\n", list_count(head_int));
if ((rc = list_del_matching(&head_int, match_int_6_8, NULL, NULL)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_matching() failed when deleting 'int' node\n");
}
printf("Node count after list_del_matching() [9]: %d\n", list_count(head_int));
}
/* Delete duplicate nodes using list_del_dup(), matching a criteria defined in a callback */
{
/* Delete node 2 before testing list_del_dup() */
if ((rc = node_del(&head_int, NULL, 2)) == ERROR)
{
fprintf(stderr, "ERROR: node_del(): couldn't delete 'int' node at index 2\n");
}
printf("\nint list: delete all duplicated nodes:\n");
printf("-----------------------------------------------------------------------------------------------------\n");
/* To detect a duplicate node, use a 'cmp_*' callback to compare data. */
/* To delete the node data, an optional 'del_*' callback may be used. */
printf("\nAll int nodes before list_del_dup() [9]: %d\n", list_count(head_int));
printf("---------------------------------------------------------------------------------------\n");
node = head_int; i = 0;
while (node)
{
printf("Node %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
printf("---------------------------------------------------------------------------------------\n");
if ((rc = list_del_dup(&head_int, cmp_int, NULL)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_dup() failed when deleting 'int' node\n");
}
printf("\nAll int nodes after list_del_dup() [3]: %d\n", list_count(head_int));
printf("---------------------------------------------------------------------------------------\n");
node = head_int; i = 0;
while (node)
{
printf("Node %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
printf("---------------------------------------------------------------------------------------\n");
}
/* Results: Get a subset of a list, without modifying the original list. */
printf("\nint list results:\n");
printf("--------------------------------------------------------------------------------\n");
printf("create 100 nodes with values 0-99 calling 'node_append()', print first 10 nodes:\n");
printf("--------------------------------------------------------------------------------\n");
/* Delete any existing nodes and create 100 nodes with the value 0-99 */
list_del(&head_int, NULL);
head_int = NULL;
for (i = 0; i < 100; ++i)
{
/* Error handling */
if ((rc = node_append(&head_int, &i, add_int)) == ERROR)
{
fprintf(stderr, "ERROR: node_append(): couldn't append 'int' node, index %d\n", i);
break;
}
}
node = head_int;
i = 0;
while (i < 10)
{
printf("Orig nodes %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
{
/* Call list_copy_range() to get node 5-10 into a new result list */
/* result_range_int has to be free():d using list_del() */
result_range_int = list_copy_range(head_int, 5, 10, copy_int, NULL);
printf("-------------------------------------------------------------------------------------\n");
printf("Call 'list_copy_range(5,10)'. Result nodes are copies, not pointing to original nodes:\n");
printf("-------------------------------------------------------------------------------------\n");
node = result_range_int; i = 0;
/* If an error occurred, result_range_int and node are NULL, and nothing will be printed. */
while (node)
{
printf("Result nodes %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
}
{
int match_data = 80;
/* Call list_copy_matching() to get matching nodes into the result */
list_del(&result_range_int, NULL);
result_range_int = list_copy_matching(head_int, match_int_gt, &match_data, copy_int, NULL);
printf("-------------------------------------------------------------------------------------\n");
printf("Call 'list_match(> 80)'. Result nodes are copies, not pointing to original nodes:\n");
printf("-------------------------------------------------------------------------------------\n");
node = result_range_int; i = 0;
while (node)
{
printf("Result nodes %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
printf("---------------------------------------------------------------------------------------\n");
}
/* Reduce the original list from 100 to 20 nodes */
if ((rc = list_del_from(&head_int, NULL, 20)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_from() failed!\n");
}
{
const int set_data = 42;
/* Call list_set_range() to set new value (42) for a range of nodes (5-10) */
list_set_range(&head_int, set_int, &set_data, NULL, 5, 10);
printf("-------------------------------------------------------------------------------------\n");
printf("Call 'list_set_range(42, 5, 10)':\n");
printf("-------------------------------------------------------------------------------------\n");
node = head_int; i = 0;
/* If an error occurred, result_range_int and node are NULL, and nothing will be printed. */
while (node)
{
printf("Original %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
}
{
/* Call list_set_matching() to set new values (current node value + 1000) for odd node values */
const int sum_data = 1000;
const int match_data = MATCH_ODD;
list_set_matching(&head_int, sum_int, &sum_data, NULL, match_int_odd_or_even, &match_data);
printf("-------------------------------------------------------------------------------------\n");
printf("Call 'list_set_matching(+1000, MATCH_ODD)':\n");
printf("-------------------------------------------------------------------------------------\n");
node = head_int; i = 0;
/* If an error occurred, result_range_int and node are NULL, and nothing will be printed. */
while (node)
{
printf("Original %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
}
printf("\nint list: set all nodes to value 3, calling 'node_set_size()':\n");
printf("---------------------------------------------------------------------------------------------------\n");
for (i = 0; i < list_count(head_int); ++i)
{
/* Create some "unordered" data */
int data = 30-i;
if (i > 8) data = i - data;
if ((rc = node_set_size(&head_int, &data, sizeof(data), i)) == ERROR)
{
fprintf(stderr, "ERROR: node_set_size(): couldn't set value to %d for node at index %d\n", data, i);
break;
}
}
node = head_int; i = 0;
while (node)
{
printf("Original %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
/* Reverse list - no callback needed */
if ((rc = list_rev(&head_int)) == ERROR)
{
fprintf(stderr, "ERROR: list_rev() failed: couldn't reverse int list\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d (reversed): %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
/* Sort list (insertion sort), descending */
if ((rc = list_sort(&head_int, list_isort, cmp_int, SORT_DESC)) == ERROR)
{
fprintf(stderr, "ERROR: list_isort() failed: couldn't sort int list (insertion sort, desc)\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d (isort, descending): %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
/* Sort list again, using quicksort, ascending */
if ((rc = list_sort(&head_int, list_qsort, cmp_int, SORT_ASC)) == ERROR)
{
fprintf(stderr, "ERROR: list_qsort() failed: couldn't sort int list (quick sort, asc)\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d (qsort): %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
{
/* Copy 3 int nodes to an array of 3 separate nodes. */
int existing_node_indices[3] = {5, 8, 12};
for (i = 0; i <=2; i++)
{
int j = existing_node_indices[i];
if ((node_int_copy[i] = node_copy(head_int, j, copy_int)) == NULL)
{
fprintf(stderr, "ERROR: node_copy() failed: couldn't copy existing node %d\n", j);
break;
}
}
head_int_copy = NULL;
/* Prepend each node in array onto list */
for (i = 0; i <=2; i++)
{
if ((rc = node_prependp(&head_int_copy, node_int_copy[i])) == ERROR)
{
fprintf(stderr, "ERROR: node_prependp() failed: couldn't prepend existing node %d\n", i);
break;
}
}
node = head_int_copy; i = 0;
while (node)
{
printf("Copy and prepend existing %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
/* Reset list and append (instead of prepend) each node in array to list */
/* Note that the allocated memory is associated to the "node array", not to the list.
As we want to "reuse" the "node array", list_del() should NOT be called at this point. */
head_int_copy = NULL;
for (i = 0; i <=2; i++)
{
if ((rc = node_appendp(&head_int_copy, node_int_copy[i])) == ERROR)
{
fprintf(stderr, "ERROR: node_appendp() failed: couldn't append existing node %d\n", i);
break;
}
}
node = head_int_copy; i = 0;
while (node)
{
printf("Copy and append existing %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
/* Resetlist and insert (instead of prepend/append) each node in array to list at a given index */
/* Note that the allocated memory is associated to the "node array", not to the list.
As we want to "reuse" the "node array", list_del() should NOT be called at this point. */
head_int_copy = NULL;
for (i = 0; i <=2; i++)
{
int list_index = 0;
if (i == 2) list_index = -2;
if ((rc = node_insertp(&head_int_copy, node_int_copy[i], list_index)) == ERROR)
{
fprintf(stderr, "ERROR: node_insertp() failed: couldn't insert existing node %d at list index %d\n", i, list_index);
break;
}
}
node = head_int_copy; i = 0;
while (node)
{
printf("Copy and insert existing %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
}
/* Before splitting the list, assign sequential numbers using node_set() */
{
/* First set node values */
int index = 0;
for (index = 0; index < list_count(head_int); index++)
{
int set_data = index;
if ((rc = node_set(&head_int, set_int, &set_data, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set() before node_swap(): couldn't set 'int' node, index %d\n", index);
}
}
}
/* Split the list */
head_int_split = list_split(&head_int, list_count(head_int)/2);
node = head_int; i = 0;
while (node)
{
printf("Split list 1 %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
node = head_int_split; i = 0;
while (node)
{
printf("Split list 2 %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
/* Move nodes: */
/* Move a node within the original int list */
node = head_int; i = 0;
while (node)
{
printf("Original %d BEFORE move within list: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 2) ? " <-----" : "");
node = node->next;
}
if ((rc = node_move(&head_int, NULL, 2, 5)) == ERROR)
{
fprintf(stderr, "ERROR: node_move() failed: couldn't move node from list1(2) to list1(5)\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d AFTER move within list: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 2) ? " <-----" : "");
node = node->next;
}
/* Move a node from the original to the "target list", created by the split */
/* First delete some nodes on the "target list" */
if ((rc = list_del_from(&head_int_split, NULL, 7)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_from() failed: couldn't delete nodes starting from node 2\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d BEFORE move between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 6) ? " <-----" : "");
node = node->next;
}
node = head_int_split; i = 0;
while (node)
{
printf("Target %d BEFORE move between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 6) ? " <-----" : "");
node = node->next;
}
if ((rc = node_move(&head_int, &head_int_split, 6, 2)) == ERROR)
{
fprintf(stderr, "ERROR: node_move() failed: couldn't move node from list1(2) to list2(5)\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d AFTER move between lists: %p next=%p data=%d\n",
i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
node = head_int_split; i = 0;
while (node)
{
printf("Target %d AFTER move between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 6) ? " <-----" : "");
node = node->next;
}
/* Swap nodes */
{
/* First set node values for original list */
int index = 0;
for (index = 0; index < list_count(head_int); index++)
{
int set_data = index;
if ((rc = node_set(&head_int, set_int, &set_data, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set() before node_swap(): couldn't set 'int' node, index %d\n", index);
}
}
}
{
node = head_int; i = 0;
while (node)
{
printf("Original %d BEFORE swap within list: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(((*(int *)node->data == 2) || (*(int *)node->data == 5)) ? " <-----" : ""));
node = node->next;
}
/* Swap two nodes within the same (original) int list */
/* if ((rc = node_swap(&head_int, NULL, 2, 5)) == ERROR) */
if ((rc = node_swap(&head_int, NULL, 5, 2)) == ERROR)
{
fprintf(stderr, "ERROR: node_swap() failed: couldn't swap nodes list1(2) and list1(5)\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d AFTER swap within list: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(((*(int *)node->data == 2) || (*(int *)node->data == 5)) ? " <-----" : ""));
node = node->next;
}
/* Swap two nodes, one from the original, and one from the "split" list */
{
/* First set node values for both lists */
int index = 0;
for (index = 0; index < list_count(head_int); index++)
{
int set_data = index;
if ((rc = node_set(&head_int, set_int, &set_data, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set() before node_swap(): couldn't set 'int' node, index %d\n", index);
}
}
index = 0;
for (index = 0; index < list_count(head_int_split); index++)
{
int set_data = index;
if ((rc = node_set(&head_int_split, set_int, &set_data, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set() before node_swap(): couldn't set 'int_split' node, index %d\n", index);
}
}
node = head_int; i = 0;
while (node)
{
printf("Original %d BEFORE swap between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 2) ? " <-----" : "");
node = node->next;
}
/* Set node values for target to easier distinguish values */
index = 0;
for (index = 0; index < list_count(head_int_split); index++)
{
int set_data = index + 10;
if ((rc = node_set(&head_int_split, set_int, &set_data, NULL, index)) == ERROR)
{
fprintf(stderr, "ERROR: node_set() before node_swap(): couldn't set 'int_split' node, index %d\n", index);
}
}
node = head_int_split; i = 0;
while (node)
{
printf("Target %d BEFORE swap between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 15) ? " <-----" : "");
node = node->next;
}
if ((rc = node_swap(&head_int, &head_int_split, 2, 5)) == ERROR)
{
fprintf(stderr, "ERROR: node_swap() failed: couldn't swap nodes list1(2) and list2(5)\n");
}
node = head_int; i = 0;
while (node)
{
printf("Original %d AFTER swap between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 15) ? " <-----" : "");
node = node->next;
}
node = head_int_split; i = 0;
while (node)
{
printf("Target %d AFTER swap between lists: %p next=%p data=%d%s\n",
i++, (void *)node, (void *)node->next, *(int *)node->data,
(*(int *)node->data == 2) ? " <-----" : "");
node = node->next;
}
}
}
{
/*
node_map():
Pass a callback function ('map_int' in this example) which should be applied on each node of a list, return the result as a new list.
Depending on the callback, the resulting list may filter out node(s), so list_count() for the original and the resulting lists may differ.
The original list is not modified.
*/
int map_data = 3;
result_map_int = list_map(head_int, map_int_sum, &map_data, add_int, NULL);
if (result_map_int == NULL)
{
fprintf(stderr, "ERROR: list_map(): couldn't get mapped list\n");
}
printf("-------------------------------------------------------------------------------------\n");
printf("Call 'list_map(+=3)'. Result nodes are copies, not pointing to original nodes:\n");
printf("-------------------------------------------------------------------------------------\n");
node = result_map_int; i = 0;
while (node)
{
printf("list_map() result nodes %d: %p next=%p data=%d\n", i++, (void *)node, (void *)node->next, *(int *)node->data); node = node->next;
}
printf("---------------------------------------------------------------------------------------\n");
printf("print result_map_int (first node) with node_print():\n");
node = result_map_int;
node_print(node, print_int);
printf("---------------------------------------------------------------------------------------\n");
/* printf("print result_map_int (first node) with node_printf():\n"); */
/* node = result_map_int; */
/* node_printf(node, print_int, ""); */
printf("---------------------------------------------------------------------------------------\n");
printf("print result_map_int (entire list) list_print():\n");
node = result_map_int;
list_print(node, print_int);
printf("---------------------------------------------------------------------------------------\n");
}
/* Char * list */
printf("\n\n---------------------------------------------------------------------------------------\n");
printf("char * list:\n");
printf("---------------------------------------------------------------------------------------\n");
node = node_string;
for (i = 0; i < 100; ++i)
{
/* Error handling */
if ((rc = node_append(&node_string, &i, add_string_from_int)) == ERROR)
{
fprintf(stderr, "ERROR: node_append(): couldn't append 'char *' node, index %d\n", i);
break;
}
if (i == 0) head_string = node_string;
}
/* Print node 42 of 100 - should print '42' */
node = node_get(head_string, 42);
node_print(node, print_string);
/* Delete some "string nodes". Note that the 'del_func' callback is not needed for simple types such as 'char*' */
/* if ((rc = list_del_to(&head_string, del_string, 40)) == ERROR) */
if ((rc = list_del_to(&head_string, NULL, 40)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_to(): couldn't delete 'char *' nodes, 0-40\n");
}
/* if ((rc = list_del_from(&head_string, del_string, 10)) == ERROR) */
if ((rc = list_del_from(&head_string, NULL, 10)) == ERROR)
{
fprintf(stderr, "ERROR: list_del_from(): couldn't delete 'char *' nodes, 10-60\n");
}
node = head_string; i = 0;
printf("head_string: list_count=%d\n", list_count(head_string));
while (node)
{
printf("string list after list_del_to() and list_del_from(): %d %p next=%p data='%s'\n",
i++, (void *)node, (void *)node->next, (char *)node->data);
node = node->next;
}
{
/* Prepend the text 'NODE ' each node. */
/* Append the text ' this is'. */
/* Insert the text '###'. */
/* Replace '###' with '!!!'. */
const char *set_data_prepend = "NODE ";
const char *set_data_append = " this is";
const char *set_data_insert = "###";
int set_data_insert_index = strlen(set_data_prepend);
const char *set_data_replace = "###";
const char *set_data_replace_regex = "/#/!/g";
list_set(&head_string, set_string_prepend, &set_data_prepend, NULL);
list_set(&head_string, set_string_append, &set_data_append, NULL);
list_set(&head_string, set_string_insert_at, &set_data_insert, &set_data_insert_index);
list_set(&head_string, set_string_regex_replace, &set_data_insert, &set_data_insert_index);
node = head_string; i = 0;
while (node)
{
printf("string list after list_set(): %d %p next=%p data='%s'\n",
i++, (void *)node, (void *)node->next, (char *)node->data);
node = node->next;
}
}
printf("---------------------------------------------------------------------------------------\n\n");
printf("\nstruct list:\n");
printf("---------------------------------------------------------------------------------------\n");
/* node = node_struct; */
for (i = 0; i < 100; ++i)
{
if ((rc = node_append(&node_struct, &i, add_struct)) == ERROR)
{
fprintf(stderr, "ERROR: node_append(): couldn't append 'struct' node, index %d\n", i);
break;
}
if (i == 0) head_struct = node_struct;
}
/* Print node 42 of 100 - should print 'This is title 42' */
node = node_get(head_struct, 42);
node_print(node, print_struct);
printf("\ndouble[] list:\n");
printf("---------------------------------------------------------------------------------------\n");
node = node_double_arr;
for (i = 0; i < 100; ++i)
{
if ((rc = node_append(&node_double_arr, &i, add_double_arr)) == ERROR)
{
fprintf(stderr, "ERROR: node_append(): couldn't append 'double[]' node, index %d\n", i);
break;
}
if (i ==0) head_double_arr = node_double_arr;
}
/* Print node 42 - should print "node42->data= {42.0, 97.0, 33.0, 31.0, 96.0, 30.0, 36.0, 92.0}" */
node = node_get(head_double_arr, 42);
node_print(node, print_double_arr);
/*
Delete all lists.
No additional de-allocation is needed for simple types like int and char *,
so no callback for free():ing data is used in these cases.
Callbacks are only needed when the node data type is a struct where
struct member(s) have allocated additionally memory.
*/
list_del(&head_int, NULL);
list_del(&head_int_copy, NULL);
list_del(&result_range_int, NULL);
list_del(&head_int_split, NULL);
list_del(&result_map_int, NULL);
list_del(&head_string, NULL);
list_del(&head_struct, del_struct);
list_del(&head_double_arr, del_double_arr);
printf("\nTIP: MEMLEAK CHECK:\n");
printf("valgrind -v --track-origins=yes --leak-check=full --show-leak-kinds=all %s\n", argv[0]);
(void)argc;
printf("----------------------------------------\n");
return rc;
}