Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Part 2======

=====Entries=====

====October 4, 2011====
I got an array based stack implemented. Looking at the implementation on wikipedia was a bit confusing. I had some problems getting it to compile and to some degree it could be hard to follow So, in the end, I just decided  on my own implementation. Surprisingly, the array based stack seemed more difficult to write than the linked list based stack. This is probably because most of the grunt work in the linked list based stack gets done in the linked list class. With the array I had to start from scratch. Also, with the linked list version, whenever you push onto the stack, you're just creating a new start. In the array version, you need to move all the elements up the stack and then you can add the new value. Similarly, when you pop a value off, you shit all of other values down by one. The only thing I question at this point is manually setting the value of top to 0  after declaring and allocating memory for the stack. I'm sure there's a better way to do it. The compiler wasn't very happy when I initialized it within the struct. I'll do some snooping around.

====October 14, 2011====
So, I've done a struct based linked list. A less OO approach to it I guess is what I should say. However, I've run into a problem with deleting nodes. The rest of the functionality seems to work fine. It appears that delete, in its entirety, is broken. Upon trying to delete a node in the middle of the list a -1 is returned from the delete function, an error status. ...okay, now I'm upset. I'm pretty certain I found it. After beating my head over it most of Friday evening, I found it. The whole purpose of this entry was to help track down there error by logging its behavior. Well, I guess it worked. However, I won't bet that it works 100% just yet. Tests are required. Horrible tests. Okay, test one: delete node from the middle of the list is successful. Now let us try to delete from the beginning of the list. And failure... Loose ends apparently aren't tied up. After deleting node 0 and trying to retrieve the value of the new node 0 we get seg fault hell. Okay, before doing anything else let us try deleting from the last node in the list. Everything here acts okay UNLESS you make an attempt to access the node that was deleted. IE if you have 3 nodes and you delete the last node, node 2 and then you try to access that node. Comparing my code to the code we originally wrote in class, the only difference that I see is the order that some of the things are done. I can't imagine that this should matter though. I'll try it anyway. Just not right now as class will be starting in a few minutes. I require snacks!
 
====October 24, 2011====
Somehow I end up doing one of these every ten days. Strange... I finished the link list library. I might throw in some added functionality in the future. For right now I've got the following functions: create, append, insert, deleteNode, deleteList, getLength, getValue, and copy. The linked list library in Java has functionality to dump the values of list into an array. I may or may not add that in the future. It could be useful. I think from here, I'm going to start working on the stack library. I'll use the java library as guide. It doesn't seem have a lot of extra functionality. One of the functions already exists in my linked list library, the search function.  It also has a function to check if the stack is empty which wouldn't be very hard to implement.  Other than that it just has your standard p functions: push, pop, and peek. 

I'm a bit stuck on the upgrade to the jumble solver. Once it does the final check on the two strings, it always says the two strings are unequal. I've done some debugging on it. I've printed out and compared the entire strings and I've checked them character by character and it can still show them as equal but it never executes the if statement. My only guess is that it reads past the null terminator and keeps comparing. I have no idea how to fix that, though. Not yet, anyway.
====October 31, 2011====
Well, there's no October 34 and even if there was the opus is due tomorrow so that means i'm here tonight. I've been doing quite a bit of playing lately. My linked list based stack has been giving me some problems. I think I may be having some issues with naming conventions. I'm not really sure exactly how I should structure it. Chances are I'm making too big of a deal out of things. Really, a stack is nothing more than a special case linked list. My original thought was to simply have a line that defines List as Stack. I've been working through the examples in chapter 7 of the systems programming book. It gets into creating a pong type game using the curses library. This is very much like what I've been playing with in python. It'll be neat to see similarities and differences between the two implementations. 
=====data Topics=====

====Stacks (array-based, linked-list based)====
=== Linked List Based ===
Think of a linked list based stack as a vertical linked list. Every time a new value is added to the stack, you "slide" it under the the previous value in the stack. Lets say that we want to create a stack and place the values 1, 2, 3, 4 onto the stack. Each time we add a new value, it would look as follows. 

            [4]
        [3] [3]
    [2] [2] [2]
[1] [1] [1] [1]

The difference between a linked list based stack and an array based stack is that we don't necessarily know ahead of time how big our stack must be. For instance, if we want to test a string to see if it is a palindrome. We move each character to the stack, pull them off the stack and compare.

