Advertisement
drankinatty

Doubly Linked Circular Linked List w/Pointer to Payload

Apr 14th, 2017
299
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 18.15 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAXLISTS 64
  6.  
  7. typedef struct llist {  /* list structure   */
  8.     void *data;
  9.     struct llist *prev, *next;
  10. } llist;
  11.  
  12. typedef struct {    /* payload structure    */
  13.     size_t n;
  14.     size_t len;
  15.     char *s;
  16. } payld;
  17.  
  18. unsigned long llsize[MAXLISTS] = {0};       /* array for lists size     */
  19. /* NOTE: llsize[0] used for example below.
  20.  * for implementaion, you need to pass the
  21.  * list number or list size as an argument
  22.  * to properly implement the use of a
  23.  * global for tracking list size. It is
  24.  * a great efficiency improvemnt to not
  25.  * iterate over every node to get the list
  26.  * size each time it is required. Change to
  27.  * dynamic array and pass list count index
  28.  * as an argument. Otherwise see the separate
  29.  * stuct implementaion containing list object
  30.  * and additional list params: count, sizeof
  31.  */
  32.  
  33. /* list funciton prototypes */
  34. llist *createlist ();                       /* create/insert/read file  */
  35. llist *create_node (void *data);
  36. llist *insert_node (llist **list, void *data);
  37. llist *read_file2list (llist **list, char *fname);
  38.  
  39. void free_node (llist *node);               /* delete node/delete list  */
  40. void delete_list (llist **list);
  41. void delete_node_fwd (llist **list, unsigned long num);
  42. void delete_node (llist **list, unsigned long num);
  43.  
  44. unsigned long getszlist (llist *list);      /* get number of list nodes */
  45.  
  46. /* iteration fwd/rev that take function pointer
  47.    to define the function operation and output */
  48. void iterfnfwd (void fnc (llist *list), llist *list);
  49. void iterfnrev (void fnc (llist *list), llist *list);
  50.  
  51. /* iteration fwd/rev that take function pointer
  52.    and pointer to integer value to define the
  53.    function operation and output and returns a
  54.    pointer to a node and updates the value at i
  55.    to its new value */
  56. void *iterfnfwdvi (void* fnc (llist*, unsigned long*), llist *list, unsigned long *n);
  57. void *iterfnrevvi (void* fnc (llist*, unsigned long*), llist *list, unsigned long *n);
  58. void *getfnfwdvi (void* fnc (llist*, unsigned long*), llist *list, unsigned long *n);
  59.  
  60. /* functions to pass to list iterators */
  61. /* void iterfn prototypes              */
  62. void itf_printnode (llist *node);           /* print nodes by func ptr  */
  63.  
  64. /* functions to pass to list iterators */
  65. /* void* iterfn prototypes with int *n */
  66. void *itf_printnodev (llist *node, unsigned long *n);
  67. void *itf_getszv (llist *node, unsigned long *n);
  68. void *itf_getnodev (llist *node, unsigned long *n);
  69. void *itf_getdata (llist *node, unsigned long *n);
  70. void *itf_srchlen (llist *node, unsigned long *n);
  71.  
  72. /* general functions */
  73. void chkhelp (char **a, const char *opts);
  74.  
  75. /* test program - reads all lines in file
  76.    given as first argument or from stdin */
  77. int main (int argc, char **argv) {
  78.  
  79.     char *fn = NULL;
  80.     llist *ll = NULL;
  81.     unsigned long i = 0;
  82.  
  83.     if (argc > 1) {             /* check for -h or --help and show usage    */
  84.         chkhelp (argv, "[filename (stdin)] to read file or stdin into list");
  85.         fn = argv[1];
  86.     }
  87.  
  88.     read_file2list (&ll, fn);   /* read lines from file (or stdin) into list */
  89.     if (!getszlist (ll)) {
  90.         fprintf (stderr, "error: insufficient input.  usage: %s [filename (stdin)]\n",
  91.                 argv[0]);
  92.         return 1;
  93.     }
  94.  
  95.     /* printf the list forward */
  96.     printf ("\n linked list read from '%s'\n\n", fn ? fn : "stdin");
  97.     iterfnfwd (itf_printnode, ll);
  98.  
  99.     i = 0;  /* get the number of nodes in list through funciton pointer */
  100.     printf ("\n list size: %lu  (by void *funciton pointer return)\n",
  101.             *(unsigned long *)iterfnfwdvi (itf_getszv, ll, &i));
  102.     /* get the number of nodes in list through global */
  103.     printf (" list size: %lu  (by llsize)\n\n", llsize[0]);
  104.  
  105.     /* printf the list in reverse */
  106.     printf (" iterating the file in reverse:\n\n");
  107.     iterfnrev (itf_printnode, ll);  // iterate with funciton pointer
  108.  
  109.     /* find node 10 (11th node in list) */
  110.     printf ("\n selecting node 10 (11th in list -- zero based):\n\n");
  111.     i = 10;
  112.     payld *pt = getfnfwdvi (itf_getdata, ll, &i);
  113.     if (pt)
  114.         printf (" %2zu - [%3zu]  %s  ( node %lu -- cast to payld*)\n\n", pt->n, pt->len, pt->s, i);
  115.  
  116.     i = 20; /* find all (nodes) holding strings >= 20 chars */
  117.     printf (" searching list for strings >= %lu chars:\n\n", i);
  118.     iterfnfwdvi (itf_srchlen, ll, &i);  // iterate with funciton pointer
  119.     printf ("\n '%lu' rows >= 20 chars\n\n", i);
  120.  
  121.     /* delete the first two nodes in list (original list address) */
  122.     printf (" deleting nodes 1, 2  -  (indexes 0,1)\n\n");
  123.     delete_node (&ll, 0);
  124.     delete_node (&ll, 0);
  125.  
  126.     /* confirm size reduction with both iteration and global */
  127.     printf (" list size: %lu\n", getszlist (ll));
  128.     printf (" list size: %lu  (by llsize)\n\n", llsize[0]);
  129.  
  130.     i = 20; /* find all (nodes) holding strings >= 20 chars */
  131.     printf (" searching list for strings >= %lu chars:\n\n", i);
  132.     iterfnfwdvi (itf_srchlen, ll, &i);  // iterate with funciton pointer
  133.     printf ("\n '%lu' rows >= 20 chars\n\n", i);
  134.  
  135.     /* delete the first two nodes in list (original list address) */
  136.     printf (" deleting node 12  -  (original index 14)\n\n");
  137.     delete_node (&ll, 12);
  138.  
  139.     i = 20; /* find all (nodes) holding strings >= 20 chars */
  140.     printf (" searching list for strings >= %lu chars:\n\n", i);
  141.     iterfnfwdvi (itf_srchlen, ll, &i);  // iterate with funciton pointer
  142.     printf ("\n '%lu' rows >= 20 chars\n\n", i);
  143.  
  144.     printf (" deleting all nodes in list\n");
  145.     delete_list (&ll);
  146.  
  147.     /* confirm size reduction with both iteration and global */
  148.     printf ("\n list size: %lu\n", getszlist (ll));
  149.     printf (" list size: %lu  (by llsize)\n\n", llsize[0]);
  150.  
  151.     return 0;
  152. }
  153.  
  154. /* allocate & copy data to node
  155.    NOTE: function requires custimization based
  156.    on the struct definition of payld */
  157. llist *create_node (void *data)
  158. {
  159.     llist *node = NULL;
  160.  
  161.     node = malloc (sizeof *node);
  162.     node-> data = malloc (sizeof (payld));
  163.  
  164.     if (!node || !node-> data) return NULL;
  165.  
  166.     if (data) {
  167.         memcpy (node->data, data, sizeof (payld));
  168.         payld *p = (payld *) data;
  169.         payld *np = (payld *) node->data;
  170.         if (!(np->s = strdup (p-> s))) {
  171. #ifdef DEBUG
  172.             fprintf (stderr, "%s() error: payload allocation failed.\n",
  173.                     __func__);
  174. #endif
  175.             free_node (node);
  176.             return NULL;
  177.         }
  178.     }
  179.  
  180.     return node;
  181. }
  182.  
  183. /* insert node into list */
  184. llist *insert_node (llist **list, void *data)
  185. {
  186.     llist *node = NULL;
  187.     if (!(node = create_node (data))) return NULL;
  188.  
  189.  
  190.     if (!*list) {                       /* if empty, create first node  */
  191.     node-> next = node;
  192.     node-> prev = node;
  193.         *list = node;                   /* insert as new first node     */
  194.     } else {
  195.         if (*list == (*list)-> next) {  /* list only contains 1 node    */
  196.             (*list)-> next = node;      /* insert as next node          */
  197.             node-> prev = *list;
  198.         }
  199.         else
  200.         {
  201.             (*list)->prev->next = node; /* cir list, just ins as last   */
  202.             node->prev = (*list)->prev; /* no need to iterate to end    */
  203.         }
  204.         node-> next = *list;            /* circular - next is first     */
  205.         (*list)-> prev = node;          /* list->prev is node           */
  206.     }
  207.  
  208.     return *list;                       /* return list */
  209. }
  210.  
  211. /* read list from file fname and add to list
  212.    NOTE: function requires custimization based
  213.    on the struct definition of payld */
  214. llist *read_file2list (llist **list, char *fname)
  215. {
  216.     FILE *fp = NULL;
  217.     if (fname) {
  218.         if (!(fp = fopen (fname, "r"))) {
  219.             fprintf (stderr, "%s() error: file open failed for '%s'\n",
  220.                     __func__, fname);
  221.             return NULL;
  222.         }
  223.     }
  224.     else
  225.         fp = stdin;
  226.  
  227.     /* allocate and initialize all variables */
  228.     char *ln = NULL;            /* NULL forces getline to allocate  */
  229.     size_t n = 0;               /* ln size (0 - getline chooses)    */
  230.     size_t idx = 0;             /* line number index                */
  231.     ssize_t nchr = 0;           /* number of chars actually read    */
  232.  
  233.     while ((nchr = getline (&ln, &n, fp)) != -1)    /* read file    */
  234.     {
  235.         while (nchr > 0 && (ln[nchr-1] == '\n' || ln[nchr-1] == '\r'))
  236.             ln[--nchr] = 0;     /* strip newline or carriage rtn    */
  237.  
  238.         payld pld = { 0, 0, NULL }; /* static initialization struct */
  239.  
  240.         pld.n = idx;
  241.         pld.len = nchr;
  242.         pld.s = ln;
  243.         insert_node (list, &pld);           /* add node to list     */
  244.         idx++;
  245.         llsize[0] += 1;
  246.     }
  247.  
  248.     if (fp != stdin) fclose (fp);           /* close file/free line */
  249.     if (ln) free (ln);
  250.  
  251.     return *list;
  252. }
  253.  
  254. /* free dynamically allocated payload, then node */
  255. void free_node (llist *node)
  256. {
  257.     if (!node) return;
  258.  
  259.     if (node-> data) {
  260.         payld *p = (payld *)node-> data;
  261.         if (p-> s)
  262.             free (p-> s);
  263.         free (node-> data);
  264.     }
  265.  
  266.     free (node);
  267. }
  268.  
  269. /* free memory for all nodes in list */
  270. void delete_list (llist **list)
  271. {
  272.     llist *iter = (*list)-> next;
  273.     llist *np = NULL;
  274.     while (iter != *list)
  275.     {
  276.         np = iter-> next;
  277.         if (iter) free_node (iter);
  278.         iter = np;
  279.     }
  280.     if (iter) free_node (iter);
  281.     *list = NULL;
  282.     if (llsize[0]) llsize[0] = 0;
  283. }
  284.  
  285. /* free memory for specific node (zero based) */
  286. void delete_node_fwd (llist **list, unsigned long node)
  287. {
  288.     /* validate list exists */
  289.     if (!*list) {
  290.     fprintf (stderr, "%s(), The list is empty\n",__func__);
  291.     return;
  292.     }
  293.  
  294.     /* get size of list */
  295.     unsigned long szlist = getszlist (*list);
  296.  
  297.     /* test node < szlist */
  298.     if (node >= szlist) {
  299.     fprintf (stderr, "%s() error: record to delete is out of range (%lu)\n",
  300.                 __func__, node);
  301.     return;
  302.     }
  303.  
  304.     /* find the node'th node    */
  305.     while (node--)
  306.     list = &(*list)->next;
  307.  
  308.     /* create pointer to node to delete */
  309.     llist *victim = *list;
  310.  
  311.     /* for non-self-referenced nodes - just rewire pointers     */
  312.     if (victim != victim->next) {
  313.     (victim->prev)->next = victim->next;
  314.     (victim->next)->prev = victim->prev;
  315.     *list = victim->next;
  316.     } else {      /* deleted node self-referenced - last node   */
  317.     *list = NULL;
  318.     }
  319.  
  320.     if (llsize[0]) llsize[0]-= 1;   /* maintian global count    */
  321.  
  322.     /* free node memory    */
  323.     free_node (victim);
  324. }
  325.  
  326. /* free memory for specific node (zero based)
  327.    (balanced search in only 1/2 list w/node) */
  328. void delete_node (llist **list, unsigned long node)
  329. {
  330.  
  331.     /* validate list exists */
  332.     if (!*list) {
  333.     fprintf (stderr, "%s()  list is empty\n", __func__);
  334.     return;
  335.     }
  336.  
  337.     /* get size of list */
  338.     // int szlist = getszlist (*list);
  339.     unsigned long szlist = llsize[0];
  340.  
  341.     /* test node < szlist */
  342.     if (node >= szlist) {
  343.     fprintf (stderr, "%s() error: record to delete is out of range (%lu)\n",
  344.                 __func__, node);
  345.     return;
  346.     }
  347.  
  348.     /* find the node'th node with balanced search
  349.        search fwd for 0->szlist/2, rev end->szlist/2 */
  350.     if (node != 0  && node >= szlist/2) {
  351.     while (szlist - node++)
  352.         list = &(*list)->prev;
  353.  
  354.     list = &(*list)->prev; /* hack to get correctly bracket ptr before */
  355.     list = &(*list)->next; /* delete when traversing list in reverse   */
  356.     } else
  357.     while (node--)
  358.         list = &(*list)->next;
  359.  
  360.     /* create pointer to node to delete */
  361.     llist *victim = *list;
  362.  
  363.     /* for non-self-referenced nodes - just rewire pointers     */
  364.     if (victim != victim->next) {
  365.     (victim->prev)->next = victim->next;
  366.     (victim->next)->prev = victim->prev;
  367.     *list = victim->next;
  368.     } else {      /* deleted node self-referenced - last node   */
  369.     *list = NULL;
  370.     }
  371.  
  372.     if (llsize[0]) llsize[0]-= 1;   /* maintian global count    */
  373.  
  374.     /* free node memory    */
  375.     free_node (victim);
  376. }
  377.  
  378. /* get list info functions */
  379. unsigned long getszlist (llist *list) {
  380.  
  381.     const llist *iter = list;   // second copy to iterate list
  382.     register unsigned long cnt = 0;
  383.  
  384.     if (iter ==  NULL) {
  385. #ifdef DEBUG
  386.     fprintf (stderr, "%s(), The list is empty\n", __func__);
  387. #endif
  388.     return cnt;
  389.     }
  390.  
  391.     for (; iter; iter = (iter->next != list ? iter->next : NULL))
  392.         cnt++;
  393.  
  394.     return cnt;
  395. }
  396.  
  397. /* iteration fwd/rev that take function pointer
  398.    to define the function operation and output */
  399. void iterfnfwd (void fnc (llist *list), llist *list)
  400. {
  401.     if (list ==  NULL) {
  402. #ifdef DEBUG
  403.     fprintf (stderr, "%s()  list is empty\n", __func__);
  404. #endif
  405.     return;
  406.     }
  407.  
  408.     llist *iter = list; /* create pointer to iterate list   */
  409.  
  410.     do
  411.     {
  412.         fnc (iter);
  413.         iter = iter->next;
  414.     } while (iter != list);
  415. }
  416.  
  417. void iterfnrev (void fnc (llist *list), llist *list)
  418. {
  419.     if (list ==  NULL) {
  420. #ifdef DEBUG
  421.     fprintf (stderr, "%s()  list is empty\n", __func__);
  422. #endif
  423.     return;
  424.     }
  425.  
  426.     llist *iter = list-> prev; /* create pointer to last iterate list   */
  427.  
  428.     do
  429.     {
  430.         fnc (iter);
  431.         iter = iter->prev;
  432.     } while (iter != list->prev);
  433. }
  434.  
  435. void *iterfnfwdvi (void *fnc (llist*, unsigned long*), llist *list, unsigned long *n)
  436. {
  437.     if (list ==  NULL) {
  438. #ifdef DEBUG
  439.     fprintf (stderr, "%s()  list is empty\n", __func__);
  440. #endif
  441.     return NULL;
  442.     }
  443.  
  444.     llist *iter = list; /* create pointer to iterate list   */
  445.     void *rtn = NULL;   /* create poiner for fnc return     */
  446.     unsigned long nbegin = *n;
  447.     size_t cnt = 0;
  448.  
  449.     for (; iter; iter = (iter->next != list ? iter->next : NULL))
  450.     {
  451.         if ((rtn = fnc (iter, n))) cnt++;
  452.     }
  453.  
  454.     if (*n == nbegin) *n = cnt;  /* if ptr *n unchanged rtn cnt  */
  455.  
  456.     return rtn;
  457. }
  458.  
  459. void *iterfnrevvi (void *fnc (llist*, unsigned long*), llist *list, unsigned long *n)
  460. {
  461.     if (list ==  NULL) {
  462. #ifdef DEBUG
  463.     fprintf (stderr, "%s()  list is empty\n", __func__);
  464. #endif
  465.     return NULL;
  466.     }
  467.  
  468.     llist *iter = list-> prev;  /* pointer to last to iterate list  */
  469.     void *rtn = NULL;           /* create poiner for fnc return     */
  470.     unsigned long nbegin = *n;
  471.     size_t cnt = 0;
  472.  
  473.     for (; iter; iter = (iter->prev != list->prev ? iter->prev : NULL))
  474.     {
  475.         if ((rtn = fnc (iter, n))) cnt++;
  476.         // rtn = fnc (iter, n);
  477.     }
  478.  
  479.     if (*n == nbegin) *n = cnt;  /* if ptr *n unchanged rtn cnt  */
  480.  
  481.     return rtn;
  482. }
  483.  
  484. /* RENAME: to something reflecting this is balanced search for node 'n' */
  485. void *getfnfwdvi (void *fnc (llist*, unsigned long*), llist *list, unsigned long *n)
  486. {
  487.     if (list ==  NULL) {
  488. #ifdef DEBUG
  489.     fprintf (stderr, "%s()  list is empty\n", __func__);
  490. #endif
  491.     return NULL;
  492.     }
  493.  
  494.     if (*n == 0)        /* request first node, call/return  */
  495.         return fnc (list, n);
  496.  
  497.     /*  need to save global list size to be able to do efficient
  498.         balanced search. If calling getszlist() iterates over
  499.         the list once to get sz, the you save nothing with the
  500.         balance search, you may as well just iterate once to
  501.         find the node in question, unless the fnc code is so
  502.         big a full iter of the list makes sense.
  503.  
  504.         llsize[0] is list size  (maybe use struct?)
  505.     */
  506.  
  507.     // int szlist = getszlist (*list);
  508.     unsigned long szlist = llsize[0];
  509.  
  510.     /* validate node > 0 && < szlist */
  511.     if (*n >= llsize[0]) {
  512. #ifdef DEBUG
  513.     fprintf (stderr, "%s() error: record to delete is out of range (%lu)\n",
  514.                 __func__, *n);
  515. #endif
  516.     return NULL;
  517.     }
  518.  
  519.     llist *iter = list; /* create pointer to iterate list   */
  520.     void *rtn = NULL;   /* create poiner for fnc return     */
  521.     register unsigned long node = *n;
  522.  
  523.     /* find the node'th node with balanced search
  524.        search fwd for 0->szlist/2, rev end->szlist/2 */
  525.     if (*n >= szlist/2) {
  526.         while (szlist - node++)
  527.             iter = iter-> prev;
  528.  
  529.         iter = iter-> prev; /* hack to get correctly bracket ptr before */
  530.         iter = iter-> next; /* delete when traversing list in reverse   */
  531.     }
  532.     else {
  533.         while (node--)
  534.             iter = iter-> next;
  535.     }
  536.  
  537.     rtn = fnc (iter, n);
  538.  
  539.     return rtn;
  540. }
  541.  
  542. /* void print nodes by function pointer */
  543. void itf_printnode (llist *node)
  544. {
  545.     if (!node)
  546.         return;
  547.  
  548.     payld *p = (payld *)node-> data;
  549.  
  550. #ifdef DEBUG
  551.     printf (" %2zu - prev: %p  cur: %p  next: %p\n",
  552.             p->n, node->prev, node, node->next);
  553. #else
  554.     printf (" %2zu - [%3zu]  %s\n", p->n, p->len, p->s);
  555. #endif
  556. }
  557.  
  558. /* void* print nodes by function pointer */
  559. void *itf_printnodev (llist *node, unsigned long *n)
  560. {
  561.     if (!node) return NULL;
  562.     (*n)++;
  563.  
  564.     payld *p = (payld *)node-> data;
  565.  
  566. #ifdef DEBUG
  567.     printf (" %2zu - prev: %p  cur: %p  next: %p\n",
  568.             p->n, node->prev, node, node->next);
  569. #else
  570.     printf (" %2zu - [%3zu]  %s\n", p->n, p->len, p->s);
  571. #endif
  572.     return node;
  573. }
  574.  
  575. /* simple funciton to return list length through n
  576.    while using a funciton pointer with iterator  */
  577. void *itf_getszv (llist *node, unsigned long *n)
  578. {
  579.     if (!node) return NULL;
  580.     (*n)++;
  581.  
  582.     return n;
  583. }
  584.  
  585. void *itf_getnodev (llist *node, unsigned long *n)
  586. {
  587.     if (!node) return NULL;
  588.  
  589.     payld *p = (payld *)node-> data;
  590.     if (p-> n == (size_t)*n) {
  591.         printf ("  %2zu - [%3zu]  %s  ( %s() )\n\n", p->n, p->len, p->s, __func__);
  592.         return p;
  593.     }
  594.     return NULL;
  595. }
  596.  
  597. /* return a pointer to data for node n (zero based) */
  598. void *itf_getdata (llist *node, unsigned long *n)
  599. {
  600.     if (!node) return NULL;
  601.     if (*n ==0) *n = 0; /* prevent unused */
  602.     return node->data;
  603. }
  604.  
  605. /* search list for strings >= n */
  606. void *itf_srchlen (llist *node, unsigned long *n)
  607. {
  608.     if (!node) return NULL;
  609.  
  610.     payld *p = (payld *)node-> data;
  611.  
  612.     if (p-> len >= (size_t)*n) {
  613.         printf (" %2zu - [%3zu]  %s\n", p->n, p->len, p->s);
  614.         return p;
  615.     }
  616.  
  617.     return NULL;
  618. }
  619.  
  620. /* check argv[1] for -h or --help request */
  621. void chkhelp (char **a, const char *opts)
  622. {
  623.     if ((*a[1] == '-' && *(a[1] + 1) == 'h') ||
  624.         (*(a[1] + 1) == '-' && *(a[1] + 2) == 'h'))
  625.     {
  626.         fprintf (stderr, " usage: %s %s\n", a[0], opts);
  627.         exit (0);
  628.     }
  629. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement