Lab46 Wiki

User Tools

Site Tools

You are here: start » opus » fall2014 » mgardne8
opus:fall2014:mgardne8:start

Table of Contents

Matt Gardner's fall2014 Opus

dimidium facti qui coepit habet

He who has begun has the work half done

Horace, Epistularum liber primus, Epistle II

Introduction

Currently I'm studying computer science to move on into Computational Neuroscience. The field of Computational Neuroscience has always interested me, and I believe that with better models and research into the brain we will be able to find the causes and how to heal many mental disorders.

Data Structures Journal

18 September 2014

Notes

Fix your makefile for node0: Change into your node0 folder then issue fixit 

lab46:~/src/Data/node0$ fixit
Copying base Makefile from /var/public/data/fall2014/node0 ...
    '/var/public/data/fall2014/node0/Makefile' -> '/home/mgardne8/src/Data/node0/Makefile'

View the new make help 

lab46:~/src/Data/node0$ make help
*********************************************************
*** NEW UPDATE AVAILABLE: Type 'make update' to apply ***
*********************************************************

****************[ Data Structures List Implementation ]*****************
** make                     - build everything (libs and testing)     **
** make debug               - build everything with debug symbols     **
**                                                                    **
** make libs                - build all supporting libraries          **
** make libs-debug          - build all libraries with debug symbols  **
** make testing             - build unit tests                        **
** make testing-debug       - build unit tests with debugging symbols **
**                                                                    **
** make save                - create a backup archive                 **
** make submit              - submit assignment (based on dirname)    **
** make update              - check for and apply updates             **
**                                                                    **
** make clean               - clean; remove all objects/compiled code **
** make help                - this information                        **
************************************************************************

apply the new update: make update 

lab46:~/src/Data/node0$ make update
Update 1 COMMENCING
Update 1 CHANGE SUMMARY: Fixed base and other Makefile typos
    Please reference errata section on project page for more information
Update 1 COMPLETE
Update 2 COMMENCING
Update 2 CHANGE SUMMARY: Ensure sane permissions for files
    Please reference errata section on project page for more information
Update 2 COMPLETE
Updated from revision 0 to revision 2

Linked list

[temp→(12)→(57)→(26)→NULL] singly linked list^^

[NULL↔(12)↔(57)↔(26)↔NULL] doubly linked list^^

linked lists cplist() copy list rmlist() removes the list element by element mklist() makes the list? insert() add a node BEFORE specified node append() add a node AFTER specified node obtain() disconnect specified node from list displayf() Display list from the beginning to the end displayb() Display list from the end to the beginning search() sortlist() swap()

Submit can now be used to see your status on projects 

lab46:~/src/Data/node0$ submit data
data projects:
    intro, submitted on 20140911-085637
    node0, due on 20140924 (in 6 days)
    node1, due on 20141001 (in 13 days)

23 September 2014

node0

Upgrade node0 to node1 with make upgrade-node1 inside of node0 

--(mgardne8@lab46)-(09:10am)-( ~/src/Data/node0$)--
-->make upgrade-node1
make[1]: Entering directory '/home/mgardne8/src/Data/node0/src'
make[2]: Entering directory '/home/mgardne8/src/Data/node0/src/node'
rm -f *.swp *.o  core
make[2]: Leaving directory '/home/mgardne8/src/Data/node0/src/node'
make[1]: Leaving directory '/home/mgardne8/src/Data/node0/src'
make[1]: Entering directory '/home/mgardne8/src/Data/node0/testing'
make[2]: Entering directory '/home/mgardne8/src/Data/node0/testing/node'
make[3]: Entering directory '/home/mgardne8/src/Data/node0/testing/node/app'
rm -f *.swp *.o ../../../bin/node-app-display node-app-test node-app-test2 core
make[3]: Leaving directory '/home/mgardne8/src/Data/node0/testing/node/app'
make[2]: Leaving directory '/home/mgardne8/src/Data/node0/testing/node'
make[1]: Leaving directory '/home/mgardne8/src/Data/node0/testing'
Archiving the project ...
Compressing the archive ...
Setting Permissions ...
You may now switch to the ../node1 directory