=== Array Based ===
In an array based list, the bottom of the list is at list[0] and the top of the list would be at list[size - 1]. Size is whatever the length of the list is. Think of this like a character string. The array of characters can be of any length but the null terminator, \0, can bee used as a means of stopping. In our case size works like the null terminator, a means of stopping in our list. 
<code c>
#include <stdio.h>
#define STACK_SIZE 50

struct Stack {
	int values[STACK_SIZE]; //The stack
	int top;				//Pos of the top of the stack
};
typedef struct Stack Stack;

int push(Stack*, int);
int pop(Stack*);
int peek(Stack*);

int main()
{
	Stack *stack;
	int input;
	
	//Allocate memory for our stack and initialize top
	stack = (Stack*) malloc(sizeof(Stack));				
	stack -> top = 0;
	
	//Get some input and store it on the stack
	printf("Enter a number (-1 to quit): ");
	scanf("%d", &input);
	
	while (input != -1 && stack -> top <= STACK_SIZE) {
		push(stack, input);
		printf("Enter a number (-1 to quit): ");
		scanf("%d", &input);
	}
	
	//Peek at the top of the stack
	printf("Top of the stack: %d\n\n", peek(stack));
	
	//Pop the contents of the stack and print them
	while (stack -> top > 0) {
		printf("%d\n", pop(stack));
	}
	
	return 0;
}

int push(Stack *sp, int val)
{
	/*Push values onto the stack. If the stack
	size is reached return a -1, otherwise
	return 0.*/
	int x;
	
	if (sp -> top > STACK_SIZE) { //Our stack has reached its size limit
		fprintf(stderr, "Stack full!\n");
		return -1;
	} else if (sp -> top == 0) { //The stack is empty
		//Move val onto the stack
		sp -> values[0] = val; 
		//increment the top of the stack
		sp -> top++;		   
		return 0;
	} else {	//Our stack is still growing
		for (x = sp -> top; x >= 0; x--)
			//Push all the values on the stack up by one
			sp -> values[x + 1] = sp -> values[x]; 
		//Push val onto the stack
		sp -> values[0] = val;	
		//Incrememnt the top of the stack
		sp -> top++;
		return 0;
	}
}

int pop(Stack *sp)
{
	/*(Pop values from the stack. If the stack
	reaches 0, return a -1, otherwise return the
	value from the bottom of the stack.*/
	int val, x;
	
	//pull the bottom value from the stack
	val = sp -> values[0];
	
	if (sp -> top == 0) { //Stack is now empty
		fprintf(stderr, "Stack empty!\n");
		return -1;
	} else { //The stack is not empty
	for (x = 0; x < sp -> top; x++)
		//Pull all the values down the stack by one
		sp -> values[x] = sp -> values[x + 1];
	//Decrememnt the top of the stack
	sp -> top--;
	
	return val;
	}
}

int peek(Stack *sp)
{
	//Returns the value at the top of the stack
	
	return sp -> values[sp -> top - 1];
}
</code>
====Pushing====
Pushing involves adding a new value to stack and "Push" any other items to higher positions on the stack. 
<cli>
lab46:~$ ./arrayStack
Enter a number (-1 to quit): 1
Enter a number (-1 to quit): 2
Enter a number (-1 to quit): 3
Enter a number (-1 to quit): 4
Enter a number (-1 to quit): 5
Enter a number (-1 to quit): -1
Top of the stack: 1
</cli>
Here we push the values 1 through 5 onto the stack. After we've done this, using the peek function we print the value at the top of the stack.

<code c>
for (x = sp -> top; x >= 0; x--)
	//Push all the values on the stack up by one
	sp -> values[x + 1] = sp -> values[x]; 
	//Push val onto the stack
	sp -> values[0] = val;	
</code>
Here's where most of the work is done when we push a value to the stack. We move all of the values on the stack up one position and then insert the new value at position 0 of the array.

If we were using a linked list, when we push an item onto the stack, we would create a new node. This node would become the new start who's prev will be pointing to NULL and who's next will be pointing to the previous start.
====Popping====
Popping, as expected, is the opposite of pushing. We get the value from the bottom of the stack and then we shift every other value down one position. 
<code c>
for (x = 0; x < sp -> top; x++)
		//Pull all the values down the stack by one
		sp -> values[x] = sp -> values[x + 1];
