Matt finished the make file for our stack program. Matt's code is included at the bottom of this entry. Information on Make files can be found here. To use Matt's Make file:

On a lab46 terminal:

$ cd /var/public/data/fall2013/linkedlistimp

Then copy the contents of the directory:

• To copy into your ~/src/datas/ directory:

$ make copy

• To copy into a different directory:

$ cp -a ~/src/dir

In Matt's Make file:

• Variables are at the top.
• Then there are “Labels” that run a set of “rules”.
• Written in “MAKEFILE” and runs set of Bash commands.
• The /inc directory contains only headers.
• The /lib directory contains only libraries.
• The /src directory contains only the source code. Note: The parts rule equals the running of the shell command. This means Matt's Make file will only work on a Unix system.
• ar: Sets up the archiver.
• cc: Sets up the compiler.
• src: Lists all .c files in the src directory.
• obj: Turns every .c file into a .o object file.
• lib: Finds the current directory the script is in.
• all: Compiles src, handles objects, handles libraries.
• debug rule: Checks to see if the source code was compiled with debug symbols.
• lib rule: Checks library information.
• clean rule: Removes all .o object files.
• testing dir: Makes the libraries, renames the executable from the source code, then builds the final executable.

To use Matt's Make file:

1. $ make

2. $ ls lib

   Shows the newly made .lib files.

3. $ make clean

   Removes all the object files.

4. $ make debug

   Builds the source code with debugging symbols. Not required but good practice; can also use “make”.

5. The terminal output for Matt's Make file:

   lab46:~/src/datas/linkedlistimp$ make
   make[1]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src'
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/list'
   [L]                        ... SUCCESS
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/list'
   
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/node'
   [B]   cp.c                 ... OK
   [B]   mk.c                 ... OK
   [B]   rm.c                 ... OK
   [L]                        ... SUCCESS
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/node'
   
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/stack'
   [B]   peek.c               ... peek.c: In function 'peek':
   peek.c:6: warning: control reaches end of non-void function
   OK
   [B]   pop.c                ... OK
   [B]   push.c               ... OK
   [B]   stackops.c           ... OK
   [L]                        ... SUCCESS
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/stack'
   
   
   make[1]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src'
   
   
   lab46:~/src/datas/linkedlistimp$ ls lib
   liblist.a  libnode.a  libstack.a
   lab46:~/src/datas/linkedlistimp$ make clean
   make[1]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src'
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/list'
   rm -f *.o  core
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/list'
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/node'
   rm -f *.o cp.o mk.o rm.o core
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/node'
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/stack'
   rm -f *.o peek.o pop.o push.o stackops.o core
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/stack'
   make[1]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src'
   make[1]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/testing'
   rm -f *.o stacktest core
   make[1]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/testing'
   lab46:~/src/datas/linkedlistimp$ make debug
   make[1]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src'
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/list'
   ar rcs ../../lib/liblist.a 
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/list'
   
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/node'
   gcc -Wall -I ../../inc  -DDEBUG -g -c cp.c
   gcc -Wall -I ../../inc  -DDEBUG -g -c mk.c
   gcc -Wall -I ../../inc  -DDEBUG -g -c rm.c
   ar rcs ../../lib/libnode.a cp.o mk.o rm.o
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/node'
   
   make[2]: Entering directory `/home/nbrimme1/src/datas/linkedlistimp/src/stack'
   gcc -Wall -I ../../inc  -DDEBUG -g -c peek.c
   peek.c: In function 'peek':
   peek.c:6: warning: control reaches end of non-void function
   gcc -Wall -I ../../inc  -DDEBUG -g -c pop.c
   gcc -Wall -I ../../inc  -DDEBUG -g -c push.c
   gcc -Wall -I ../../inc  -DDEBUG -g -c stackops.c
   ar rcs ../../lib/libstack.a peek.o pop.o push.o stackops.o
   make[2]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src/stack'
   
   
   make[1]: Leaving directory `/home/nbrimme1/src/datas/linkedlistimp/src'
   
   
   lab46:~/src/datas/linkedlistimp$

Matt's Code:

• /src/datas/linkedlistimp
  • /inc
    • list.h

      #ifndef _LIST_H
      #define _LIST_H
       
      #include "node.h"
       
      struct list {
      	Node *start;
      	Node *end;
      	int qty;
      };
      typedef struct list List;
       
      List *mklist();
      List *insert(List *, Node *, Node *);
      List *append(List *, Node *, Node *);
      List *removeNode(List *, Node **);
      void displayf(List *);
      void displayb(List *);
      List *clearlist(List *);
      List *sortlist(List *);
       
      #endif

    • node.h

      #ifndef _NODE_H
      #define _NODE_H
       
      #include <stdlib.h>
       
      struct node {
      	struct node *next;
      	struct node *prev;
      	int value;
      };
      typedef struct node Node;
       
      Node *mknode(int);
      void  rmnode(Node **);
      Node *cpnode(Node *);
       
      #endif

    • queue.h

      #ifndef _QUEUE_H
      #define _QUEUE_H
       
      #include "list.h"
       
      struct queue {
      	List *data;
      	Node *front;
      	Node *back;
      	int bufsize;
      };
      typedef struct queue Queue;
       
      Queue *mkqueue(int);
      Queue *enqueue(Queue *, Node *);
      Node  *dequeue(Queue **);
       
      #endif

    • stack.h

      #ifndef _STACK_H
      #define _STACK_H
       
      #include "list.h"
       
      struct stack {
      	List *data;
      	Node *top;
      	int size;
      };
      typedef struct stack Stack;
       
      Stack *mkstack(int);
      Stack *push   (Stack *, Node *);
      Node  *pop    (Stack **);
      Node  *peek   (Stack *);
       
      #endif

  • /lib
    • liblist.a: Library file for list.c.
    • libnode.a: Library file for node.c.
    • libstack.a: Library file for stack.c.
  • /src
    • /src/list
      • Makefile

        CFLAGS = -Wall
        INC = -I ../../inc
        AR = ar
        CC = gcc $(CFLAGS) $(INC) 
        SRC = $(shell /bin/ls -1 *.c 2>/dev/null)
        OBJ = $(SRC:.c=.o)
        LIB = $(shell /bin/pwd | /bin/sed 's/^.*\///')
        all: $(SRC) $(OBJ) lib
         
        debug: CC += -DDEBUG -g
        debug: DEBUG = debug
        debug: $(SRC) $(OBJ) lib
         
        .c.o:
        ifneq ($(MAKECMDGOALS),debug)
        	@printf "[B]   %-20s ... " "$<"
        	@$(CC) -c $< && echo "OK" || echo "FAIL"
        else
        	$(CC) -c $<
        endif
         
        lib:
        ifneq ($(MAKECMDGOALS),debug)
        	@printf "[L]   %-20s ... " "$<"
        	@$(AR) rcs ../../lib/lib$(LIB).a $(OBJ) && echo "SUCCESS" || echo "FAIL"
        else
        	$(AR) rcs ../../lib/lib$(LIB).a $(OBJ)
        endif
         
         
        clean:
        	rm -f *.o $(OBJ) core

    • /src/node
      • Makefile

        CFLAGS = -Wall
        INC = -I ../../inc
        AR = ar
        CC = gcc $(CFLAGS) $(INC) 
        SRC = $(shell /bin/ls -1 *.c 2>/dev/null)
        OBJ = $(SRC:.c=.o)
        LIB = $(shell /bin/pwd | /bin/sed 's/^.*\///')
        all: $(SRC) $(OBJ) lib
         
        debug: CC += -DDEBUG -g
        debug: DEBUG = debug
        debug: $(SRC) $(OBJ) lib
         
        .c.o:
        ifneq ($(MAKECMDGOALS),debug)
        	@printf "[B]   %-20s ... " "$<"
        	@$(CC) -c $< && echo "OK" || echo "FAIL"
        else
        	$(CC) -c $<
        endif
         
        lib:
        ifneq ($(MAKECMDGOALS),debug)
        	@printf "[L]   %-20s ... " "$<"
        	@$(AR) rcs ../../lib/lib$(LIB).a $(OBJ) && echo "SUCCESS" || echo "FAIL"
        else
        	$(AR) rcs ../../lib/lib$(LIB).a $(OBJ)
        endif
         
         
        clean:
        	rm -f *.o $(OBJ) core

    • /src/node
      • cp.c

        #include "node.h"
         
        Node *cpnode(Node *tmp)
        {
        	Node *newNode = mknode(tmp -> value);
         
        	newNode -> prev = newNode -> next = NULL;
         
        	return(newNode);
        }

      • mk.c

        #include "node.h"
         
        Node *mknode(int value)
        {
        	Node *tmp = (Node *) malloc (sizeof(Node));
         
        	tmp -> prev  = tmp -> next = NULL;
        	tmp -> value =               value;
         
        	return(tmp);
        }

      • rm.c

        #include "node.h"
         
        void rmnode(Node **tmp)
        {
        	if ((*tmp) -> prev != NULL)
        	{
        		(*tmp) -> prev -> next = (*tmp) -> next;
        	}
         
        	if ((*tmp) -> next != NULL)
        	{
        		(*tmp) -> next -> prev = (*tmp) -> prev;
        	}
         
        	(*tmp) -> prev  = (*tmp) -> next = NULL;
        }

      • cp.o: Object file for cp.c
      • mk.o: Object file for mk.o
      • rm.o: Object file for rm.o
    • /src/stack
      • Makefile

        CFLAGS = -Wall
        INC = -I ../../inc
        AR = ar
        CC = gcc $(CFLAGS) $(INC) 
        SRC = $(shell /bin/ls -1 *.c 2>/dev/null)
        OBJ = $(SRC:.c=.o)
        LIB = $(shell /bin/pwd | /bin/sed 's/^.*\///')
        all: $(SRC) $(OBJ) lib
         
        debug: CC += -DDEBUG -g
        debug: DEBUG = debug
        debug: $(SRC) $(OBJ) lib
         
        .c.o:
        ifneq ($(MAKECMDGOALS),debug)
        	@printf "[B]   %-20s ... " "$<"
        	@$(CC) -c $< && echo "OK" || echo "FAIL"
        else
        	$(CC) -c $<
        endif
         
        lib:
        ifneq ($(MAKECMDGOALS),debug)
        	@printf "[L]   %-20s ... " "$<"
        	@$(AR) rcs ../../lib/lib$(LIB).a $(OBJ) && echo "SUCCESS" || echo "FAIL"
        else
        	$(AR) rcs ../../lib/lib$(LIB).a $(OBJ)
        endif
         
         
        clean:
        	rm -f *.o $(OBJ) core

      • peek.c

        #include "stack.h"
         
        Node *peek(Stack *myStack)
        {
        	// exercise left to the implementer
        }

      • pop.c

        #include "stack.h"
         
        Node *pop(Stack **myStack)
        {
        	Node *tmp = NULL;
         
        	if ((*myStack) != NULL)
        	{
        		tmp = (*myStack) -> data -> end;
        		(*myStack) -> data = removeNode((*myStack) -> data, &tmp);
        		(*myStack) -> top  = (*myStack) -> data -> end;
        	}
         
        	return (tmp);
        }

      • push.c

        #include "stack.h"
         
        Stack *push(Stack *myStack, Node *newNode)
        {
        	if ((myStack -> size <= 0) || ((myStack -> data -> qty) < (myStack -> size)))
        	{
        		myStack -> data = append(myStack -> data, myStack -> data -> end, newNode);
        		myStack -> top  = myStack -> data -> end;
        	}
         
        	return(myStack);
        }

      • stackops.c

        #include "stack.h"
         
        Stack *mkstack(int size)
        {
        	Stack *myStack;
         
        	myStack = (Stack *) malloc (sizeof(Stack));
         
        	myStack -> data = mklist();
        	myStack -> size = size;
        	myStack -> top  = myStack -> data -> end;
         
        	return (myStack);
        }

      • peek.o: Object file for peek.c.
      • pop.o: Object file for pop.c.
      • push.o: Object file for push.c.
      • stackops.o: Object file for stackops.c.
    • Makefile

      SHELL = /bin/bash -e
      CC = g++ $(CFLAGS) $(OPTS) $(INC)
      INC = -I ../include/
      CFLAGS = -Wall 
      OBJ = $(shell find . -name *.o)
      OPTS =
      PARTS = $(shell /bin/ls -1Ad * | grep -v 'Makefile')
      AR = ar
      DEBUG = 
      default: libs
       
      debug: CC += -DDEBUG -g
      debug: DEBUG = debug
      debug: libs
       
      libs:
      	@for i in $(PARTS); do make -C $$i $(DEBUG); echo; done
      	@echo
       
      clean:
      	@for i in $(PARTS); do make -C $$i clean; done
      	@rm -f ${LIB}

  • /testing
    • Makefile

      SHELL = /bin/bash -e
      INC = -I inc/
      CCFLAGS = -Wall 
      OPTS =
      CC = gcc $(CCFLAGS) $(OPTS) $(INC)
      OBJ = 
      AR = ar
      DEBUG = 
      LIBS = src
      UNIT = testing
      ALL = $(LIBS) testing
      BIN = 
      default: libs testing
      debug: libs-debug testing-debug
      #default: $(LIBS) $(BIN)
       
      libs-debug: CC += -DDEBUG -g
      libs-debug: DEBUG = debug
      libs-debug: libs
       
      libs:
      	@for i in $(LIBS); do make -C $$i $(DEBUG); echo; done
      	@echo
       
      testing-debug: CC += -DDEBUG -g
      testing-debug: DEBUG = debug
      testing-debug: testing
       
      testing:
      	@for i in $(UNIT); do make -C $$i $(DEBUG); echo; done
      	@echo
       
      clean:
      	@for i in $(ALL); do make -C $$i clean; done
      #	@rm -f bin/*
       
      copy:
      	mkdir -p ~/src/data/linkedlistimp
      	cp -av /var/public/data/fall2013/linkedlistimp/* ~/src/data/linkedlistimp/
       
      help:
      	@echo
      	@echo "****************[ Data Structures List Implementation ]*****************"
      	@echo "** make                     - build everything                        **"
      	@echo "** make debug               - build everything with debug symbols     **"
      	@echo "**                                                                    **"
      	@echo "** make testing             - build unit tests                        **"
      	@echo "** make testing-debug       - build unit tests with debugging symbols **"
      	@echo "** make libs                - build all supporting libraries          **"
      	@echo "** make libs-debug          - build all libraries with debug symbols  **"
      	@echo "**                                                                    **"
      	@echo "** make clean               - clean; remove all objects/compiled code **"
      	@echo "** make help                - this information                        **"
      	@echo "************************************************************************"

      • stacktest.c

        #include <stdio.h>
        #include "stack.h"
         
        int main()
        {
        	Node *tmp;
        	Stack *myStack;
        	myStack = mkstack(0);
        	tmp = create();
        	tmp -> value = fgetc(stdin);
        	fgetc(stdin);
         
        	while(tmp->value != '\n')
        	{
        		myStack = push(myStack, tmp);
        		tmp = create();
        		tmp->value = fgetc(stdin);
        		fgetc(stdin);
        	}
         
        	fprintf(stdout, "linked list has %d nodes\n", myStack->data->qty);
        	fprintf(stdout, "String is: ");
        	do {
        		tmp = pop(&myStack);
        		if(tmp != NULL)
        		{
        			fprintf(stdout, "%c", tmp->value);
        		}
        		rmnode(*tmp);
        	}
        	while(tmp != NULL);
         
        	fprintf(stdout, "\n");
        	return(0);
        }

  • Makefile

    SHELL = /bin/bash -e
    INC = -I inc/
    CCFLAGS = -Wall 
    OPTS =
    CC = gcc $(CCFLAGS) $(OPTS) $(INC)
    OBJ = 
    AR = ar
    DEBUG = 
    LIBS = src
    UNIT = testing
    ALL = $(LIBS) testing
    BIN = 
    default: libs testing
    debug: libs-debug testing-debug
    #default: $(LIBS) $(BIN)
     
    libs-debug: CC += -DDEBUG -g
    libs-debug: DEBUG = debug
    libs-debug: libs
     
    libs:
    	@for i in $(LIBS); do make -C $$i $(DEBUG); echo; done
    	@echo
     
    testing-debug: CC += -DDEBUG -g
    testing-debug: DEBUG = debug
    testing-debug: testing
     
    testing:
    	@for i in $(UNIT); do make -C $$i $(DEBUG); echo; done
    	@echo
     
    clean:
    	@for i in $(ALL); do make -C $$i clean; done
    #	@rm -f bin/*
     
    copy:
    	mkdir -p ~/src/data/linkedlistimp
    	cp -av /var/public/data/fall2013/linkedlistimp/* ~/src/data/linkedlistimp/
     
    help:
    	@echo
    	@echo "****************[ Data Structures List Implementation ]*****************"
    	@echo "** make                     - build everything                        **"
    	@echo "** make debug               - build everything with debug symbols     **"
    	@echo "**                                                                    **"
    	@echo "** make testing             - build unit tests                        **"
    	@echo "** make testing-debug       - build unit tests with debugging symbols **"
    	@echo "** make libs                - build all supporting libraries          **"
    	@echo "** make libs-debug          - build all libraries with debug symbols  **"
    	@echo "**                                                                    **"
    	@echo "** make clean               - clean; remove all objects/compiled code **"
    	@echo "** make help                - this information                        **"
    	@echo "************************************************************************"

I'm finding that GDB is quickly becoming an indispensable and invaluable tool when finding and fixing bugs. The command alias gcc='gcc -g' won't negatively effect anything in the future, so I'll make it an alias. Also, Google has some nice GDB “cheat sheets” that will come in handy.

I had the idea to use 2 lists instead of modifying just 1. My logic is complicated and that logic seems far more simpler; and hopefully simpler to implement.

Pseudocode/Logic steps:

1. Create 2 lists: (Not sure this will work; Could copy tmp's list into tmp2's list, then call clearList() on tmp2?).
   1. tmp → unsorted list.
   2. tmp2 → sorted list.
2. Find the lowest value in tmp's list
3. Insert that value into tmp2's list
4. Remove the lowest value from tmp's list
5. Repeat steps 2-4 until the program is at the end of the tmp's list.
   1. Not sure if this is needed; delete empty tmp list?
6. Display tmp2's sorted list.

Back to my Opus