/* File: stringlist.c * Author: Samuel A. Rebelsky * Version: 1.0 of February 2000 * * A simple implementation of doubly-linked lists of strings. Elements * remain in the order in which they're specified. Written as an example * for CSC364 2000S. * * Provides: * newList() * create a new list * addToFront(stringlist, string) * add an element to the front of the list * addToEnd(stringlist, string) * add an element to the end of the list * deleteAll(stringlist, pattern) * delete all copies of the pattern * clear(stringlist) * remove everything from the list * freeList(stringlist) * deallocate memory associated with the list * reset(stringlist) * prepare to iterate the list * nextElement(stringlist) * return the next element in the list; returns NULL when * you reach the end of the list. */ /*********** * Headers * *****************************************************************/ #include "debug.h" /* Yes, I have to debug, too. */ #include "stringlist.h" /* Defines these functions. */ #include /* Provides: malloc, free. */ /********* * Types * *****************************************************************/ /* The nodes in the list. Kept local to this file so that * the code is appropriately encapsulated. */ struct node { char *contents; struct node *next; struct node *prev; }; /* The helpful wrapper class. Keeps track of the first and last * elements of the list and the (currently unused) length of the * list. */ struct stringlist { struct node *front; // The first node in the list. struct node *back; // The last node in the list. struct node *current; // The current node (for iteration). int length; // The number of elements in the list. }; /******************************* * Local Function Declarations * *****************************************************************/ /* Free the space allocated to a node. Written this way to make it * easier to choose other ways to allocate and deallocate memory * for nodes. Note that after you free a node, the pointer still * points somewhere in memory, so you should reset it. * Pre: The node was allocated by newNode. * Post: The memory allocated to the node is now available. */ void freeNode(struct node *garbage); /* Create a new list node with specified contents. Note that this * makes a *copy* of the string (which means that the copy must * also be freed. * Pre: None * Post: Returns a pointer to a node. Returns NULL if there * is insufficient memory available for the new node. */ struct node *newNode(char *contents); /******************** * Exported Methods * *****************************************************************/ /* Add an element to the end of the list. */ int addToEnd(stringlist stuff, char *value) { struct node *newEnd; /* The node for the front of the list. */ /* Create the new node. */ newEnd = newNode(value); if (newEnd == NULL) return 0; /* Special case: Empty list. */ if (stuff->front == NULL) { /* Put it at the front. */ stuff->front = newEnd; /* It's also at the back! */ stuff->back = newEnd; /* And hey, let's make it the current element, too. */ stuff->current = newEnd; } /* Normal case. */ else { /* Link it to the front of the list. */ newEnd->prev = stuff->back; stuff->back->next = newEnd; /* And put it at the front. */ stuff->back = newEnd; } /* normal case */ /* Increment the length of the list. */ ++(stuff->length); /* Indicate success. */ return 1; } // addToEnd() */ /* Add an element to the front of the list. */ int addToFront(stringlist stuff, char *value) { struct node *newFront; /* The node for the front of the list. */ /* Create the new node. */ newFront = newNode(value); if (newFront == NULL) return 0; /* Special case: Empty list. */ if (stuff->front == NULL) { /* Put it at the front. */ stuff->front = newFront; /* It's also at the back! */ stuff->back = newFront; /* And hey, let's make it the current element, too. */ stuff->current = newFront; } /* Normal case. */ else { /* Link it to the front of the list. */ newFront->next = stuff->front; stuff->front->prev = newFront; /* And put it at the front. */ stuff->front = newFront; } /* normal case */ /* Increment the length of the list. */ ++(stuff->length); /* Indicate success. */ return 1; } /* addToFront() */ /* Clear the list. */ void clear(stringlist stuff) { struct node *tmp = stuff->front; /* Deallocate all the memory by stepping through the nodes one by one. */ while (tmp != NULL) { freeNode(tmp); tmp = tmp->next; } /* Clear the fields. */ stuff->front = NULL; stuff->back = NULL; stuff->current = NULL; stuff->length = 0; } /* clear() */ /* Delete all copies of a pattern from the list. */ void deleteAll(stringlist stuff, char *pattern) { struct node *deleteMe; struct node *tmp = stuff->front; LOG_SS("Searching for", pattern); /* Step through each of the nodes. */ while (tmp != NULL) { LOG_SS("Checking", tmp->contents); /* Does it match the pattern? */ if (strcmp(tmp->contents, pattern) == 0) { LOG_S("MATCHED"); /* Update the previous node, if one exists. */ if (tmp->prev != NULL) { LOG_S("UPDATING PREV"); tmp->prev->next = tmp->next; } /* Update the next node, if one exists. */ if (tmp->next != NULL) tmp->next->prev = tmp->prev; /* Update the front of the list if necessary. */ if (stuff->front == tmp) stuff->front = tmp->next; /* Update the back of the list if necessary. */ if (stuff->back == tmp) { LOG_S("UPDATING BACK"); stuff->back = tmp->prev; } /* Update the current element (just to be safe). */ if (stuff->current == tmp) stuff->current = NULL; /* Update the length of the list. */ --(stuff->length); /* Remember the node we're about to delete. */ deleteMe = tmp; /* Move on to the next value. */ tmp = tmp->next; /* Free memory. */ freeNode(deleteMe); } /* did we match the pattern? */ /* If we don't match the pattern ... */ else { /* Just move on to the next value. */ tmp = tmp->next; } /* Didn't match. */ } /* for each node in the list. */ } /* deleteAll() */ /* Free the space allocated to a list. */ void freeList(stringlist stuff) { clear(stuff); free((char *) stuff); } //* freeList() */ /* Create a new, empty list. */ stringlist newList() { stringlist tmp = (stringlist) malloc(sizeof(struct stringlist)); if (tmp != NULL) { tmp->front = NULL; tmp->back = NULL; tmp->length = 0; } return tmp; } /* newList() */ /* Get the next uniterated element of the list. */ char * nextElement(stringlist stuff) { char *str; /* The string we plan to return. */ /* Special case: at the end of the list. */ if (stuff->current == NULL) return NULL; /* Normal case. */ else { str = stuff->current->contents; stuff->current = stuff->current->next; return str; } /* normal case */ } /* nextElement() */ /* Reset iteration to the beginning of the list. */ void reset(stringlist stuff) { stuff->current = stuff->front; } /* reset() */ /***************** * Local Methods * *****************************************************************/ /* Free a node. */ void freeNode(struct node *garbage) { if (garbage->contents != NULL) free(garbage->contents); garbage->next = NULL; garbage->prev = NULL; free(garbage); } // freeNode(struct node *) /* Create a new node. */ struct node * newNode(char *contents) { struct node *tmp = (struct node *) malloc(sizeof(struct node)); if (tmp != NULL) { tmp->next = NULL; tmp->prev = NULL; tmp->contents = (char *) malloc(strlen(contents)+1); // Sanity check if (tmp->contents == NULL) { free(tmp); return NULL; } strcpy(tmp->contents, contents); } return tmp; } /* newNode() */