SHARE
TWEET

Untitled

a guest Sep 16th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5.  
  6. /***************************************************************************
  7.  * Helper Types
  8.  ***************************************************************************/
  9.  
  10. /* Basic example person data structure. */
  11. typedef struct {
  12.     char *name;
  13.     unsigned int age;
  14. } person_t;
  15.  
  16. /***************************************************************************/
  17.  
  18. /***************************************************************************
  19.  * List Types
  20.  ***************************************************************************/
  21.  
  22. /* Represents a node in a doubly-linked list. */
  23. typedef struct __node_t {
  24.     struct __node_t *prev;
  25.     struct __node_t *next;
  26.     void *data;
  27. } node_t;
  28.  
  29. /***************************************************************************/
  30.  
  31. /***************************************************************************
  32.  * List Functions
  33.  ***************************************************************************/
  34.  
  35. /* Initialises a node in a doubly-linked list, returning a pointer to the node. */
  36. node_t *list_node_init() {
  37.     node_t *node = calloc(1, sizeof(node_t));
  38.     return node;
  39. }
  40.  
  41. /* Get the head of the list. */
  42. node_t *list_get_head(node_t *node) {
  43.     node_t *head = node;
  44.     node_t *prev = head->prev;
  45.     while (prev) {
  46.         head = prev;
  47.         prev = head->prev;
  48.     }
  49.     return head;
  50. }
  51.  
  52. /* Get the tail of the list. */
  53. node_t *list_get_tail(node_t *node) {
  54.     node_t *tail = node;
  55.     node_t *next = tail->next;
  56.     while (next) {
  57.         tail = next;
  58.         next = tail->next;
  59.     }
  60.     return tail;
  61. }
  62.  
  63. /* Free the memory of a node, including its data contents if applicable. */
  64. void list_free_node(node_t *node) {
  65.     if (node->data)
  66.         free(node->data);
  67.     free(node);
  68. }
  69.  
  70. /* Free the memory of an entire list. */
  71. void list_free(node_t *node) {
  72.     node_t *curr = list_get_head(node);
  73.     node_t *next = NULL;
  74.     while (curr) {
  75.         next = curr->next;
  76.         list_free_node(curr);
  77.         curr = next;
  78.     }
  79. }
  80.  
  81. /* Insert a node on to the head of the list. Returns a pointer to the added
  82.  * node.
  83.  */
  84. node_t *list_add_start(node_t *node, node_t *node_add) {
  85.     node_t *head = list_get_head(node);
  86.     assert (head);
  87.     head->prev = node_add;
  88.     node_add->next = head;
  89.     return node_add;
  90. }
  91.  
  92. /* Insert a node on to the tail of the list. Returns a pointer to the added
  93.  * node.
  94.  */
  95. node_t *list_add_end(node_t *node, node_t *node_add) {
  96.     node_t *tail = list_get_tail(node);
  97.     assert (tail);
  98.     tail->next = node_add;
  99.     node_add->prev = tail;
  100.     return node_add;
  101. }
  102.  
  103. /* Insert a node before the specified node. Returns a pointer to the added
  104.  * node.
  105.  */
  106. node_t *list_add_before(node_t *node, node_t *node_add) {
  107.     assert (node && node_add);
  108.     node_t *prev = node->prev;
  109.     if (prev)
  110.         prev->next = node_add;
  111.     node_add->prev = prev;
  112.     node_add->next = node;
  113.     node->prev = node_add;
  114.     return node_add;
  115. }
  116.  
  117. /* Insert a node after the specified node. Returns a pointer to the added
  118.  * node.
  119.  */
  120. node_t *list_add_after(node_t *node, node_t *node_add) {
  121.     assert (node && node_add);
  122.     node_t *next = node->next;
  123.     if (next)
  124.         next->prev = node_add;
  125.     node_add->prev = node;
  126.     node_add->next = next;
  127.     node->next = node_add;
  128.     return node_add;
  129. }
  130.  
  131. /* Find a node in the list with the specified data. Returns a pointer to the
  132.  * node if found, otherwise NULL. */
  133. node_t *list_find(node_t *node, void *data) {
  134.     node_t *curr = list_get_head(node);
  135.     while (curr) {
  136.         if (curr->data == data)
  137.             return curr;
  138.         curr = curr->next;
  139.     }
  140.     return NULL;
  141. }
  142.  
  143. /* Delete a node from the list containing the data. Returns 1 on success,
  144.  * or 0 if not found.
  145.  */
  146. int list_delete(node_t *node, void *data) {
  147.     node_t *curr = list_get_head(node);
  148.     while (curr) {
  149.         if (curr->data) {
  150.             if (curr->data == data) {
  151.                 node_t *next = curr->next;
  152.                 node_t *prev = curr->prev;
  153.                 prev->next = next;
  154.                 next->prev = prev;
  155.                 list_free_node(curr);
  156.                 return 1;
  157.             }
  158.         }
  159.     }
  160.     return 0;
  161. }
  162.  
  163. /***************************************************************************/
  164.  
  165. /***************************************************************************
  166.  * Helper Functions
  167.  ***************************************************************************/
  168.  
  169. /* Iterate the list from the head treating each node as a person, printing its
  170.  * contents.
  171.  */
  172. void print_person_list(node_t *node) {
  173.     node_t *curr = list_get_head(node);
  174.     while (curr) {
  175.         if (curr->data) {
  176.             person_t *person = (person_t *)curr->data;
  177.             printf("name: %s; age: %d\n", person->name, person->age);
  178.         }
  179.         curr = curr->next;
  180.     }
  181. }
  182.  
  183. /* Create a person with a name and age, returning a pointer to the person. */
  184. person_t *create_person(char *name, int age) {
  185.     person_t *person = malloc(sizeof(person_t));
  186.     person->name = name;
  187.     person->age = age;
  188.     return person;
  189. }
  190.  
  191. /* Find a person by name in a list of persons, returning a pointer to the person. */
  192. person_t *find_person(node_t *node, char *name) {
  193.     node_t *curr = list_get_head(node);
  194.     while (curr) {
  195.         person_t *person = (person_t *)curr->data;
  196.         if (strcmp(person->name, name) == 0)
  197.             return person;
  198.         curr = curr->next;
  199.     }
  200.     return NULL;
  201. }
  202.  
  203. /***************************************************************************/
  204.  
  205. /***************************************************************************
  206.  * Test Functions (INCOMPLETE)
  207.  ***************************************************************************/
  208.  
  209. int i = 0;
  210.  
  211. node_t *test_list() {
  212.     node_t *head = list_node_init();
  213.     head->data = create_person("John Meikle", 23);
  214.  
  215.     node_t *node1 = list_node_init();
  216.     node1->data = create_person("Bob Dole", 32);
  217.     list_add_end(head, node1);
  218.  
  219.     node_t *node2 = list_node_init();
  220.     node2->data = create_person("John Smith", 56);
  221.     list_add_end(head, node2);
  222.  
  223.     return head;
  224. }
  225.  
  226. void test_list_node_init() {
  227.     node_t *node = list_node_init();
  228.     assert (node);
  229.     list_free_node(node);
  230. }
  231.  
  232. void test_list_get_head() {
  233.     node_t *head = test_list();
  234.     assert (list_get_head(head) == head);
  235.     list_free(head);
  236. }
  237.  
  238. void test_list_get_tail() {
  239.     node_t *head = test_list();
  240.     // ...
  241.     list_free(head);
  242. }
  243.  
  244. // ...
  245.  
  246. void test_all() {
  247.     test_list_node_init();
  248.     test_list_get_head();
  249.     test_list_get_tail();
  250. }
  251.  
  252. /***************************************************************************/
  253.  
  254. int main(void) {
  255.     node_t *head = list_node_init();
  256.     head->data = create_person("John Meikle", 23);
  257.  
  258.     node_t *node1 = list_node_init();
  259.     node1->data = create_person("Bob Dole", 32);
  260.     list_add_end(head, node1);
  261.  
  262.     node_t *new_head = list_node_init();
  263.     new_head->data = create_person("John Smith", 56);
  264.     list_add_head(head, new_head);
  265.  
  266.     print_person_list(head);
  267.     assert(find_person(head, "John Meikle"));
  268.     list_free(head);
  269.     return 0;
  270. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top