Brad Hammond's Fall 2011 Opus
LDA #$FF
Welcome to Opus Land. Here you will find all kinds of opusy like things directly related to my Opus. See the opus. Hear the opus. Touch the opus. Become one with the opus. However, there are certain things one should never ever ever do with their opus. This will be a compendium of such things. Some of these things may seem like common sense. However, others will not.
Well, I think I'm finally at a good point with my linked list class. I may add a few more functions that, perhaps, compare linked lists to see if they're the same or copy one linked list into another linked list. As it stands right now many of the functions are overloaded to handle multiple data types. I can append and insert nodes into the list as well as delete nodes. Creating this class and implementing it really boosted my knowledge on doubly linked lists. At first, I was like, “huh?” but now I feel I've reached a decent level of understanding. Doing the insert functions was where I really had to think about things. Dropping a new node and relinking all the pointers to the right places really hurts the brain at first. I'd also like to try an implementation with templates. This will minimize the number of functions and, hopefully, will really cement my understanding of the subject.
I think I've come to understand the whole function pointer thing. It was just hard to come up with a practical use for them. In, C++ I remember discussing that the only difference between a class and a struct in C++ was that a class contains private members whereas in a function everything is public. However, in C structs cannot contain any functions. However, it is possible to create a function and put a pointer function within the struct. Now you can have a semi-sort of member function for your struct.
We've moved onto creating a stack today. Well, I guess I should say yesterday at this point but… At first it was kind of weird. I thought it would be difficult to mold the idea into my Linked List Class but it really didn't take that much. Instead of creating several Node pointers, I just instantiated a linked list object called stack. To push to the stack, I would just call the insert function and insert to the first point in the list. When popping from the stack I would just get the value at the first point in the list and then delete that node. Right now, I'm trying to get a palindrome checker using the stack but it's being a little goofy.
This is a sample format for a dated entry. Please substitute the actual date for “Month Day, Year”, and duplicate the level 4 heading to make additional entries.
As an aid, feel free to use the following questions to help you generate content for your entries:
Remember that 4 is just the minimum number of entries. Feel free to have more.
A pointer is a data type that contains the memory address where another value is stored in memory.
#include <stdio.h> int main() { int regVar = 0; int *pointVar = ®Var; printf("regVar is stored at 0x%x. \n", ®Var); printf("pointVar points to 0x%x. \n", pointVar); printf("regVar = %d\n", regVar); printf("The value of pointVar = %d\n", *pointVar); return 0; }
lab46:~$ ./pointer regVar is stored at 0x22ff74. pointVar points to 0x22ff74. regVar = 0 The value of pointVar = 0 lab46:~$
An array is a sequence of equally spaced address in memory. Arrays usually come in two flavors: one dimensional arrays and two dimensional arrays. One dimensional arrays are in a row format. Ex. array[0], array[1], array[3]… Two dimensional arrays use a row column format. Ex. array[0][0], array[0][1], array[0][2]…
Pointer arithmetic is a means of manipulating a position in memory via addition or subtraction. Pointer arithmetic and array subscripting are two ways of doing the same thing. To do the same
#include <cstdlib> #include <iostream> using namespace std; int main() { int *intPointer, x; intPointer = (int*) malloc(sizeof(int)*5); for (x = 0; x < 5; x++) cout << intPointer++ << endl; return 0; }
lab46:~$ ./pointerArithmetic 0x2145010 0x2145014 0x2145018 0x214501c 0x2145020 lab46:~$
In C/C++, a null pointer is a special case. Null is a mnemonic which makes it a little clearer that there is no object associated with a pointer. Integers and memory addresses are interchangeable. Zero, null, is the exception because in C it is guaranteed that 0 will never be a valid memory location. Attempting to access a null pointer would be bad. If you're fuzzy on the whole good bad thing, I want you to imagine all life as you know it stopping instantaneously, and every molecule in your body exploding at the speed of light.
#include <stdio.h> int main() { char *cp = NULL; printf("%c\n", *cp); return 0; }
lab46:~/src$ ./nullPoint Segmentation fault (code dumped) lab46:~/src$
A void pointer can be looked at kind of like a shape shifter. It can store an address to any data type. In C, it will be converted to any other data type when assigned. However, it can't be dereferenced without a cast.
#include <stdio.h> int main() { int i = 0; char c = 'A'; void* q = &i; printf("%d\n", *(int*)q); q = &c; printf("%c\n", *(char*)q); return 0; }
lab46:~$ ./voidPoint 0 A lab46:~$
Static memory allocation is the process of the allocating memory at compile time. This happens when variables are declared locally within a function.
{ int i, j; i = 1; j = i + 4; }
With dynamic memory allocation, memory is created at run time. In C, malloc() is used to allocate memory and in C++ the keyword new is used. This memory will exist until the user deallocates it via free() in C, and delete in C++ or the garbage collector takes care of it. In C
{ int *i = NULL; i = malloc(sizeof(int)); free(i); return 0; }
In C++
{ int *i; i = new int; delete i; return 0; }
A structure, or struct, is a compound data type consisting of multiple variables of, possibly, different data types. This makes for a nice way to group information that is related. This can be particularly useful when accessing records within a file. For instance, you may have a file which contains the first and last name and age of the employees at a company.
struct empInfo { char firstName[50]; char lastName[50]; int age; };
If we want to access the members of a struct, we'd do as follows.
struct empInfo joe; joe.firstName = "Joe"; joe.lastName = "Smith"; joe.age = 29;
A structure pointer is a much like any other pointer one would use. Using the structure example above, to create a pointer to that structure, one would do as follows:
struct empInfo *empPoint; empPoint = malloc(sizeof(struct empInfo));
Accessing the members of a struct pointer is a little different than accessing the members of a struct declared statically. Lets say we want to store the age of an employee into our struct, we'd do the following:
empPoint -> age = 20;
A linked list is an unspecified number of structure pointers all chained together. Only the start and the end are specified. Every other part of the chain is linked by the “next” pointer in the previous part of the chain. In order to maneuver through the list, one needs to resume back to the beginning of the list and move forward.
struct Node { int value; struct Node *next; };
The above struct is the core of a linked list. The variable value stores what integer data we have. The node pointer next points to the next item in the list. If there is only one item in the list or this node is the end of the list, next points to NULL. If we're somewhere in the middle of the list, next will point to whatever the next item in the list is.
int value, i; if (pos > listLength || pos < 0) pos = 0; tmp = start; for (i = 0; i < pos; i++) tmp = tmp -> next; value = tmp -> intVal;
This code first checks if the desired position in the list is out of bounds and sets the pos to 0. We then move to the beginning of the list and cycle through until we reach the desired position and retrieve the value
A doubly linked list isn't much different that a singly linked list. The only major difference is that your struct will also contain a pointer to the previous item in the list. With this type of list you can move from either the beginning of the list to the end or from the end to the beginning.
struct Node { int value; struct Node* prev; struct Node* next; };
The only difference between this struct and the one from above is the Node pointer prev. This means that there will be a few more loose ends to tie up. So, if we were to delete a node somewhere in the middle of the list.
tmp -> next -> prev = tmp -> prev; tmp -> prev -> next = tmp -> next; tmp -> prev = NULL; tmp -> next = NULL; free(tmp);
In the above code, first, we set the prev pointer in the next list element to point at the list element before tmp. So, if we have 3 nodes One, Two, and Three, and we're deleting node Two, we're Three's prev to point at Two. Now we set the next pointer of the previous element in the list to point at the node after tmp. So, One's next will point at Three. We then set all of the pointers within Two to NULL and deallocate the memory.
A function pointer is a bit of a special case pointer. A function starts at a certain address in memory. We can dereference a pointer to invoke a function.
#include <stdio.h> int add(int, int); int sub(int, int); struct Thing { int val1, val2; int (*addition)(int, int); int (*subtraction)(int, int); }; int main() { int x, y; struct Thing myThing; myThing.addition = &add; myThing.subtraction = ⊂ printf("First int: "); scanf("%d", &x); printf("Second int: "); scanf("%d", &y); printf("Addition: %d\n", myThing.addition(x, y)); printf("Subtraction: %d\n", myThing.subtraction(x, y)); return 0; } int add(int a, int b) { return a + b; } int sub(int a, int b) { return a - b; }
In C, it's not possible to declare a function inside of a struct. However, we can create function pointers to work around and have some functions within our struct to process the struct's data.
Version control, in relation to our coursework, is the monitoring and manipulation of the changes within our source code. We can create changes and upload them to our repository, revert to an older change within the repository, and also we can view any changes that have been made.
lab46:~/src/cpu$ svn update At revision 432. lab46:~/src/cpu$
lab46:~/src/cpu$ ------------------------------------------------------------------------ r3 | bh011695 | 2011-01-27 13:05:23 -0500 (Thu, 27 Jan 2011) | 1 line added nandGate function ------------------------------------------------------------------------ r2 | jr018429 | 2011-01-27 09:56:47 -0500 (Thu, 27 Jan 2011) | 1 line added boolean operators ------------------------------------------------------------------------ r1 | wedge | 2011-01-23 19:30:06 -0500 (Sun, 23 Jan 2011) | 1 line Initial commit ------------------------------------------------------------------------
In Unix memory is segregated into two sections. First there is kernel space and secondly there is also user space. User space encompasses the area where the memory is used for user applications.
The location in memory where the operating system is stored is referred to as system space or kernel space. The operating system is referred to as the kernel. The kernel has sole access to any kind of peripheral device such as a printer, mouse, or keyboard. If an application wants to access any of these devices, it requires permission from the kernel.
The function open of type int which returns a file descriptor. If opening the file was unsuccessful a -1 will be returned, otherwise will return an integer. It takes, as parameters a filename and an int constant, the read/write flag, to tell the function what you plan on doing with the file: reading, writing, or reading and writing.
read() is a system call which reads from a file descriptor. As parameters, it takes a file descriptor, a void pointer buf, and a count. read() will read count number of bytes starting from buf into the buffer from the file descriptor.
write() is used to store data into a file. write() has the parameters: a file descriptor, buffer, and amount. write() will take amount bites from buffer and send them to the file descriptor. If successful, write() will return the number of bytes written. If it fails it will return a -1. It is possible for the number of bytes sent to be different from the number of bytes requested. The system could possibly put a limit on the size of a file. There is also the possibility of disk space. Perhaps there is no more space left on the hard drive.
lseek() is used to find an offset within a file. It takes, as parameters, a file descriptor, the distance in bytes from the base, and the base which can be 0: start of file, 1: current position within the file, or 2: the end of the file.
Whenever finished with a file descriptor, it needs to be closed. close() takes as a parameter a file descriptor and returns a 0 upon success and a -1 on error. An error, for example, if you were to try to open a file that does not exist a -1 will be returned by close().
#include <stdio.h> #include <stdlib.h> #define OFFSET 100 #define BASE 0 #define BUFF_SIZE 50 int main(int argc, char** argv) { char *filePath, c[BUFF_SIZE]; int fd1, fd2; filePath = (char*) malloc(sizeof(char) * 100); if (argc != 2) { printf("error: no filepath entered\n"); } else { fd1 = open(argv[1], "r"); fd2 = creat("myFile", 644); lseek(fd1, OFFSET, BASE); read(fd1, c, BUFF_SIZE); write(fd2, c, BUFF_SIZE); close(fd1); close(fd2); } return 0; }
The data outputted to the file is a tad unintelligible. I thought I was doing everything right. It would appear that things aren't getting read into the buffer properly but I'm not sure why that would be.
A file descriptor is a means for which a process can talk to a file. When you open a file, a file descriptor will be created. A -1 signifies that there was an error. However, if there was no error an integer will be returned that will. This is the file descriptor. Any files opened will have a different file descriptor. This file descriptor will be used for operations performed on the file.
fd = open("myFile", "r");
This is how one would create a file descriptor.
Buffering is the means of taking data and storing in memory in chunks of a predetermined size. An example of this would be prompting the user for some character data and storing the first 50 bytes into an array. Once the desired operations have been performed on the data another 50 bytes would be stored into the array. Repeat this until there is no more data to process. The kernel has its own buffers which it uses to save time. It keeps copies of disk blocks in memory because of how long it would take to keep writing back and forth between memory and the hard disk.
A system call is a function that requests a service from the kernel. System calls can be divided into several groups: process control, file management, device management, information maintenance and communication. read() write() open() and close are all examples of a system call.
When you do an ls -l a lot of information is displayed. However, on the far left you can find the file type designation. There are many different types of files such as directories, regular files, sockets, symbolic links, or named pipes. In one of the earlier examples we used creat() to create a file. When creat() is called a filetype is designated to to the file. It is simply just a regular file. However, different system calls can be used to create different types of files.
A file also has many different properties such as its owner, its permissions, its name, the last time it had been written to, its size, or its create data. Like the file type, all of these things can be displayed by doing a simple ls -l. Using chown(), it is possible to be able to change the owner of a file. As parameters, chown() takes the path to the file, the owner id, and the group id. It is also possible to change the permission bits of a file using chmod(). It's parameters are a file path and the new permissions.
bh011695@lab46:~/discrete$ ls -l total 776 -rw-r--r-- 1 bh011695 lab46 96 Sep 17 13:05 Makefile -rwxr-xr-x 1 bh011695 lab46 684685 Sep 23 23:35 a.out -rwxr-xr-x 1 bh011695 lab46 7104 Sep 7 15:45 assignmentFive -rw-r--r-- 1 bh011695 lab46 654 Sep 9 17:34 assignmentFive.c -rwxr-xr-x 1 bh011695 lab46 7065 Sep 10 10:07 assignmentOne -rw-r--r-- 1 bh011695 lab46 602 Sep 9 17:36 assignmentOne.c -rwxr-xr-x 1 bh011695 lab46 8553 Sep 9 15:38 assignmentTwo -rw-r--r-- 1 bh011695 lab46 776 Sep 9 17:33 assignmentTwo.c -rwxr-xr-x 1 bh011695 lab46 8046 Sep 17 13:09 count -rw-r--r-- 1 bh011695 lab46 344 Sep 17 13:09 count.c -rw-r--r-- 1 bh011695 lab46 1872 Sep 17 13:09 count.o -rw-r--r-- 1 bh011695 lab46 4154 Sep 23 23:34 libStringLib.a drwxr-xr-x 2 bh011695 lab46 4096 Sep 29 10:21 stringLib -rw-r--r-- 1 bh011695 lab46 874 Sep 17 12:30 stringLib.c -rw-r--r-- 1 bh011695 lab46 228 Sep 17 12:30 stringLib.h -rw-r--r-- 1 bh011695 lab46 2312 Sep 23 23:39 stringLib.o -rwxr-xr-x 1 bh011695 lab46 7697 Sep 23 23:40 test -rw-r--r-- 1 bh011695 lab46 3237 Sep 24 14:31 test.c -rw-r--r-- 1 bh011695 lab46 1552 Sep 23 23:39 test.o -rw-r--r-- 1 bh011695 lab46 120 Sep 23 23:30 test1.c
Bit masking involves checking to see if a certain bit is a one or a zero. To turn a bit on a logical or operation is used. To turn a bit off a logical and is used. It also possible to check the status of a single bit or to change multiple bit values.
#include <stdio.h> int main() { int num = 97; int mask = 128; printf("num = %d\n", num); //Turn on the left most bit printf("num = %d\n", num = num | mask); //turn off the left most bit mask = 127; printf("num = %d\n", num = num & mask); return 0; }
lab46:~$./mask num = 97 num = 225 num = 97
An unsigned integer value is designated to every user within the system. This UID ranges between 0 and 32767. 0 is always designated to root. A GID, or group ID, follows the same convention. Any user on the system can run the id command to obtain their user and group ID.
bh011695@lab46:~$ id uid=5577(bh011695) gid=5000(lab46) groups=5000(lab46),1734(sys),1738(data),2999(bigworld),5577(bh011695)
An inode stores information about a file The only things the inode does not contain are the files data and the file's name. Every file on the system has an inode associated with it. All of the inodes on the system are contained inside of an inode table. Data blocks are where the file data is actually stored. When a file is to be stored, the kernel will locate however many blocks are needed to store the file. These data blocks may or may not be adjacent to each other. The kernel will then store the information within these data blocks.
In Unix, a directory is a special type of file. A directory contains all of the names of the files stored within it. To be able to view the files of a directory with their respective inode numbers is to do an ls -1ia.
bh011695@lab46:~$ ls systemsProg -1ia 573673308 . 66461891 .. 573676539 .swp 573654795 Output.txt 573673286 cli 573673302 cli.c 573655652 filesandargs.c 573655709 fork.c 573655682 fork2.c 573654788 fprintf 573655613 fprintf.c 573655696 fscanf.c 573655614 getopt.c 573655620 mtest 573655617 mtest.c 573655706 output.txt 573655618 screentest.c 573655707 stringmanip.c
Looking at the output, there is a big list of numbers followed by file names. For instance inode 573655707 is associated with stringmanip.c. All of the meta data for stringmanip.c is stored within this inode.
Symbolic links or just links for short are very much like a shortcut in windows. A link is a file that points to another file. The reason for this is because multiple files can have the same inode number.
bh011695@lab46:~/ASM_6502$ ln helloWorld.asm newHi.asm bh011695@lab46:~/ASM_6502$ ls -1ia 553450825 . 66461891 .. 556055369 0x8.65s 556055370 0x9.65s 556055378 0xA.65s 553450824 ASM_EOCE.txt 556055371 helloWorld.asm 556055371 newHi.asm
If we look at the output of ls after doing the ln, we see that helloWorld.asm and newHi.asm both share the same inode number.
Choose the appropriate data structure for solving a given problem. Apply the data structure that would be best suited for solving some problem.
I've used our stack implementation from earlier to be able to solve the palindrome problem.
#include "LinkedList.h" #include <cstdio> #include <cstdlib> void push(char, LinkedList&); char pop(LinkedList&); int main() { LinkedList stack; char *string, *start, c; int unequal = 0; string = (char*) malloc(sizeof(char)*50); start = string; printf("Enter a string: "); scanf("%s", string); printf("Your string is %s.\n", string); while (*string != '\0') push(*string++, stack); string = start; while (stack.length() > 0 ) { if (pop(stack) != *string++) unequal = -1; stack.del(0); } string = start; if (unequal == 0) printf("%s is a palindrome.\n", string); else printf("%s is not a palindrome.\n", string); return 0; } void push(char value, LinkedList &s) { s.insert(value, 0); } char pop(LinkedList &s) { return s.getCharVal(0); }
lab46:~$ ./palindrome Enter a string: noon Your string is noon. Noon is a palindrome ./palindrome Enter a string: lair Your string is lair. lair is not a palindrome.
Reflect upon your results of the measurement to ascertain your achievement of the particular course objective.
Better understand file I/O for efficient data processing. Be able to read and write using C functions.
I've created a bit of a file copying program. It opens an input file, reads the character data into it, and then copies it into a new file.
#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { char *filePath; int inChar; FILE *inFile, *outFile; filePath = (char*) malloc(sizeof(char) * 100); if (argc != 2) { printf("Path to file: "); scanf("%s", filePath); inFile = fopen(filePath, "r"); outFile = fopen("fileCopy.txt", "w"); } else { inFile = fopen(argv[1], "r"); outFile = fopen("fileCopy.txt", "w"); } while ((inChar = fgetc(inFile)) != EOF) fputc(inChar, outFile); fclose(inFile); fclose(outFile); return 0; }
It does what it's supposed to. It reads input from a file and then outputs it into a new file.
Reflect upon your results of the measurement to ascertain your achievement of the particular course objective.
I had some issues with part of the project in discrete. I was having a little confusion as passing a pointer. I'm used to either passing a normal variable by value or passing by referencing using &. So, the question is, aren't sending a pointer and passing by reference the same thing?
Well, from what I know about pointers, when you pass one to a function you're passing a memory address. When you pass by reference, you pass the memory address of the variable that you're passing, a pointer. http://www.cplusplus.com/forum/beginner/7117/
Passing a variable by reference and passing a pointer to a variable will achieve the same result.
How are you going to test your hypothesis? What is the structure of your experiment?
#include <cstdio> void first(int&); void second(int*); int main() { int i = 25; int *j = &i; first(i); second(j); return 0; } void first(int& i) { printf("%d\n", i); } void second(int *i) { printf("%d\n", *i); }
lab46:~$ ./exp1 25 25
Based on the data collected:
For the most part, sending a pointer to a function and passing a variable by reference isn't much difference. The only real difference between the two of these is the ability to set a pointer to NULL which doesn't exist when passing by reference.
Something I've wondered in C++ there is a string type however, in C we create a pointer or an array of characters. Are these two things identical in size?
The two should be the same size. A C string should be one byte times the number of elements and the string type, unless there's added overhead, should be the same size. However, I want to say that I've tested this before and the two variables were of different sizes. Thought I can't quite remember.
A C string and a C++ string type variable should be the same size in bytes if they are of the same length.
How are you going to test your hypothesis? What is the structure of your experiment?
int main() { char *s1 = "cats"; string s2 = "cats"; printf("s1 is %d bytes\n", sizeof(s1)); printf("s2 is %d bytes\n", sizeof(s2)); return 0; }
lab46:~$ ./size s1 is 4 bytes s2 is 4 bytes
Based on the data collected:
It does turn out that both the C String and the string type are the same size if they are of the same length. However, I'm NOT sure as to why they're only four bytes. “cats\0” should be 5 bytes I would think.
The SysProg book had an experiment. Create a shell script that seems to recursively create directories. Even a second after there should be lots and lots of directories. Kind of like sticking a mirror in front of another mirror and looking at it. The question is, how do you delete them?
The book says that it shouldn't take long to create a directory tree that will go beyond the abilities of most commands that work on directory trees.
There won't be a simple command that deletes this tree. Rm will not delete a directory if it contains any other files. Rmdir works very much the same and lacks a recursive option. Neither of these should work.
The experiment will be to use a shell script to create a gigantic directory tree. After the tree has been created, check the number of sub-directories with ls. Confirm this by cd-ing through the tree. Lastly, try to delete the tree with a fairly simple command.
Create a huge file tree
#!/bin/bash while true do mkdir deep-well cd deep-well done
Doing an ls -lh gives us the following output on our new directory tree
drwxr-xr-x 3 ubuntu ubuntu 2.0k 2011-10-01 12:57 deep-wellI strolled through the tree and found the directory count, 3, in the ls was quite wrong. So, if that doesn't work, will it be possible to delete the tree using standard rm and rmdir. Both of these result in failure.
ubuntu:~$ rm deep-well/ rm:cannot remove `deep-well/': Is a directory ubuntu:~$ rmdir deep-well ubuntu:~$ rmdir: failed to remove `deep-well': Directory not empty
Now what happens when we add the force and recursive options to rmdir?
ubuntu@ubuntu:~/scripts$ ls 2Fake.sh deepWell.sh guessing_game.sh random_num_generator.sh anagram.sh dialog.sh jumble2.sh test_jumble.sh array.sh dice_game.sh jumble.sh yrProd.sh auto_draw fake_work.sh mousescroll.sh deep-well ghostarray.sh palindrome.sh ubuntu@ubuntu:~/scripts$ cd deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/ ubuntu@ubuntu:~/scripts/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well$ pwd /home/ubuntu/scripts/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well ubuntu@ubuntu:~/scripts/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well/deep-well$ cd ~/scripts ubuntu@ubuntu:~/scripts$ rm -rf deep-well/ ubuntu@ubuntu:~/scripts$ ls 2Fake.sh deepWell.sh ghostarray.sh mousescroll.sh yrProd.sh anagram.sh dialog.sh guessing_game.sh palindrome.sh array.sh dice_game.sh jumble2.sh random_num_generator.sh auto_draw fake_work.sh jumble.sh test_jumble.sh ubuntu@ubuntu:~/scripts$
Based on the data collected:
It is possible to delete a fairly large directory tree with a simple command line. However, it would be worth retesting while keeping track of how long the shell script runs for, 5 seconds, 10 seconds, etc. It is possible that it's simply not running long enough. There may be a point where commands will no longer be able to do any kind of operations on the tree.
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.
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!
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.
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.
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.
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.
#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]; }
Pushing involves adding a new value to stack and “Push” any other items to higher positions on the stack.
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
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.
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;
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, 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.
for (x = 0; x < sp -> top; x++) //Pull all the values down the stack by one sp -> values[x] = sp -> values[x + 1];
Fully demonstrating the array based stack program with the below example.
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
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 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.
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.
#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; }
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.
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!
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 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 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.
//future code to be added
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 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 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.
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.
#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; }
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
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.
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.
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.
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.
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 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 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.
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.
#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); }
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$
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.
An alarm counts down from a specified time and sends the SIGALRM signal to the process when the timer reaches 0.
#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"); }
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ ./alarm 5 Sleeping for 5 seconds. Waking up...
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.
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.
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.
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
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.
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.
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.
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.
design programs that handle signals
I have a program that when you press CTRL-C it grabs the SIGINT and asks the user if they really want to quit.
#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); }
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$
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.
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.
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.
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.
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.
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
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
Based on the data collected:
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.
When working with large data structures, is there a large gap in execution time between statically allocation and dynamic allocation?
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.
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.
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.
int main() { int intArray[1024], i; for (i = 0; i < 1024; i++) { intArray[i] = i + 1; } return 0; }
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ time ./staticTest real 0m0.001s user 0m0.000s sys 0m0.000s
#include "List.h" int main() { List *myList; int i; myList = create(); for (i = 0; i < 1024; i++) { appendToList(myList, i + 1); } return 0; }
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs/LinkedList$ time ./dynamicTest real 0m0.002s user 0m0.000s sys 0m0.000s
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.
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.
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?
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
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.
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.
Publish the data you have gained from your performing of the experiment here.
int main() { void *vPtr; int i = 25; char c = '#'; vPtr = (int*)&i; vPtr = (char*)&c; return 0; }
brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$ gcc voidPointer.c -o voidPointer brad@brad-desktop:/media/50E9-B47B/Notepad++/Programs$
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.
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.
printf("%c\n", *(char*)vPtr);
Adding that to the code appears to work just fine. It will print the '#' character.
I finally got my stack working. The problem took some time to sort out. The issue wasn't with the stack implementation really. It was more of a problem with the linked list. When I created the insert function for the linked list it was assumed that if you were inserting into the list, the list already existed. To push onto the stack I was using the insert function to insert at position 0, however, since there was technically no list as stack→first was set to NULL, which in the insert function was considered an error. I ended up backtracking further and further using the error codes to figure out what was going on. In the end, I added a simple check to the push function. If stack→first is NULL, use the append function instead of the insert function. Still, the real weird thing is that a lot of these problems didn't pop up at first. Initially, I wasn't using the create function to create a list to use as a stack. Everything worked fine until I was popping the last value from the stack and then it would print the value but segfault immediately after. Once I used to the create function, it segfaulted immediately. That's just some kind of strange voodoo witch doctor nonsense.
As of right now, I'm going through the algorithms book and reading through all of the different sorting algorithms. It's pretty cool that you can do the same thing that many different ways. Each algorithm has a varying level of efficiency and purpose. So far, I've covered the selection sort and the bubble sort. The bubble sort causes the larger values to “float” to the top and the smaller values to “sink” to the bottom of the list. In a selection sort, the idea is to search through the list to find the smallest value and swap it with the element in the current position in the list.
In systems programming, I just finished covering socket programming. Socket programming is much different in C than in it is in Java. There's a lot more lower level things to worry about than in Java.
import java.net.*; import java.io.*; class Server { public static void main(String args[]) { try { ServerSocket ss = new ServerSocket(65000); for (int x = 0; x < 5; x++) { Socket s = ss.accept(); PrintWriter p = new PrintWriter(s.getOutputStream()); p.println("Connection number " + (x + 1) + "."); p.close(); } } catch (Exception e) { System.out.println(e.toString()); } } }
That's all there is to it in java.
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <netdb.h> #include <time.h> #include <string.h> #define PORT_NUM 13000 #define HOST_LEN 256 #define oops(msg) {perror(msg); exit(1);} int main(int argc, char **argv) { struct sockaddr_in saddr; struct hostent *hp; char hostname[HOST_LEN]; int sockID, sockFD, count = 0; FILE *sockFP; char *ctime(); time_t theTime; //Get a socket sockID = socket(PF_INET, SOCK_STREAM, 0); if (sockID == -1) oops("socket"); //Bind address to the socket bzero((void*)&saddr, sizeof(saddr)); gethostname(hostname, HOST_LEN); hp = gethostbyname(hostname); bcopy( (void*)hp -> h_addr, (void*)&saddr.sin_addr, hp -> h_length); saddr.sin_port = htons(PORT_NUM); saddr.sin_family = AF_INET; if (bind(sockID, (struct sockaddr *)&saddr, sizeof(saddr)) != 0) oops("bind"); //Allow incoming calls if (listen(sockID, 1) != 0) oops("listen"); //main loop while (1) { sockFD = accept(sockID, NULL, NULL); if (sockFD == -1) oops("accept"); sockFP = fdopen(sockFD, "w"); if (sockFP == NULL) oops("fdopen"); theTime = time(NULL); fprintf(sockFP, "The time here is.."); fprintf(sockFP, "%s", ctime(&theTime)); printf("Call number %d at %s", ++count, ctime(&theTime)); fclose(sockFP); } return 0; }
There's definitely more the user has to concern himself with here.
I got a start on the directory listing project. I've got some really basic functionality out of it which just consists of listing all the files within the directory except for the . files. Most of that comes from looking at what the book has and restricting . files really wasn't that hard. All you need to do is to check for whether or not the first character in the directory name is a . and if so don't display it. The book also says to alphabetize the listing, dump the listing to an array and run it through qsort. My problem here is that we have no real idea how many items will be in the directory. It could be 1 it could be more than 100. So, you could just make a 2 dimensional array of some size, however, you then could potentially have excess or insufficient space. I suppose you could also run through the items in the directory, count them, and then create a dynamic array for the number of items in the directory and then have the name length as a fixed size. As far as formatting goes i don't think that should be too difficult.
This is a sample format for a dated entry. Please substitute the actual date for “Month Day, Year”, and duplicate the level 4 heading to make additional entries.
As an aid, feel free to use the following questions to help you generate content for your entries:
Remember that 4 is just the minimum number of entries. Feel free to have more.
Computational Complexity focuses on classifying computational problems by their level of difficulty. The basic principle is that a problem is capable of being solved by a computer. A problem will be regarded as initially difficult if it requires a large amount of resources to solve. The resources in question can be disk space, memory usage, network resources, etc. This can help to establish the practical limits of current computers. This can also help to decide whether or not a particular problem can be solved with the given resources at hand.
In computer science, Big-O notation is used to describe how an algorithm responds to different input sizes. This can be used to describe an algorithm's efficiency. It can be formally defined as f(x) = O(g(x)) as x approaches infinity. Big-O notation can sometimes be replaced by Big-Theta notation. Depending on the bounds you wish to describe will determine which notation would be used.
In a selection sort the basic idea is to find the smallest value in a list and move it to the first position. From here we move tot he second position and search for the smallest value starting from this position and moving it to this position. After we find the smallest value and move it to the current position, we move to the next position and repeat.
#include <iostream> #include <cstdlib> using std::cout; using std::endl; void selectionSort(int[]); const int ELEMENTS = 25; int main() { srand(time(NULL)); int values[ELEMENTS], j, temp, min; for (int i = 0; i < ELEMENTS; i++) values[i] = rand() % 100; cout << "Before: "; for (int i = 0; i < ELEMENTS; i++) cout << values[i] << " "; cout << endl; selectionSort(values); cout << "After: "; for (int i = 0; i < ELEMENTS; i++) cout << values[i] << " "; cout << endl; return 0; } void selectionSort(int v[]) { int minIdx, temp; for (int i = 0; i < ELEMENTS - 1; i++) { minIdx = i; for (int j = i + 1; j < ELEMENTS; j++) { if (v[j] < v[minIdx]) minIdx = j; } if (minIdx != i) { temp = v[minIdx]; v[minIdx] = v[i]; v[i] = temp; } } }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./selectSort Before: 99 9 57 47 9 77 47 61 14 35 92 49 87 32 95 54 21 85 96 96 66 9 48 29 2 After: 2 9 9 9 14 21 29 32 35 47 47 48 49 54 57 61 66 77 85 87 92 95 96 96 99
The idea behind a bubble sort is that the higher values will rise to the top of the list while the lower values will sink to the bottom of the list. The list is sorted by checking adjacent array elements and if the element that is higher in the array is less than the element that is lower the two values will be exchanged.
#include <iostream> #include <cstdlib> using namespace std; const int SIZE = 25; void bubbleSort(int[], int); int main() { int values[SIZE]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) values[i] = rand() % 100; cout << "Before: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; bubbleSort(values, SIZE); cout << "After: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; return 0; } void bubbleSort(int v[], int size) { int temp; for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1; j++) { if (v[j] > v[j + 1]) { temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; } } } }
brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ ./bubbleSort Before: 78 97 77 0 48 64 94 77 31 86 22 2 68 2 42 42 21 35 13 36 46 98 16 12 22 After: 0 2 2 12 13 16 21 22 22 31 35 36 42 42 46 48 64 68 77 77 78 86 94 97 98
An insertion sort goes through a list one element at a time placing each element into its correct place. Each time an element is selected, its moved into down the list until it finds an element that it is greater than. If the current element is already greater than its previous element it moves to the next element in the list.
#include <iostream> #include <cstdlib> using namespace std; void insertionSort(int[], int, int); int *makeList(const int); const int SIZE = 25; int main() { int *values; values = makeList(SIZE); cout << "Before: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; for (int i = 0; i < SIZE; i++) insertionSort(values, i, values[i]); cout << "After: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; delete[] values; return 0; } int *makeList(const int size) { int *values = new int[size]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) values[i] = rand() % 100; return values; } void insertionSort(int a[], int pos, int val) { int i = pos - 1; while (i >= 0 && a[i] > val) { a[i + 1] = a[i]; i--; } a[i + 1] = val; }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./insertSort Before: 61 49 66 97 46 16 29 23 42 76 8 52 65 7 29 3 96 64 93 28 25 55 47 90 50 After: 3 7 8 16 23 25 28 29 29 42 46 47 49 50 52 55 61 64 65 66 76 90 93 96 97
Right now I'm not entirely sure how this functions. I'm not very good with recursive logic. I'll keep pecking at it later and see if I can get any further with it.
#include <iostream> #include <cstdlib> using namespace std; int *makeList(const int); void quickSort(int[], int, int); const int SIZE = 25; int main() { int *values; values = makeList(SIZE); cout << "Before: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; quickSort(values, 0, SIZE); cout << "After: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; delete[] values; return 0; } int *makeList(const int size) { int *values = new int[size]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) values[i] = rand() % 100; return values; } void quickSort(int v[], int left, int right) { int mid, temp, i, j; i = left; j = right; mid = v[(left + right) / 2]; do { while (v[i] < mid) i++; while (mid < v[j]) j--; if (i <= j) { temp = v[i]; v[i] = v[j]; v[j] = temp; i++; j--; } } while (i <= j); if (left < j) quickSort(v, left, j); if (i < right) quickSort(v, i, right); }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./quickSort Before: 49 75 62 19 11 12 70 96 16 95 2 83 99 30 69 73 80 20 41 84 28 86 82 23 54 After: 2 11 12 16 19 20 23 28 30 41 49 54 62 69 70 73 75 80 82 83 84 86 95 96 99
#include <iostream> #include <cstdlib> using namespace std; int *makeList(const int); int binarySearch(int[], int, const int); const int SIZE = 10; int main() { int grandpaSeth[] = {0, 2, 4, 7, 12, 15, 16, 19, 21, 22}, nilbog; cout << "Enter a value to search for: "; cin >> nilbog; if (binarySearch(grandpaSeth, nilbog, SIZE) == 0) cout << "Found " << nilbog << endl; else { cout << "Could not find " << nilbog << endl; for (int i = 0; i < SIZE; i++) cout << grandpaSeth[i] << " "; cout << endl; cout << "Try again..."; cin >> nilbog; if (binarySearch(grandpaSeth, nilbog, SIZE) == 0) cout << "Found " << nilbog << endl; else cout << "Could not find " << nilbog << endl; } return 0; } int binarySearch(int v[], int val, const int size) { int low = 0, high = size -1, i; while (low <= high) { i = (low + high) / 2; if (val == v[i]) return 0; else if (val < v[i]) high = i - 1; else low = i + 1; } return -1; }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./binSearch Enter a value to search for: 10 Could not find 10 0 2 4 7 12 15 16 19 21 22 Try again...12 Found 12
A binary search algorithm splits a sorted list down the middle and the checks to see what side of the list the desired value exists if it does exist within the list. Then, depending on what side of the list we're searching through, we keep moving through the list until we find a value that is either equal to, greater than, or less than the desired value. In the example above, 10 was the first value searched and was first compared to see if it was equal to 15. Since they're not equal we check if to see if 10 less than or greater than 15. Less than, so we check the first half of the list. We keep going down the list until we find the number in the list or we find a value that is less than the desired value.
A binary search tree is a programming data structure much like a linked list. Each node in the list has at most two child nodes, a right in left. The left child node contains values that are less than that of the current node while the right child node contains only values that are greater than the current node.
When inserting into a binary tree everything is relative to the current node. Lets say that we have a binary tree that contains the values 4, 2, 9, and 7. All of which we were inserted in that order. The tree would look as follows
[4]
/ \
/ \
[2] [9]
/
/
[7]
Now lets say that we wish to insert 8 into the tree. We would first compare 8 with 4. Since 8 > 4 we move to the right branch. We than compare 8 with 9. Since 8 < 9 we move to the left branch. Finally we compare 8 with 7. Since 8 > 7 we move to the right branch and also since we have now encountered NULL, the end of the list we can insert the value here.
When removing a leaf from a binary tree there are 3 possible scenarios.
If the node has no children, you can simply remove it from the tree. If a node has one child we remove the node from tree and then replace that node with its child. If the node has two children, we can shift the value of the right child node to the position of the node that we wish to remove.
Inserting and searching a binary tree are very similar. In order to insert into a tree we must first search the tree for the right spot to insert the value. However, in the case of simply searching through a tree if we reach NULL, the end of the tree, than the value we're searching for does not exist within the tree.
I'm not quite sure that I understand how to retrieve the values stored in a tree. Here is some material on the subject. http://en.wikipedia.org/wiki/Binary_search_tree#Traversal
http://encrypt3d.wordpress.com/2010/09/21/binary-search-tree-traversal/
A program is simply a list of executable machine instructions. The idea of a process is a bit different. A process is a program during execution, the memory space allocated for the program.
Threads can be thought of as multiple programs using the same source code but executing at different points within the source code. The processor will jump back and forth between the different threads quickly enough to that to the user it appears that the execution is all taking place simultaneously.
In UNIX, processes are created in a tree like manner. All processes are created by a parent process, in most cases bash using the fork system call. Any process created by fork is a child process of the process that called fork. the calling process is referred to as a parent process. Both parent and child have their own individual PIDs allowing the user to distinguish the two.
#include <unistd.h> #include <stdio.h> int main() { int myPid; myPid = getpid(); fork(); if (myPid == getpid()) printf("I'm the parent my PID is %d\n", myPid); else printf("I'm the child my PID is %d\n", getpid()); return 0; }
brad@brad-desktop:~/c_programs$ ./forkin I'm the parent my PID is 16251 I'm the child my PID is 16252
Shell variables are a set of variables that are used by the shell that can be manipulated by running processes. They can be used to specify file paths, the current shell version, the current user's name and many other things. For example, the bash shell has a shell variable for random numbers.
brad@brad-desktop:~/c_programs$ echo $RANDOM 21946 brad@brad-desktop:~/c_programs$ echo $USER brad brad@brad-desktop:~/c_programs$ echo $BASH_VERSION 4.1.5(1)-release
I/O can be redirected in several ways. One of the most common ways is to redirect output from the standard output device to some file. For instance, if a process outputs some information we don't really care about it can be redirected to /dev/null. Also, if we wish to save some output, we could redirect it to a file and use it later.
brad@brad-desktop:~/closet$ ./msg "Howdy, Stranger" >> msg.txt brad@brad-desktop:~/closet$ ls msg msg.cc msg.txt brad@brad-desktop:~/closet$ cat msg.txt Howdy, Stranger brad@brad-desktop:~/closet$
In UNIX, a pipe is a means to send the output from one process as input to another process.
bh011695@lab46:~/src/music/brad_notes$ cat MidiServer.java | wc -c 493
In the above command line, we cat MidiServer.java and send that output to wc which counts every character in MidiServer.java.
A server is a process which has some information that another process would like to retrieve. A socket is the means for retrieving this information. A socket is similar to a pipe, however, a socket is capable of bidirectional communication whereas a pipe can only send data in one direction. If the server process wishes to get information from the process that is communicating with it, it may do so.
The client/server model is a means of depicting the relationship between client and server processes. The server portion of the process provides some kind of data or service to the client(s). Examples of server applications are web servers and ftp servers. Client applications are things like web browsers and e-mail clients.
Coroutines both continue to run, however, control will pass from one process to the other to handle some phase of the task. If you have process1 and process2 such that they are coroutines, two pipes would be required for bidirectional communication. Data would be passed from process1 to process2. Process2 would manipulate the data and send the result back to process1 to perform other manipulations on and print the result.
A zombie process is a process that has finished executing but still has an entry remaining in the process table. Essentially it's a process that has not sent an exit status signaling completion to its parent. To remove a zombie, one can send the SIG_CHILD signal to the parent or attempt to kill the process. However, if this does not work it is possible to kill the parent at which point init will adopt the zombie and reap it itself.
A server socket waits for a request to come from some client application. It will perform some manipulation on the data from the request and then can return a result to the client application.
/* * Sample code block */ #include <stdio.h> int main() { return(0); }
A client socket is the end of a bidirectional communication with the purpose of retrieving some data from a server socket.
Compare alternative implementations of data structures with respect to performance
Time the execution to push and pop 10000 values to an array based stack and a linked list based stack.
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ time ./aStack real 0m1.230s user 0m0.716s sys 0m0.000s brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs/LinkedList$ time ./lStack real 0m0.003s user 0m0.004s sys 0m0.000s
It seems that the array stack took longer to execute than the linked list based stack. This is not at all what I was expecting. I was assuming the opposite would happen. Furthermore, the time gap is off by more than a second. This makes me wonder whether or not I've done something wrong but I ran the linked list through gdb just to make sure it wasn't skipping the pop loop but that's not the case. Perhaps my array stack algorithms for pushing and popping aren't very efficient?
design programs that handle signals - write a program that can perform an action based on a single that it receives.
#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"); }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./alarm 3 Sleeping for 3 seconds. Waking up...
Reflect upon your results of the measurement to ascertain your achievement of the particular course objective.
What will be the output of the following code?
#include <stdio.h> int main() { char name1[] = "Egon"; char name2[] = "Peter"; int myPid = getPid(); fork(); if (getpid() == myPid) printf("Hello, %s\n", name1); else printf("Hello, %s\n", name2); return 0; }
forkdemo1.c in the Understanding Unix/Linux programming book.
The output of the above program wasn't quite what I was expecting. It seems that if you differentiate between the PID of the child and parent process, you can then use that value as a means of flow control in your program to split the load of the program between the parent and child processes.
I'm going to compile the code from above and check the output. In the previous example of fork, certain code was executed twice. In this case, it should split the execution of the print statements. It should give the output of each line only once, unlike what happened in forkdemo1.c.
brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ gcc -o forkExp forkExp.c brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ ./forkExp Hello, Egon Hello, Peter
My hypothesis was correct. Based on the PID, it is possible to use this as a means of flow control giving the user the possibility to pass certain tasks over to the child process.
It would be very interesting to investigate this further. Something that would be fairly interesting, a possible other experiment, would be to take a program which contains two functions that would be doing some fairly long calculations but neither function relies on the other. Using the method above split the two functions between the parent and child and clock the execution time and compare this with the execution time of calling the functions sequentially.
If you had multiple unrelated manipulations to perform, could you fork and use this to cut the overall execution time in half?
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.
Yes, this should speed up execution time as you have two processes running simultaneously instead of performing one set of manipulations followed by the next set.
I will create two programs, one that performs the manipulations sequentially and another that uses fork to perform the operations.
#include <limits.h> #include <unistd.h> int main() { unsigned long l, k; for (l = 0; l < ULONG_MAX; l++) ; for (k = 0; k < ULONG_MAX; k++) ; return 0; }
#include <limits.h> #include <unistd.h> int main() { unsigned long l; unsigned long k; int myPid; myPid = getpid(); fork(); if (myPid == getpid()) { for (l = 0; l < ULONG_MAX; l++) ; } else { for (k = 0; k < ULONG_MAX; k++) ; } return 0; }
brad@Lucid-Lynx:~/c_programs$ time ./seqUlong real 0m17.570s user 0m17.513s sys 0m0.000s brad@Lucid-Lynx:~/c_programs$ time ./forUlong real 0m12.831s user 0m12.029s sys 0m0.032s
Based on the data collected:
Forking between these two processes cut 5 seconds off of the program's execution time. 5 seconds is a lot when it comes to processor time. This means that this is a very good method for cutting down on execution time.
If you're doing an experiment instead of a retest, delete this section.
If you've opted to test the experiment of someone else, delete the experiment section and steps above; perform the following steps:
Whose existing experiment are you going to retest? Prove the URL, note the author, and restate their question.
Evaluate their resources and commentary. Answer the following questions:
State their experiment's hypothesis. Answer the following questions:
Follow the steps given to recreate the original experiment. Answer the following questions:
Publish the data you have gained from your performing of the experiment here.
Answer the following:
Answer the following:
