"Doubly Linked-List Using Address of List"

/*
 *  compile with -DPASSPTR2PTR to use add() with address of list.
 *  for: https://stackoverflow.com/a/66997713/3422102
 *
 *  example inut file:
John 12345
Sam 54321
Daivd 1000
Mike 5391
Lion 43222
Phil 8332
Bill 2853
 *
 *  defines:
 *    PASSPTR2PTR - do add by passing address of list
 *    ADDRDELETE  - do delete by passing address of list
 *
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct person{
  char* firstName;
  char* age;
  struct person* previous;
  struct person* next;
}Person;

void print(Person*);

// void reverseList(Person*);

// Person* add (Person*, char*, char*);

void print (Person* list) {
  while(list != NULL) {
    printf("%s %s\n",list->firstName,list->age);
    list = list->next;
  }
}

void prnptrs (Person *list) {
    while (list) {
        printf ("%p  %p  %p\n", (void*)list->previous, (void*)list, (void*)list->next);
        list = list->next;
    }
}
#ifndef PASSPTR2PTR
void reverseList (Person *list) {

  if (!list) {                  /* validate list not empty */
    puts ("(list empty)");
    return;
  }

  while (list->next != NULL)    /* iterte to last node */
    list = list->next;

  while (list) {    /* print in reverse using ->previous pointers */
    printf ("%s %s\n", list->firstName, list->age);
    list = list->previous;
  }
}
#else
void reverseList (Person **list) {

  Person *current = *list;
  Person *last = current;

  if (!current || !current->next)
    return;

  do {
    Person *temp = current->previous;
    current->previous = current->next;
    current->next = temp;
    last = current;
  } while ((current = current->previous));
  *list = last;
}
#endif

Person *createnode (const char *firstName, const char *age)
{
  size_t len;
  Person *node = malloc (sizeof *node);   /* allocate node, use dereference ptr for size */

  if (!node) {                            /* validate EVERY allocation */
    perror ("malloc-node");
    return NULL;
  }
  node->next = node->previous = NULL;     /* initialize next and previous NULL */

  len = strlen (firstName);                         /* get length of firstName */
  if (!(node->firstName = malloc (len + 1))) {      /* allocate/validate */
    perror ("malloc-node->firstName");
    free (node);                                    /* free node before return */
    return NULL;
  }
  memcpy (node->firstName, firstName, len + 1);     /* copy firstName to node */

  len = strlen (age);                               /* get length of age */
  if (!(node->age = malloc (len + 1))) {            /* allocate/validate */
    perror ("malloc-node->age");
    free (node->firstName);                         /* free node->firstName, and */
    free (node);                                    /* free node before return */
    return NULL;
  }
  memcpy (node->age, age, len + 1);                 /* copy age to node */

  return node;
}
#ifdef PASSPTR2PTR
/* add node to list using address of list and pointer to list
 * returns pointer to new node on success, NULL otherwise.
 */
Person *add (Person **list, const char *firstName, const char *age)
{
  Person **ppn = list,                            /* address of list */
          *pn = *list,                            /* pointer to list */
          *node = createnode (firstName, age);    /* initialize & validate new node */

  if (!node)                /* node creation failed, return list */
    return NULL;

  while (pn) {  /* loop over each node */
    if (strcmp (firstName, pn->firstName) <= 0) { /* compare sorts before pn->firstName */
      node->previous = (*ppn)->previous;          /* if so, insert new before pn */
      node->next = pn;
      pn->previous = node;
      *ppn = node;          /* update node at address of current node to new node */
      return node;
    }
    if (!pn->next) {        /* if pn is last node, insert at end */
      pn->next = node;
      node->previous = pn;
      break;
    }
    ppn = &pn->next;        /* advamce address to address of next node */
    pn = pn->next;          /* advance pointer to next */
  }

  return pn ? node : (*list = node);  /* if not 1st node, return node, else *list=node */
}