There are new files in: 

./src/node/
./testing/node/app/
./testing/node/unit/

Each function is in it's own file: 

./src/node/mk.c - make   node
./src/node/rm.c - remove node
./src/node/cp.c - copy   node

Code

Node *tmp3, *tmp4;
tmp3 = mknode(8);
tmp4 = cpnode(tmp3);

tmp3 → (8) → NULL ← (8) ← tmp4 

tmp3 = rmnode(tmp3);

NULL ← (8) ← tmp4

malloc allocates;

free deallocates;

25 September 2014

NAI (Notes As Images)

sep_25_1.bmp sep_25_2.bmp sep_25_3.bmp sep_25_4.bmp sep_25_5.bmp

NAC (Notes As Code)

PointerFun.c
#include <stdio.h>
#include <stdlib.h>
 
struct node{
	char value;
	struct node *next;
};
 
typedef struct node Node;
 
int main(void)
{
	Node   *tmp, *tmp2, *start, *end;
	tmp  = tmp2 = start = end = NULL;
	char   input;
	int    i;
 
	while (input != -1)
	{
	        printf("Enter a value(-1 to finalize): ");
	        scanf ("%hhd",&input);
 
		if(start == NULL)
		{
			start        = end  = (Node*)malloc(sizeof(Node));
			start->value = input;
			start->next  = NULL;
		}
		else
		{
			end->next   = (Node*)malloc(sizeof(Node));
			end         = end->next;
			end->value  = input;
			end->next   = NULL;
		}
	}
 
	printf("Enter value of new node: ");
	scanf ("%hhd",&input);
 
	tmp        = (Node*)malloc(sizeof(Node));
	tmp->value = input;
	tmp->next  = NULL;
 
	printf("Enter node value to insert before: ");
	scanf ("%hhd",&input);
 
	tmp2 = start;
 
	while(tmp2->next->value != input)
	{
		tmp2 = tmp2->next;
	}
 
	tmp->next  = tmp2->next;
	tmp2->next = tmp;
 
	//display the list
 
	return(0);
}

JMW (Just Misc. Writing)

insert before append after

tmp →NULL tmp2 →(13)

Insert node into empty list, node becomes the list tmp →(13)← tmp2

insert tmp before tmp2

tmp2→(x)

2 October 2014

Ouch!

Debugging!

Working it out
sll-debug.c
#include <stdio.h>
#include <stdlib.h>
//Original/Broken
struct node {
	char value;
	struct node *next;
};
typedef struct node Node;
 