</code>

Fully demonstrating the array based stack program with the below example. 
<cli>
lab46:~$ ./arrayStack
Enter a number (-1 to quit): 1
Enter a number (-1 to quit): 2
Enter a number (-1 to quit): 3
Enter a number (-1 to quit): 4
Enter a number (-1 to quit): 5
Enter a number (-1 to quit): -1
Top of the stack: 1

5
4
3
2
1
</cli>

In a linked list based stack, when we pop an item off the stack, we would set our temp to start and start to temp's next. Then temp's prev would be set to NULL and temp would be de-allocated.
====Top====
Top refers to the top of a stack. The top of the stack is simply the entry or exit for any data being pushed onto the stack. Whenever some piece of data is first pushed onto to the stack, it is considered to be at the top. No item can be popped from the stack unless it is at the top. Similarly, no item can be pushed onto the stack without, first, being at the top position.

====Overflow condition====
Whenever a stack becomes full and no more data can be pushed onto the stack, this is referred to as an overflow condition or overflow state.
<code c>
#include <stdio.h>
#include "ArrayStack.h"

int main()
{
	int i;
	Stack *myStack;
	
	for (i = 0; i < 55; i++) {
		if (i < STACK_SIZE) {
			push(myStack, i + 1);
			printf("%d pushed to stack\n", i + 1);
		}
		else 
			printf("Stack overflow state!\n");
	}
	
	return 0;
}
</code>
As can be seen below, the code attempts to push 55 objects onto the stack. The problem is that the stack can only hold 50 items. The last 5 will reach an overflow state and not be added.
<cli>
stackOverflow.exe
Process started >>>
1 pushed to stack
2 pushed to stack
3 pushed to stack
4 pushed to stack
5 pushed to stack
6 pushed to stack
7 pushed to stack
8 pushed to stack
9 pushed to stack
10 pushed to stack
11 pushed to stack
12 pushed to stack
13 pushed to stack
14 pushed to stack
15 pushed to stack
16 pushed to stack
17 pushed to stack
18 pushed to stack
19 pushed to stack
20 pushed to stack
21 pushed to stack
22 pushed to stack
23 pushed to stack
24 pushed to stack
25 pushed to stack
26 pushed to stack
27 pushed to stack
28 pushed to stack
29 pushed to stack
30 pushed to stack
31 pushed to stack
32 pushed to stack
33 pushed to stack
34 pushed to stack
35 pushed to stack
36 pushed to stack
37 pushed to stack
38 pushed to stack
39 pushed to stack
40 pushed to stack
41 pushed to stack
42 pushed to stack
43 pushed to stack
44 pushed to stack
45 pushed to stack
46 pushed to stack
47 pushed to stack
48 pushed to stack
49 pushed to stack
50 pushed to stack
Stack overflow state!
Stack overflow state!
Stack overflow state!
Stack overflow state!
Stack overflow state!
</cli>

====Underflow State====
An underflow state is the opposite of an overflow. With an underflow, there are no more data left on the stack to manipulate, yet we may be trying to perform a pop operation. 
====LIFO or FIFO====
LIFO refers to Last In First Out. This is usually used in conjunction with with stacks. There is only one entrance or exit to a stack. So, if you were to push 1, 2, 3, 4, 5 to a stack the last in would be the first out, 1. 

FIFO refers to First In First Out. FIFO is usually used with queues. In a queue there is an entrance at the beginning and an exit at the end. Unlike stacks where the entrance and exit are the same point. Again, using 1 2 3 4 5 as an example. The first in would be 5, and therefore the first out.

====Queues: Array Based Vs Linked List Based====
Queues are much like stacks but with a few important differences. First, a stack grows up queues grow out. When you think of queues, imagine that really big line at the Wal-Mart check out because the geniuses decided to only have 2 registers open out of about 14. The first one into the line will be the first one out. 

In an array based queue, once you have x many items on your queue, you have the ability to dequeue them. When you dequeue them, the idea will be to keep track of how many items are on the queue. So, again, if we have x items and we perform a dequeue operation, we will have x - 1 items on the list. We won't actually remove the dequeued item, however, right now we will decrease our queue size. This can be thought of like a string. There may be information after our null terminator, but we don't care about that so the null terminator stops us from accessing it.