#else
Person *add (Person *list, char *firstName, char *age)
{
  /* allocate node, use dereference ptr for size */
  Person *node = createnode (firstName, age),
         *iter = list,
         *prev = NULL;

  if (!node)                              /* validate EVERY allocation */
    return list;

  if (!list)                              /* if list empty */
    return node;                          /* return node */

  /* handle new 1st node */
  if (strcmp (firstName, iter->firstName) <= 0) {
    list->previous = node;
    node->next = list;
    return node;
  }

  /* iterate until firstName sorts before iter->firstName */
  while (iter && strcmp (iter->firstName, firstName) <= 0) {
    prev = iter;
    iter = iter->next;
  }

  if (!iter) {                            /* if new end node */
    prev->next = node;
    node->previous = prev;
  }
  else {                                  /* insert between nodes */
    node->previous = prev;
    node->next = iter;
    iter->previous = node;
    prev->next = node;
  }

  /* if new first node, return iter, otherwise return list */
  return strcmp (list->firstName, firstName) >= 0 ? node : list;
}

#endif

#ifdef ADDRDELETE
int delete (Person **list, const char *name)
{
  if (!*list) {             /* list-empty */
    puts ("List Empty");
    return 0;               /* return 0 - no replacement */
  }

  Person **ppn = list,      /* address of node (pointer-to-pointer-to-node) */
          *pn  = *list;     /* pointer to node */

  for (; pn; ppn = &pn->next, pn = pn->next) {    /* loop over all nodes */
    if (strcmp (pn->firstName, name) == 0) {      /* if node with name found */
      *ppn = pn->next;                    /* replace node at current address with next */
      if (pn->next)                       /* if not last node (*ppn now NULL) */
        (*ppn)->previous = pn->previous;  /* update node at address w/exiting previous */

      free (pn->firstName); /* free all memory for existing node */
      free (pn->age);
      free (pn);

      return 1;             /* return 1 - replacement made */
    }
  }

  fprintf (stderr, "warning: name not found '%s'.\n", name);

  return 0;
}
#else
/** delete node with firstName from list */
Person *delete (Person *list, char *name)
{
  if (list == NULL) {
    puts("List Empty");
    return list;
  }

  Person *curr = list; // current node
  Person *pre = NULL; // node previous to current

  // loop over the list and locate node with name
  while (curr && strcmp(curr->firstName, name) != 0) {
    pre = curr;
    curr = curr->next;
  }

  if (curr == NULL) { /* if name not found, warn & return */
    fprintf (stderr, "warning: name not found '%s'.\n", name);
    return list;
  }

  if (pre == NULL) {                /* remove first node */
    list = list->next;
    list->previous = NULL;
  }
  else {                            /* remove later node */
    pre->next = curr->next;
    if (curr->next)                 /* protect when removing last */
      curr->next->previous = pre;
  }

  free (curr->firstName);
  free (curr->age);
  free (curr);

  return list;
}
#endif

/** delete all nodes in list */
void del_list (Person *list)
{
  while (list) {
    Person *victim = list;
    list = list->next;
    free (victim->firstName);
    free (victim->age);
    free (victim);
  }
}

int main (int argc, char **argv) {
  FILE *in = argc > 1 ? fopen(argv[1], "r") : stdin;
  char name[20];
  char num[20];
  Person *list=NULL;

  while (fscanf(in, "%s %s",name, num) == 2)
#ifndef PASSPTR2PTR
    list = add(list,name, num);
#else
    add (&list, name, num);
#endif
  fclose (in);

  printf ("Original List\n***\n");
  print (list);
  puts ("\nPointers\n***");
  prnptrs (list);

  printf ("\nPrinting Reversed List\n***\n");
#ifndef PASSPTR2PTR
  reverseList(list);
#else
  reverseList(&list);
  print (list);
#endif

  puts ("\nRemoving Bill, Phil, Sam, bananas\n***");
#ifdef ADDRDELETE
  delete (&list, "Bill");
  delete (&list, "Phil");
  delete (&list, "Sam");
  delete (&list, "bananas");
#else
  list = delete (list, "Bill");
  list = delete (list, "Phil");
  list = delete (list, "Sam");
  list = delete (list, "bananas");
#endif

  print (list);

  del_list (list);

  return 0;
}