I117 II I117 PROGRAMMING PRACTICE II 2 MEMORY MANAGEMENT 2 Research Center for Advanced Computing Infrastructure (RCACI) / Yasuhiro Ohara yasu@jaist.ac.jp
/ SCHEDULE 1. 2011/06/07(Tue) / Basic of Programming 2. 2011/06/09(Thu) / Fundamental structures 3. 2011/06/14(Tue) / Memory Management 1 4. 2011/06/16(Thu) / Memory Management 2 5. 2011/06/21(Tue) / Debugging 6. 2011/06/23(Thu) / Software Development Env. 1 7. 2011/06/28(Tue) / Software Development Env. 2 8. 2011/06/30(Thu) / Data Structure : Tree 9. 2011/07/05(Tue) / Data Structure: Hash 10. 2011/07/07(Thu) / Understanding Programs 1 11. 2011/07/12(Tue) / Understanding Programs 2 12. 2011/07/14(Thu) / Script Language 1 13. 2011/07/19(Tue) / Script Language 2 14. 2011/07/21(Thu) / Other Languages 15. 2011/07/26(Tue) / Examination
/ FINAL REPORT free topic : decide topic by 7/5(Tue) report us of the topic by e-mail: i117report@jaist.ac.jp / Sound file converter / web crawler (CalDAV) calendar program new shell, editor, window manager rsync encrypt/decrypt, rsync markov-chain program choose good theme TAask TA and me The final report must have deep consideration
/ TODAY'S INDEX / memory management malloc () / fundamental structure / array and linked list / tree, stack, queue
MAIN() Exercise: PRINTS MAIN() ARGUMENTS / prints main() arguments.! #include <stdio.h>! int main(int argc, char* argv[])! {! int i;! for(i = 0; i < argc; i++)! {! }! }! printf("argv[%d]: %s\n", i, argv[i]);!
/ MEMORY MANAGEMENT
/ ALLOCATE NEW MEMORY #include <stdlib.h> void * malloc (size_t size); void free (void *ptr); malloc: Memory ALLOCate size / allocate "size"- bytes memory and return the pointer. free: malloc () / frees the malloc'ed memory. *) malloc () free / you should free all the unnecessary malloc'ed memory. E.x.) struct listnode *target = (struct listnode *) malloc (sizeof (struct listnode)); free (target);
EXERCISE: DYNAMIC ALLOCATION OF 2-D ARRAY malloc() / use malloc() twice.! char array[m][n + 1] / take 2 arguments and create char array[m][n + 1].! array[0] "ABC..." / Fill "ABC..." in array [0].! array[1] "BCD..." / Fill with shifted string like "BCD..." in array[1] and after.! array[x]nul/ Terminate with NUL string in each array[x].! print / print the two arguments.! array[x] print / print each array[x] as one line.!
/ ANSWER 1. #include <stdio.h>! 2. #include <stdlib.h>! 3. void! 4. main(int argc, char **argv)! 5. {! 6. int m, n;! 7. int i, j;! 8. char **array;! 9. if (argc < 3)! 10. {! 11. printf ("%s <m> <n>\n", argv[0]);! 12. exit (1);! 13. }! 14. m = atoi (argv[1]);! 15. n = atoi (argv[2]);! 1. printf ("m = %d, n = %d\n", m, n);! 2. array = (char **) malloc (m * sizeof (char *));! 3. for (i = 0; i < m; i++)! 4. array[i] = (char *) malloc (n + 1);! 5. for (i = 0; i < m; i++)! 6. {! 7. for (j = 0; j < n; j++)! 8. array[i][j] = 'A' + i + j;! 9. array[i][n] = '\0';! 10. }! 11. for (i = 0; i < m; i++)! 12. printf ("%02d: %s\n", i, array[i]);! 13. }!
/ MEMORY MANAGEMENT / Dynamic memory allocation / Free-list, Memory-pool / for example, manage constant-size memory chunks in a linked list / reference count (Buddy Memory Allocation) http://en.wikipedia.org/wiki/buddy_memory_allocation / change size of array doubly each time / garbage collection
/ ARRAY AND LINKED LIST
(ARRAY) N P r o g r a m \0 / two dimension array M
(ARRAY) / PROS AND CONS : / the size of the array is static. insert / i 1 2 3 4 5 6 7 8 9 delete /
(LINKED-LIST)
(LINK-LIST) pros : / a list has basically unlimited size cons / need bookkeeping meta- memory
( ) or
DOUBLY LINKED LIST unlimited sized, fast insertion and deletion linked with pointers (SingleDoubly) Linked List NULL= =NULL
LIST LIMITATION unlimited size NULL= =NULL new =NULL add
LIST INSERTION NULL= =NULL new
LIST INSERTION NULL= =NULL new
LIST INSERTION NULL= =NULL new
LIST INSERTION done by manipulation of 4 pointers no shifting of slide is deletion
LIST DELETION NULL= =NULL unnecessary
LIST DELETION NULL= =NULL unnecessary
LIST DELETION NULL= =NULL unnecessary
LISTNODE LISTNODE STRUCTURE void * "void *" serves as abstract struct listnode { }; struct listnode *; struct listnode *; void *;
INSIDE LIST left-> left-> struct listnode *left; right-> right-> struct listnode *right; to be changed struct listnode *target;
() LIST ADDITION EXAMPLE /* left right target left target right */ left-> = target; target-> = left; target-> = right; right-> = target;
() LIST DELETION EXAMPLE /* left target right target left right */ left-> = right; right-> = left; /* left right target */ target->-> = target->; target->-> = target->;
LIST LIST STRUCTURE struct list { struct listnode *head; /* */ struct listnode *tail; /* */ int count; /* */ };
POINTER MANIPULATION
EXERCISE: ARRAY MODIFICATION PROGRAM / Has one array inside! / the array is variable length! (fgets) / input one line from stdin! "add " + <string> + '\n'! "remove " + <string> + '\n'! "add " + <num> + <string> + '\n'! ignore rest.! / After each inputs, print the length of array and its contents.!