<code c>
//future code to be added
</code>

A linked list based queue would be very similar however, there will be one major difference. Here, we're not limited to a certain size like we are with an array. We can make our queue grow and shrink as we please. Much like how we made our stack grow and shrink. In our array based queue, we did not delete data as we popped it off. With a linked list based queue, we have the ability to delete data once we're done with it.
====Enqueing====
Enqueing information to a queue is identical to a push operation on a stack. When using an array, all the elements will get moved up one position in the array and then the new data will be added to the beginning of the queue. With a linked list queue, simply add a new node to the beginning of the list and move the data into it.
====Dequeuing====
Dequeuing is the act of removing some piece of data from a queue. Since a queue, is first in first out, the oldest piece of data on the queue is what will get dequeued. With an array queue , an index or a pointer is needed to keep track of the end of the queue. Once the data is dequeued, that index or pointer will be decremented. In a linked list queue, once the data has been dequeued simply delete the final node in the list.
====Overrun and Underrun conditions====
An ovverrun condition occurs when trying to enqueue data onto a queue that is already full. This would really only be a problem with an array based queue since a linked list can grow or shrink as needed. An underrun condition  will occur when trying to dequeue a queue with no data on it. Again, this would only be an issue with an array based stack.
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "ArrayStack.h"

int main()
{
	int i;
	Stack *myStack;
	
	myStack = (Stack*) malloc(sizeof(Stack));
	myStack -> top = 0;
	
	for (i = 0; i < STACK_SIZE; i++)
		push(myStack, i * 2);
	
	for (i = STACK_SIZE; i > -5; i--)
		printf("%d\n", pop(myStack));
		
	return 0;
}
</code>
<cli>
lab46:~$ ./stackUnderflow
98
96
94
92
90
88
86
84
82
80
78
76
74
72
70
68
66
64
62
60
58
56
54
52
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
Stack empty!
-1
Stack empty!
-1
Stack empty!
-1
Stack empty!
-1
Stack empty!
-1

</cli>
====LIFO or FIFO====
LIFO refers to Last In First Out. This is usually used in conjunction with with stacks. There is only one entrance or exit to a stack. So, if you were to push 1, 2, 3, 4, 5 to a stack the last in would be the first out, 1.

FIFO refers to First In First Out. FIFO is usually used with queues. In a queue there is an entrance at the beginning and an exit at the end. Unlike stacks where the entrance and exit are the same point. Again, using 1 2 3 4 5 as an example. The first in would be 5, and therefore the first out.

=====sysprog Topics=====

====Device Files====
In UNIX, devices all have an associated file. Devices can be written to and read from just like a file. Every device has a filename, an inode number, an owner, permissions, and a time that it was last modified. However, every device does not necessarily support every file operation. For instance a mouse file does not support the write system call and a terminal does not support lseek.
====Race Condition====
A race condition is a big problem in systems programming.  A race condition occurs when a record gets overwritten and is lost due to timing issues. Lets say that two users are about to write to the same file. The first person seeks the end of file and then it is the second user's slice of time and they seek the end of file. Now the first person write to their EOF position. Once they're done the second user writes to their EOF position which happens to be the sames as the first person's.

Another possible race condition is a file being created at the same time by two different user. Combining the O_CREAT and O_EXCL flags into an atomic operation is supposed to clear up this condition. However, this doesn't work 100% of the time.
====Atomic Operation====
lseek and write are two separate processes, which the kernel is free to interrupt in between the two. When the O_APPEND flag is set the kernel combines these two into a single operation called an atomic operation.
====Streams====
The basic idea of the streams model of data flow is that the data will be processed in some order. However, any module in this process can be removed or disabled. If what your terminal driver supports is not to your liking, it is possible to write and install your own modules. You write your new module to the specifications of STREAMS. Then you would use certain system calls to install it where you like.
====Connection Control====
Connection control refers to how one may interface with a device such as the terminal. Connections to devices share similarities with to connections to disk files. Both can be interacted with using standard file system calls such as open, read, write, close, and lseek. File permissions control access to these devices the same way they would disk files.

====Blocking Vs Nonblocking Input====
Blocking input occurs when canf() or getchar() are called. After they're called, the program will come to a halt until it gets what it wants, data entered into the keyboard. Blocking is a property of any open file which can be turned off by using fcntl() or open() to turn on the O_NDELAY or the O_NONBLOCK flag for the file descriptor. Once blocking has been disabled,  it is possible to enter input into the keyboard without pressing the enter key.

====Singals====
Signals are small messages that sent from the kernel to a running process.  Think of it like a criminal way back when running off and a cop blows their whistle. If your program does something you don't want it to, you blow your whistle to tell it to halt. The process can tell the kernel how it wants to respond when it receives a signal. 

<code c>
#include <signal.h>
#include <stdlib.h>                                                                                                                                          

int main()
{
    void f(int);
    int i;

    signal(SIGINT, f); 

    for (i = 0; i < 10; i++) {
        printf("hello\n");
        sleep(1);
    }   

    return 0;
}

void f(int signum)
{
    char choice;

    printf("Interrupted! Quit y/n?");
    scanf("%c", &choice);

    if (choice == 'y' || choice == 'Y')
        exit(1);
}
</code>
<cli>
lab46:~/c_programs$ ./sigmdemo
hello
^CInterrupted! Quit y/n?N
hello
hello
^CInterrupted! Quit y/n?hello
hello
hello
^CInterrupted! Quit y/n?y
lab46:~/c_programs$
</cli>
====Event Driven Programming====
Event driven programming involves writing programs which rely on actions that are not necessarily "scripted". A good example would be the commands entered into the Vi Editor. When you press i to enter insert mode, an event has occurred. 

====Alarms/Timers====
An alarm counts down from a specified time and sends the SIGALRM signal to the process when the timer reaches 0. 
<code c>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>

int main(int argc, char **argv)
{
	void wakeUp(int);
	int i;
	
	if (argc != 2) {
		exit(0);
	} else {
		i = atoi(argv[1]);
		printf("Sleeping for %d seconds.\n", i);
		signal(SIGALRM, wakeUp);
		alarm(i);
		pause();
	}
	
	return 0;
}

void wakeUp(int i)
{
		printf("Waking up...\n");
}
</code>
<cli>
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ ./alarm 5
Sleeping for 5 seconds.
Waking up...
</cli>

====Reentrant code, critical sections====
A function is reentrant if it can be called when it is already active and will not cause problems. It can be interrupted during its execution and called again safely before the previous version of it completes executing. Once the new version finishes its execution the previous version will correctly finish its execution. 

A critical section is a piece of code that is accessing a shared resource, a list or a stack, if interruptions occur bad data is produced. In other words the data structure cannot be accessed concurrently. 
====Asynchronous IO====
With asynchronous IO, other processes are permitted to finishing processing before the transmission has finished. A signal will be sent when the input arrives and it will be possible to do other things until a signal arrives to alert that input is available. 


====Terminal Control and Signals====
A signal is a way of flagging down a process because a certain occurred. For instance, we may want to perform some certain action when the user presses CTRL-C and sends an interrupt signal. UNIX contains several signals for various purposes. kill -l displays all of the different signals on a UNIX system.
<cli>
brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ kill -l
 1) SIGHUP	 2) SIGINT	 3) SIGQUIT	 4) SIGILL	 5) SIGTRAP
 6) SIGABRT	 7) SIGBUS	 8) SIGFPE	 9) SIGKILL	10) SIGUSR1
11) SIGSEGV	12) SIGUSR2	13) SIGPIPE	14) SIGALRM	15) SIGTERM
16) SIGSTKFLT	17) SIGCHLD	18) SIGCONT	19) SIGSTOP	20) SIGTSTP
21) SIGTTIN	22) SIGTTOU	23) SIGURG	24) SIGXCPU	25) SIGXFSZ
26) SIGVTALRM	27) SIGPROF	28) SIGWINCH	29) SIGIO	30) SIGPWR
31) SIGSYS	34) SIGRTMIN	35) SIGRTMIN+1	36) SIGRTMIN+2	37) SIGRTMIN+3
38) SIGRTMIN+4	39) SIGRTMIN+5	40) SIGRTMIN+6	41) SIGRTMIN+7	42) SIGRTMIN+8
43) SIGRTMIN+9	44) SIGRTMIN+10	45) SIGRTMIN+11	46) SIGRTMIN+12	47) SIGRTMIN+13
48) SIGRTMIN+14	49) SIGRTMIN+15	50) SIGRTMAX-14	51) SIGRTMAX-13	52) SIGRTMAX-12
53) SIGRTMAX-11	54) SIGRTMAX-10	55) SIGRTMAX-9	56) SIGRTMAX-8	57) SIGRTMAX-7
58) SIGRTMAX-6	59) SIGRTMAX-5	60) SIGRTMAX-4	61) SIGRTMAX-3	62) SIGRTMAX-2
63) SIGRTMAX-1	64) SIGRTMAX	
</cli>