int main()
{
	Node *start, *end, *tmp, *tmp2;
	char input;
 
	start        = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1);
	tmp -> value = 0;
	tmp -> next  = NULL;
 
	fprintf(stdout, "Enter a value (-1 to complete): ");
	fscanf(stdin, "%hhd", &input);
 
	while (input != -1)
	{
		end -> value = input;
 
		end -> next = (Node *) malloc (sizeof(Node)*1);
		end -> next -> value = 0;
		end -> next -> next  = NULL;
 
		fprintf(stdout, "Enter a value (-1 to complete): ");
		fscanf(stdin, "%hhd", &input);
 
		if (input == -1)
		{
			free(end -> next);
			end -> next = NULL;
		}
		else
			end = end -> next;
	}
 
	// Display list from start to end
 
	fprintf(stdout, "Enter value for new node: ");
	fscanf(stdin, "%hhd", &input);
 
	tmp = (Node *) malloc (sizeof(Node));
	tmp -> value = input;
	tmp -> next = NULL;
 
	fprintf(stdout, "Enter value of node you want to insert new node before: ");
	fscanf(stdin, "%hhd", &input);
 
	tmp2 = start;
	while (tmp2 -> next -> value != tmp -> value)
		tmp2 = tmp2 -> next;
 
	tmp  -> next = tmp2 -> next;
	tmp2 -> next = tmp;
 
	// Display list from start to end
 
	return(0);
}
--(mgardne8@[ 0;37mlab46)-(08:48am)-( ~/src/Data/example$)-- 

-->ll
total 4
-rw-r----- 1 mgardne8 lab46 1230 Sep 30 10:22 sll-debug.c

--(mgardne8@[ 0;37mlab46)-(08:48am)-( ~/src/Data/example$)-- 

-->gcc -g -o sll-debug sll-debug.c 

--(mgardne8@[ 0;37mlab46)-(08:48am)-( ~/src/Data/example$)-- 

-->gdb sll-debug
GNU gdb (Debian 7.7.1+dfsg-3) 7.7.1
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from sll-debug...done.
(gdb) run
Starting program: /home/mgardne8/src/Data/example/sll-debug 
Enter a value (-1 to complete): 1
Enter a value (-1 to complete): 2
Enter a value (-1 to complete): 3
Enter a value (-1 to complete): 4
Enter a value (-1 to complete): -1
Enter value for new node: 10
Enter value of node you want to insert new node before: 2

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400862 in main () at sll-debug.c:55
55		while (tmp2 -> next -> value != tmp -> value)
(gdb) print tmp -> value
$1 = 10 '\n'
(gdb) print tmp2 -> next -> value
Cannot access memory at address 0x0
(gdb) print tmp2 -> value
$2 = 4 '\004'
(gdb) quit
A debugging session is active.

	Inferior 1 [process 14301] will be killed.

Quit anyway? (y or n) y

It appears to be segfaulting on line 55, looking at the line, we are checking for the int 'tmp → value' and not the int 'input' lets fix this and try again

sll-debug-fixed.c
#include <stdio.h>
#include <stdlib.h>
//Fixed!
struct node {
	char value;
	struct node *next;
};
typedef struct node Node;
 
int main()
{
	Node *start, *end, *tmp, *tmp2;
	char input;
 
	start        = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1);
	tmp -> value = 0;
	tmp -> next  = NULL;
 
	fprintf(stdout, "Enter a value (-1 to complete): ");
	fscanf(stdin, "%hhd", &input);
 
	while (input != -1)
	{
		end -> value = input;
 
		end -> next = (Node *) malloc (sizeof(Node)*1);
		end -> next -> value = 0;
		end -> next -> next  = NULL;
 
		fprintf(stdout, "Enter a value (-1 to complete): ");
		fscanf(stdin, "%hhd", &input);
 
		if (input == -1)
		{
			free(end -> next);
			end -> next = NULL;
		}
		else
			end = end -> next;
	}
 
	// Display list from start to end
 
	fprintf(stdout, "Enter value for new node: ");
	fscanf(stdin, "%hhd", &input);
 
	tmp = (Node *) malloc (sizeof(Node));
	tmp -> value = input;
	tmp -> next = NULL;
 
	fprintf(stdout, "Enter value of node you want to insert new node before: ");
	fscanf(stdin, "%hhd", &input);
 
	tmp2 = start;
	while (tmp2 -> next -> value != input) // replaced 'tmp -> value' with 'input'
		tmp2 = tmp2 -> next;
 
	tmp  -> next = tmp2 -> next;
	tmp2 -> next = tmp;
 
	// Display list from start to end
 
	return(0);
}
--(mgardne8@[ 0;37mlab46)-(08:48am)-( ~/src/Data/example$)-- 

-->gcc -g -o sll-debug-fixed sll-debug-fixed.c 

--(mgardne8@[ 0;37mlab46)-(08:48am)-( ~/src/Data/example$)-- 

-->gdb sll-debug-fixed
GNU gdb (Debian 7.7.1+dfsg-3) 7.7.1
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from sll-debug-fixed...done.
(gdb) run
Starting program: /home/mgardne8/src/Data/example/sll-debug-fixed 
Enter a value (-1 to complete): 1
Enter a value (-1 to complete): 2
Enter a value (-1 to complete): 3
Enter a value (-1 to complete): 4
Enter a value (-1 to complete): 5
Enter a value (-1 to complete): 6
Enter a value (-1 to complete): 7
Enter a value (-1 to complete): -1
Enter value for new node: 900
Enter value of node you want to insert new node before: 4
[Inferior 1 (process 15835) exited normally]
(gdb) quit

It works!

Quick notes

x <variable> - Dereferences value and dumps memory at that location - can't use on non-pointers 

(gdb) x tmp  
0x6010d0:	0x00000009
(gdb) x tmp2  
0x601030:	0x00000002
(gdb) x tmp2->next
0x601050:	0x00000003
(gdb) x tmp2->next->value
0x3:	Cannot access memory at address 0x3
(gdb) x input            
0x5:	Cannot access memory at address 0x5

whatis <variable> - displays variable type! 

(gdb) whatis input
type = char
(gdb) whatis tmp
type = Node *
(gdb) whatis tmp->next
type = struct node *
(gdb) whatis tmp->value
type = char

set var <variable>=<value> 

(gdb) print tmp->value
$2 = 9 '\t'
(gdb) set var tmp->value=8
(gdb) print tmp->value
$3 = 8 '\b'

disas /m main 

(gdb) disas /m main  -  dissasemble and dump the assembler code
Dump of assembler code for function main:
11	{
   0x0000000000400676 <+0>:	push   %rbp
   0x0000000000400677 <+1>:	mov    %rsp,%rbp
   0x000000000040067a <+4>:	sub    $0x30,%rsp

12		Node *start, *end, *tmp, *tmp2;
13		char input;
14	
15		start        = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1);
   0x000000000040067e <+8>:	mov    $0x10,%edi
   0x0000000000400683 <+13>:	callq  0x400560 <malloc@plt>
   0x0000000000400688 <+18>:	mov    %rax,-0x10(%rbp)
   0x000000000040068c <+22>:	mov    -0x10(%rbp),%rax
   0x0000000000400690 <+26>:	mov    %rax,-0x18(%rbp)
   0x0000000000400694 <+30>:	mov    -0x18(%rbp),%rax
   0x0000000000400698 <+34>:	mov    %rax,-0x8(%rbp)
   0x000000000040069c <+38>:	mov    -0x8(%rbp),%rax
   0x00000000004006a0 <+42>:	mov    %rax,-0x20(%rbp)

16		tmp -> value = 0;
   0x00000000004006a4 <+46>:	mov    -0x18(%rbp),%rax
   0x00000000004006a8 <+50>:	movb   $0x0,(%rax)

17		tmp -> next  = NULL;
   0x00000000004006ab <+53>:	mov    -0x18(%rbp),%rax
   0x00000000004006af <+57>:	movq   $0x0,0x8(%rax)

18	
19		fprintf(stdout, "Enter a value (-1 to complete): ");
   0x00000000004006b7 <+65>:	mov    0x200652(%rip),%rax        # 0x600d10 <stdout@@GLIBC_2.2.5>
   0x00000000004006be <+72>:	mov    %rax,%rcx
   0x00000000004006c1 <+75>:	mov    $0x20,%edx
   0x00000000004006c6 <+80>:	mov    $0x1,%esi
   0x00000000004006cb <+85>:	mov    $0x400918,%edi
   0x00000000004006d0 <+90>:	callq  0x400570 <fwrite@plt>

20		fscanf(stdin, "%hhd", &input);
   0x00000000004006d5 <+95>:	mov    0x20063c(%rip),%rax        # 0x600d18 <stdin@@GLIBC_2.2.5>
   0x00000000004006dc <+102>:	lea    -0x21(%rbp),%rdx
   0x00000000004006e0 <+106>:	mov    $0x400939,%esi
   0x00000000004006e5 <+111>:	mov    %rax,%rdi
   0x00000000004006e8 <+114>:	mov    $0x0,%eax
   0x00000000004006ed <+119>:	callq  0x400530 <__isoc99_fscanf@plt>

21	
22		while (input != -1)
   0x00000000004006f2 <+124>:	jmpq   0x40079e <main+296>
   0x000000000040079e <+296>:	movzbl -0x21(%rbp),%eax
---Type <return> to continue, or q <return> to quit---
   0x00000000004007a2 <+300>:	cmp    $0xff,%al
   0x00000000004007a4 <+302>:	jne    0x4006f7 <main+129>

23		{
24			end -> value = input;
   0x00000000004006f7 <+129>:	movzbl -0x21(%rbp),%edx
   0x00000000004006fb <+133>:	mov    -0x8(%rbp),%rax
   0x00000000004006ff <+137>:	mov    %dl,(%rax)

25	
26			end -> next = (Node *) malloc (sizeof(Node)*1);
   0x0000000000400701 <+139>:	mov    $0x10,%edi
   0x0000000000400706 <+144>:	callq  0x400560 <malloc@plt>
   0x000000000040070b <+149>:	mov    %rax,%rdx
   0x000000000040070e <+152>:	mov    -0x8(%rbp),%rax
   0x0000000000400712 <+156>:	mov    %rdx,0x8(%rax)

27			end -> next -> value = 0;
   0x0000000000400716 <+160>:	mov    -0x8(%rbp),%rax
   0x000000000040071a <+164>:	mov    0x8(%rax),%rax
   0x000000000040071e <+168>:	movb   $0x0,(%rax)

28			end -> next -> next  = NULL;
   0x0000000000400721 <+171>:	mov    -0x8(%rbp),%rax
   0x0000000000400725 <+175>:	mov    0x8(%rax),%rax
   0x0000000000400729 <+179>:	movq   $0x0,0x8(%rax)

29	
30			fprintf(stdout, "Enter a value (-1 to complete): ");
   0x0000000000400731 <+187>:	mov    0x2005d8(%rip),%rax        # 0x600d10 <stdout@@GLIBC_2.2.5>
   0x0000000000400738 <+194>:	mov    %rax,%rcx
   0x000000000040073b <+197>:	mov    $0x20,%edx
   0x0000000000400740 <+202>:	mov    $0x1,%esi
   0x0000000000400745 <+207>:	mov    $0x400918,%edi
   0x000000000040074a <+212>:	callq  0x400570 <fwrite@plt>

31			fscanf(stdin, "%hhd", &input);
   0x000000000040074f <+217>:	mov    0x2005c2(%rip),%rax        # 0x600d18 <stdin@@GLIBC_2.2.5>
   0x0000000000400756 <+224>:	lea    -0x21(%rbp),%rdx
   0x000000000040075a <+228>:	mov    $0x400939,%esi
   0x000000000040075f <+233>:	mov    %rax,%rdi
   0x0000000000400762 <+236>:	mov    $0x0,%eax
   0x0000000000400767 <+241>:	callq  0x400530 <__isoc99_fscanf@plt>

32	
33			if (input == -1)
   0x000000000040076c <+246>:	movzbl -0x21(%rbp),%eax
   0x0000000000400770 <+250>:	cmp    $0xff,%al
   0x0000000000400772 <+252>:	jne    0x400792 <main+284>
---Type <return> to continue, or q <return> to quit---

34			{
35				free(end -> next);
   0x0000000000400774 <+254>:	mov    -0x8(%rbp),%rax
   0x0000000000400778 <+258>:	mov    0x8(%rax),%rax
   0x000000000040077c <+262>:	mov    %rax,%rdi
   0x000000000040077f <+265>:	callq  0x400520 <free@plt>

36				end -> next = NULL;
   0x0000000000400784 <+270>:	mov    -0x8(%rbp),%rax
   0x0000000000400788 <+274>:	movq   $0x0,0x8(%rax)
   0x0000000000400790 <+282>:	jmp    0x40079e <main+296>

37			}
38			else
39				end = end -> next;
   0x0000000000400792 <+284>:	mov    -0x8(%rbp),%rax
   0x0000000000400796 <+288>:	mov    0x8(%rax),%rax
   0x000000000040079a <+292>:	mov    %rax,-0x8(%rbp)

40		}
41	
42		// Display list from start to end
43	
44		fprintf(stdout, "Enter value for new node: ");
   0x00000000004007aa <+308>:	mov    0x20055f(%rip),%rax        # 0x600d10 <stdout@@GLIBC_2.2.5>
   0x00000000004007b1 <+315>:	mov    %rax,%rcx
   0x00000000004007b4 <+318>:	mov    $0x1a,%edx
   0x00000000004007b9 <+323>:	mov    $0x1,%esi
   0x00000000004007be <+328>:	mov    $0x40093e,%edi
   0x00000000004007c3 <+333>:	callq  0x400570 <fwrite@plt>

45		fscanf(stdin, "%hhd", &input);
   0x00000000004007c8 <+338>:	mov    0x200549(%rip),%rax        # 0x600d18 <stdin@@GLIBC_2.2.5>
   0x00000000004007cf <+345>:	lea    -0x21(%rbp),%rdx
   0x00000000004007d3 <+349>:	mov    $0x400939,%esi
   0x00000000004007d8 <+354>:	mov    %rax,%rdi
   0x00000000004007db <+357>:	mov    $0x0,%eax
   0x00000000004007e0 <+362>:	callq  0x400530 <__isoc99_fscanf@plt>

46	
47		tmp = (Node *) malloc (sizeof(Node));
   0x00000000004007e5 <+367>:	mov    $0x10,%edi
   0x00000000004007ea <+372>:	callq  0x400560 <malloc@plt>
   0x00000000004007ef <+377>:	mov    %rax,-0x18(%rbp)

48		tmp -> value = input;
   0x00000000004007f3 <+381>:	movzbl -0x21(%rbp),%edx
   0x00000000004007f7 <+385>:	mov    -0x18(%rbp),%rax
---Type <return> to continue, or q <return> to quit---
   0x00000000004007fb <+389>:	mov    %dl,(%rax)

49		tmp -> next = NULL;
   0x00000000004007fd <+391>:	mov    -0x18(%rbp),%rax
   0x0000000000400801 <+395>:	movq   $0x0,0x8(%rax)

50	
51		fprintf(stdout, "Enter value of node you want to insert new node before: ");
   0x0000000000400809 <+403>:	mov    0x200500(%rip),%rax        # 0x600d10 <stdout@@GLIBC_2.2.5>
   0x0000000000400810 <+410>:	mov    %rax,%rcx
   0x0000000000400813 <+413>:	mov    $0x38,%edx
   0x0000000000400818 <+418>:	mov    $0x1,%esi
   0x000000000040081d <+423>:	mov    $0x400960,%edi
   0x0000000000400822 <+428>:	callq  0x400570 <fwrite@plt>

52		fscanf(stdin, "%hhd", &input);
   0x0000000000400827 <+433>:	mov    0x2004ea(%rip),%rax        # 0x600d18 <stdin@@GLIBC_2.2.5>
   0x000000000040082e <+440>:	lea    -0x21(%rbp),%rdx
   0x0000000000400832 <+444>:	mov    $0x400939,%esi
   0x0000000000400837 <+449>:	mov    %rax,%rdi
   0x000000000040083a <+452>:	mov    $0x0,%eax
   0x000000000040083f <+457>:	callq  0x400530 <__isoc99_fscanf@plt>

53	
54		tmp2 = start;
   0x0000000000400844 <+462>:	mov    -0x20(%rbp),%rax
   0x0000000000400848 <+466>:	mov    %rax,-0x10(%rbp)

55		while (tmp2 -> next -> value != input)
   0x000000000040084c <+470>:	jmp    0x40085a <main+484>
   0x000000000040085a <+484>:	mov    -0x10(%rbp),%rax
   0x000000000040085e <+488>:	mov    0x8(%rax),%rax
   0x0000000000400862 <+492>:	movzbl (%rax),%edx
   0x0000000000400865 <+495>:	movzbl -0x21(%rbp),%eax
   0x0000000000400869 <+499>:	cmp    %al,%dl
   0x000000000040086b <+501>:	jne    0x40084e <main+472>

56			tmp2 = tmp2 -> next;
   0x000000000040084e <+472>:	mov    -0x10(%rbp),%rax
   0x0000000000400852 <+476>:	mov    0x8(%rax),%rax
   0x0000000000400856 <+480>:	mov    %rax,-0x10(%rbp)

57	
58		tmp  -> next = tmp2 -> next;
   0x000000000040086d <+503>:	mov    -0x10(%rbp),%rax
   0x0000000000400871 <+507>:	mov    0x8(%rax),%rdx
   0x0000000000400875 <+511>:	mov    -0x18(%rbp),%rax
   0x0000000000400879 <+515>:	mov    %rdx,0x8(%rax)

---Type <return> to continue, or q <return> to quit---
59		tmp2 -> next = tmp;
   0x000000000040087d <+519>:	mov    -0x10(%rbp),%rax
   0x0000000000400881 <+523>:	mov    -0x18(%rbp),%rdx
   0x0000000000400885 <+527>:	mov    %rdx,0x8(%rax)

60	
61		// Display list from start to end
62	
63		return(0);
   0x0000000000400889 <+531>:	mov    $0x0,%eax

64	}
   0x000000000040088e <+536>:	leaveq 
   0x000000000040088f <+537>:	retq   

End of assembler dump.

Click Image for full view CheatSheet `

7 October 2014

swap node

1.bmp

Bad!
badswapnode.c
Node *tmp3 = mknode(tmp->value);
tmp->value=tmp2->value;
tmp2->value=tmp3->value;
free(tmp3);
good!

2.bmp

Obtain node

Pulls node from list, patches hole in list, keeps pulled node. 3.bmp

obtain_1.c
myList = obtain(myList, &tmp)
{
    int pos       = getpos(myList, &tmp);
    Node          *tmp2;
    tmp2          = setpos(myList, pos-1);
    tmp2->next    = tmp->next;
 
    *(tmp)->next  = NULL;
 
    myList->qty--;
 
    return(myList);
}
obtain_1_optimized.c
myList = obtain(myList, &tmp)
{
    Node *tmp     = setpos(myList, getpos(myList, tmp)-1);
    tmp2->next    = tmp->next;
 
    *(tmp)->next  = NULL;
 
    myList->qty--;
 
    return(myList);
}

4.bmp

use.c
myList = obtain(mylist, &tmp);
Implementation tips
(*tmp)->value

Misc. Notes

Obtain is the only function in our linkedlist library where we will pass by value;

Passing variables
  1. Pass by value
    • Passes copy
    • myList=insert(myList,tmp,tmp2);
  2. Pass by address/reference
    • changes happen outside of the function
    • pointers!

9 October 2014

Dry Erase Templates

4 November 2014

Stacks

Vocab
  • Unbounded
    • Unlimited in size
  • Bounded
    • Limited in size
  • Stack Overflow
    • Adding more than the stack allows
  • Stack Underflow
    • Removing more than there is on the stack (“negative”)
Functions
  1. push
    • Add to stack
  2. pop
    • Remove from stack
  3. peek
    • look at the top
  4. isempty
    • is the list empty, used, or broke?
  5. mkstack
    • make stack
  6. cpstack
    • copy stack
  7. rmstack
    • remove stack
Misc.
  1. qty
    • This asshole is back.
  2. size
    • Maximum size of stack
    • 0 = infinite size.
    • int = max size
    • negative = error
Pictures!

This is an example stack:

This is our blank stack struct:

Blank stack template:

11 November 2014

Portfolio

Please note that these are old and may not be current or even correct at this point.

opus/fall2014/mgardne8/start.txt · Last modified: 2014/12/21 11:16 by 127.0.0.1