Description
Answer the questions below according to the lab specification. Write
your answers directly in this text file and submit it to complete the
lab.
PROBLEM 1: Memory in `diagram.c’
================================
For each of the C blocks below, give a memory diagram of the block
indicating memory locations and contents of cells. These blocks appear
in the file `diagram.c’ which you can modify to print results if you
want to verify your answers.
MAKE SURE to accurately express the standard sizes for each of the
kinds of variables ON A 64-BIT MACHINE in your diagrams by placing
them at appropriate memory addresses that are tightly packed. A
reminder: on 64-bit machines, all pointers are 64 bits / 8 bytes.
A
~
,—-
| // BLOCK A
| int a = 5;
| int b = 7;
| double x = 4.5;
| int *ip = &a;
| ip = &b;
| int c = *ip;
| *ip = 19;
| // DRAW MEMORY HERE
Ints are 4 bytes
Doubles are 8 bytes
Pointers are 8 bytes
ADDR SYMB VAL
——————
#1048 a 5
#1044 b 7
#1032 x 4.5
#1024 *ip #1048
#1024 *ip #1044
#1020 c #1040
#1024 *ip 19
B
~
,—-
| // BLOCK B
| int arr[4] = {12, 14, 16, 18};
| int *arp = arr;
| int brr = 11;
| arr[1] = 23;
| arp[3] = 29;
| arp = &arr[2];
| *arp = brr;
| // DRAW MEMORY HERE
`—-
ADDR SYMB VAL
——————–
#2020 arr 18
#2016 arr 16
#2012 arr 14
#2008 arr 12
#2000 arp #2008
#1996 brr 11
#2012 arr 23
#2020 arr 29
#2000 arp #2016
#2000 arp 11
C
~
,—-
| // BLOCK C
| char str[8] = “hello”;
| str[5] = ‘w’;
| char *cp = str + 6;
| *cp = ‘\0’;
| str[0] = ‘y’;
| // DRAW MEMORY HERE
`—-
ADDR SYMB VAL
——————–
#3107 str[7] \0
#3106 str[6] \0
#3105 str[5] w
#3104 str[4] o
#3103 str[3] l
#3102 str[2] l
#3101 str[1] e
#3100 str[0] y
PROBLEM 2: Linked List Application
==================================
This problem deals with small application spread across three files:
– list.h declares types and functions
– list_funcs.c defines linked list functions
– list_main.c has a usable main() function
You will need to compile the two C files together to produce an
executable program as in
,—-
| gcc list_main.c list_funcs.c
`—-
Study the code in these and answer the following questions.
A
~
In `list_main.c’, a function related to `scanf()’ is used to read
input. Look up this function and describe its first argument. Also
mention what else this function is good for and what it returns when
the end of input is reached.
fscanf(). Its first argument is stdin or standard input. It returns EOF or the number
of items stored.
B
~
In `list_main.c’, a function from the standard C library is used to
compare strings (character arrays). Describe this function, how to
call it, and its return value. Describe how it is used to identify
commands typed by a user in list_main.c. Also determine whether this
function gives any guidance on the sorting order of strings.
strcmp() is used. It is called with strcmp(“What you want to compare input to”, input).
It returns a negative,zero, or positive int depending on if the object pointed to is less than
equal to, or greater than the inputted object. Not much guidance on sorting of strings but rather
on direct comparison.
C
~
Examine where a `list_t’ variable is declared in `list_main.c’. Is
the list a stack variable or one that has memory dynamically allocated
with malloc() and then subsequently free()’d? Examine the convention
of the `list_init()’ function in `list_funcs.c’. Does this function
allocate any memory or simply operate on an existing list_t? How is it
used with the `list_t’ declared in `main()’?
It is declared at the start of main after commands are printed. It has memory
dynamically allocated because its a linked list. It operates on an existing list_t. It is
declared and then passed into list_init().
D
~
Examine the `list.h’ header file. Describe the C structs that you see
there. What fields does a `list_t’ have? What fields does a `node_t’
have? What is the maximum length of strings that can be stored in the
linked list according to the definitions of the types?
There are node structs. a list has a head and nodes. A node has a value and a pointer to the next
node.
E
~
Examine functions such as `list_insert()’ in `list_funcs.c’ which
allocate nodes. How are they allocated? How is the size of nodes
determined so that the correct amount of space is allocated? Where and
how is the space allocated for nodes de-allocated (which function)?
A node is inserted at the head of the list if it’s not a duplicate.
That node becomes the head with a link to the previous head. Space is allocated
and freed through malloc() and free().
PROBLEM 3: Linked List Extension
================================
The files for the linked list application have places indicating where
a `list_contains()’ function and a `contains’ command should be
implemented. Complete this implementation which will require you to
write some C code in both `list_funcs.c’ and `list_main.c’. It will
also require you to do some string comparisons.
Paste the following below for you answer
1. Your code for list_contains()
2. Code you added to main() to enable the “contains” command to work
3. A sample session of the main application where several inserts are
done and contains is used to show some items are present and not
present
1. int list_contains(list_t *list, char *query){
node_t *ptr = list->head;s
while(ptr != NULL){
if (strcmp(ptr->data,query)){
return 1;
}
else{
return 0;
}
ptr = ptr -> next;
}
}
2. else if(strcmp(“contains”,cmd) == 0){
if(echo){
printf(“contains\n”);
}
list_contains(&list,&cmd);
}
3.list> insert hi
list> contains hi
does contain
list> contains job
does not contain
list> insert job
list> contains job
does contain
list>
PROBLEM 4: Command Echoing
==========================
Interactive applications like `list_main’ are made greatly more useful
if they can be “scripted”: made to perform without the need of human
interaction. A common means of doing this is provide a file with
commands to read in it rather than typing directly. While nothing in
`list_main’ appears to allow for this, with a few command line tricks
we can replace typed input with the contents of the file. Such as
below where a *pipe |* is used.
,—-
| > gcc -o list_main list_funcs.c list_main.c
|
| > cat commands.txt # show contents of commands.txt file
| insert rolf
| insert kermit
| insert fozzy
| get 2
| get 7
| contains kermit
| contains scooter
| delete scooter
| exit
|
| > cat commands.txt | ./list_main # use commands.txt as input for list_main
| Linked List Demo
| Commands:
| print: shows the current contents of the list
| clear: eliminates all elements from the list
| exit: exit the program
| insert thing: inserts the given string into the list
| get index: get the item at the given index
| contains thing: determine if the given thing is in the list
| (NOT YET IMPLEMENTED)
|
| list> list> list> list> 0: fozzy # several commands read, start of output
| 1: kermit
| 2: rolf
|
| list> 2: rolf # another command read but not printed
|
| list> index 7 out of bounds for list size 3
| out of bounds
|
| list> ‘kermit’ is present
|
| list> not found
|
| list> unknown command delete
|
| list> unknown command scooter
`—-
Clearly `list_main’ is doing something above but it is hard to
determine what because the commands being read are not printed, a
feature known as *command echoing*.
Sprinkled throughout the `list_main.c’ code are `printf’ statements
based on the variable `echo’ declared near the top of `main’. This
`echo’ variable is set at the top of `main’ based on whether command
line argument 1 is `-echo’. When it is, all commands are printed as
they are read. This is extremely useful in the present case as
illustrated below.
,—-
| > gcc -o list_main list_funcs.c list_main.c # compile
|
| > cat commands.txt # show commands
| insert rolf
| insert kermit
| insert fozzy
| get 2
| get 7
| contains kermit
| contains scooter
| delete scooter
| exit
|
| > cat commands.txt | ./list_main -echo # use file as input, echo commands
| Linked List Demo
| Commands:
| print: shows the current contents of the list
| clear: eliminates all elements from the list
| exit: exit the program
| insert thing: inserts the given string into the list
| get index: get the item at the given index
| contains thing: determine if the given thing is in the list
| (NOT YET IMPLEMENTED)
|
| list> insert rolf # commands are echoed
|
| list> insert kermit
|
| list> insert fozzy
|
| list> print # makes understanding behavior easier
| 0: fozzy
| 1: kermit
| 2: rolf
|
| list> get 2
| 2: rolf
|
| list> get 7
| index 7 out of bounds for list size 3
| out of bounds
|
| list> contains kermit
| ‘kermit’ is present
|
| list> contains scooter
| not found
|
| list> delete
| unknown command delete
|
| list> scooter
| unknown command scooter
|
| list> exit
`—-
*You will need to know how to use command echoing in an assignment* so
study how commands are printed carefully.
Create another text file with commands in it for `list_main’. Make
this file at least 10 lines long with different commands such as
`insert’ and `get’. Use the pipe technique shown to feed your
commands to the `list_main’ with the `-echo’ option set. Show your
results below.
list> insert hi
list> insert hello
list> insert job
list> get 1
1: hi
list> get 2
2: job
list> does contain
list> does not contain
list> does contain
list> insert jim
list> insert joe
list> print
0: hello
1: hi
2: jim
3: job
4: joe
list>
OPTIONAL PROBLEM
================
For fun but no extra credit, add a `int list_remove(list_t *list, char
*query)’ function and associated `remove’ command to the list
application. Keep the following in mind.
– Follow the convention that `list_remove()’ returns an integer
indicating no change was made (0) or something was removed (1)
– Do not forget to alter the size of the `list_t’ struct on removal.
– You will need to call `free()’ on the removed node to get rid of it
but do so AFTER re-arranging pointers associated with it.
– Don’t forget special cases such as removing the first node in the
list.
This is a surprisingly tricky exercise to get the memory use
right. You may wish to use valgrind to test whether your program has
memory leaks or not. Ask a TA for help with this if it has not been
discussed in class yet (valgrind WILL be discussed later).