=====data Objective=====
====Objective====
Compare and contrast the costs and benefits of dynamic and static data structure implementations. Discuss the trade offs between linked list based data structures and array based data structures. 

===Method===
I'm going to discuss some of the similarities and differences between the two types of data structures, statically allocated and dynamically allocated, along with their advantages and disadvantages.
===Measurement===
With static allocation, using array based stacks and queues, the data structure is allocated when the program begins execution. Because of this the size of the data structure must be known ahead of time. This means that the data structure can only grow to a certain size. However, it does means that all of the values in the data structure are adjacent in memory which gives a boost in performance vs dynamic allocation. 

In dynamic allocation, a linked list based data structure, memory is allocated for the structure during execution. We don't need to know how many elements our structure will have. It could have 10 elements or it could have 100 or even 1000 or more. However, on the down side, the values are not stored adjacently in memory which means there's no straight path through the list. This would be like walking to a store that's down the street but instead of going straight down the street you take several turns before you get there. 

===Analysis===
It would help to have some data on how much of a time gap there is between statically allocated structures and dynamically allocated structures. This, indeed, sounds like  an experiment. That's our next step.
=====sysprog Objective=====
====Objective====
design programs that handle signals

===Method===
I have a program that when you press CTRL-C it grabs the SIGINT and asks the user if they really want to quit.

===Measurement===
<code c>
#include <signal.h>
#include <stdlib.h>                                                                                                                                          

int main()
{
    void f(int);
    int i;

    signal(SIGINT, f); 

    for (i = 0; i < 10; i++) {
        printf("hello\n");
        sleep(1);
    }   

    return 0;
}

void f(int signum)
{
    char choice;

    printf("Interrupted! Quit y/n?");
    scanf("%c", &choice);

    if (choice == 'y' || choice == 'Y')
        exit(1);
}
</code>
<cli>
lab46:~/c_programs$ ./sigmdemo
hello
^CInterrupted! Quit y/n?N
hello
hello
^CInterrupted! Quit y/n?hello
hello
hello
^CInterrupted! Quit y/n?y
lab46:~/c_programs$
</cli>

===Analysis===
I could have added more signals into the program. Implementing a new action depending on the signal given. It wouldn't be hard to implement. It would only need a few additional callbacks to handle the additional signals. I would alter it to incorporate two or more signals and perform different operations depending on the signal that is received.
=====Experiments=====
====Experiment 1====

===Question===
Is the executable file using the std namespace larger than an executable file that omits and instead prepends std:: when necessary? This is under the assumption that using the namespace pulls in more code than not using it.

===Resources===
[[http://www.cplusplus.com/forum/beginner/14325/]]
[[http://www.cplusplus.com/forum/beginner/9181/]]

As far as I can tell it's more of a problem having multiple objects being referred to by the same name rather than the size of a program.

===Hypothesis===
From what I've read, my original thought was wrong. It's simply a naming convention issue. The size of the executable should not be affected by using or not using a namespace.

Judging from the above links, the objects will all still be present in the executable, however, their scope will be different depending on whether the programmer decides to use or not use the namespace. This means the actual file size should not be affected.

===Experiment===
I'm going to write a hello, world program in C++, first, without including the std namespace. I'll compile it and do an ls -lh to get the size of the executable. Then I will rewrite the program to include the namespace and, again, do an ls -lh to get the size of the executable and compare the two of them.

===Data===
==Without including the std namespace==
<cli>
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ ls -lh | grep 'namespaceTest'
-rwxr-xr-x 1 brad brad 7.7K 2011-10-27 12:31 namespaceTest
</cli>
===Including the std namespace===
<cli>
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ ls -lh | grep 'namespaceTest'
-rwxr-xr-x 1 brad brad 7.7K 2011-10-27 12:59 namespaceTest
</cli>
===Analysis===
Based on the data collected:

  * yes, the hypothesis was correct.
  * There does not seem to be more going on than originally thought.
  * I may want to try something bigger than hello, world. I could write a program that also uses stdio and file io to use more than just cout and endl.
  * using the -h argument to ls makes the file size human readable at a kb level. I could have left that off to get the actual number of bytes, which would show even a slight difference in the file size.


===Conclusions===
Using the std namespace may not give you a huge executable incorporating things that you never use, however, it can cause variable or function names to butt heads". myNamespace::x and x aren't the same thing but x and x are, which would certainly cause problems.
====Experiment 2====

===Question===
When working with large data structures, is there a large gap in execution time between statically allocation and dynamic allocation?

===Resources===
Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

===Hypothesis===
Considering that there is not a straight path from value to value in memory with dynamic allocation, when working with larger structures there should be a noticeable time difference when compared with a statically allocated structure of the same size.
===Experiment===
I'm going to create two different programs. One program will contain an array with 1024 integer elements that will be populated using a for loop. The other program will contain a linked list containing 1024 integer elements that will also be populated using a for loop.  I will use the unix time utility to record each program's execution time and compare the times of each program. 

===Data===
==Static Allocation==
<code c>
int main()
{
	int intArray[1024], i;
	
	for (i = 0; i < 1024; i++) {
		intArray[i] = i + 1;
	}
	
	return 0;
}
</code>
<cli>
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ time ./staticTest

real	0m0.001s
user	0m0.000s
sys	0m0.000s
</cli>
==Dynamic Allocation==
<code c>
#include "List.h"

int main()
{
	List *myList;
	int i;
	
	myList = create();
	
	for (i = 0; i < 1024; i++) {
		appendToList(myList, i + 1);
	}
	
	return 0;
}
</code>
<cli>
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs/LinkedList$ time ./dynamicTest

real	0m0.002s
user	0m0.000s
sys	0m0.000s
</cli>

===Analysis===
Based on the data collected:

Using the linked list did take longer than the array as expected. However, the time was very small. I would like to add a few things to see the difference in execution time over different intervals. I would document that difference in times over different allocation sizes. Starting with 1000 elements moving to 10000 elements in intervals of 1000 elements. This would give a much better idea as to the difference in execution time.
===Conclusions===
What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.
====Retest====
===State Experiment===
I'm retesting Nick Sano's void pointer experiment. Is it possible to use a void pointer to pointer to a char and then to point to an int?

===Resources===
Nick seems to have a pretty good idea on void pointers. However, it is not possible to dereference a void pointer.
http://stackoverflow.com/questions/692564/concept-of-void-pointer-in-c-programming

===Hypothesis===
Nick believes that a void pointer could be used so that it would not be necessary to declare a pointer of a certain type. Yes, I do believe that his hypothesis is adequate in what he's attempting to discover.

  * Do you feel their hypothesis is adequate in capturing the essence of what they're trying to discover?
  * What improvements could you make to their hypothesis, if any?

===Experiment===
I would have been a little more specific. I think what Nick was shooting for was to try, for example, to replace the int value in our node structure with a generic void pointer and change it depending on what type of data we'd like to put in our node structure. However, this is not entirely clear.
===Data===
Publish the data you have gained from your performing of the experiment here.

===Analysis===
<code c>
int main()
{
    void *vPtr;
    int i = 25; 
    char c = '#';

    vPtr = (int*)&i;
    vPtr = (char*)&c;                                                          

    return 0;
}
</code>
<cli>
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ gcc voidPointer.c -o voidPointer
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ 
</cli>
Again, I would say that the hypothesis could be stated a bit more clearly. I did not attempt to dereference the pointer. I simply mangled it to be able to store different data types. However, all it would take as a simple print state me at the end of my code to attempt to do that.

===Conclusions===
It is possible to use a void pointer to point to different data types. The experiment did seem give Nick a better understanding of void pointers. However, it seems that there were certain aspects that he was not accounting for so it did not go quite as he had hoped. Actually... out of curiosity, I did attempt to add a printf statement and compile and the program compiles successfully. Also, after executing the program the desired effect appears to be achieved. 
<code c>
printf("%c\n", *(char*)vPtr);  
</code>
Adding that to the code appears to work just fine. It will print the '#' character.
Lab46 Wiki

User Tools

Site Tools

Page Tools
