linkedlist.c

/** * Copyright (c) 2003-2017 by Hyoung Bok Min, All rights reserved. * For license information, please refer to * http://class.icc.skku.ac.kr/~min/program/license.html * * Programming Lab : Linked List * * This is the main program provided to students who registered * in "Programming Lab" at School of Information and Communication, * Sungkyunkwan University. * * ================================================================ * You must use function "mymalloc()" for memory allocation, and * you have to use function "myfree()" for disposing memory. * DO NOT USE "malloc()/free()" FOR DYNAMIC MEMORY ALLOCATION. * * void *mymalloc(int byte_count); * void myfree(void *ptr); * ================================================================ * */

#include #include #include #define _MEMCHECK_H_SIZE_OVER 5000 #include "memcheck.h"

/** * NODE data structure used in this program */

#define MAX_NUM 100

typedef struct list_node { struct list_node *link; int data; } NODE;

int headInsert(NODE **head, NODE **tail, int item); int headDelete(NODE **head, NODE **tail, int *item); int tailInsert(NODE **head, NODE **tail, int item); int secondDelete(NODE **head, NODE **tail, int *item); void deleteList(NODE **head, NODE **tail); static void printList(NODE *head);

int main(void) { NODE *head = 0; // head pointer of linked list NODE *tail = 0; // tail pointer of linked list int data0[] = { 99, 89, 76, 65, 51, 43, 23, 18, 9, -1 }; int data1[] = { 512, 415, 328, 256, 128, -1 }; int *data_used; // either data0 or data1 int loop; // loop variable int num; // number of data in data_used int i_data; // integer data of linked list int phase; // we will perform same job twice in phase 0 and 1

for (phase = 0 ; phase < 2 ; phase++) { // we perform the same job twice if (phase) data_used = data1; // data used in phase 1 else data_used = data0; // data used in phase 0

/** * [1] Create a list with headInsert */ printf(" Perform headInsert at phase %d ", phase); for (loop = 0 ; loop < MAX_NUM ; loop++) { if (data_used[loop] < 0) // terminated by negative value break; if (!headInsert(&head, &tail, data_used[loop])) { fprintf(stderr, "[E1] Head insertion failed(1). "); return 1; } printf(" a node added to head :"); printList(head); printf(" "); } if (tail->link) { fprintf(stderr, "[E2] Head insertion failed(2). "); return 2; } num = loop; // number of integers at data_used printf(" headInsert expected :"); for (loop = num-1 ; loop >= 0 ; loop--) // print expected values printf(" %d", data_used[loop]); printf(" ");

/** * [2] Delete head nodes */ printf(" Perform headDelete at phase %d ", phase); for (loop = num-1 ; loop >= 0 ; loop--) { printf(" deleting a head node :"); printList(head); printf(" "); if (!headDelete(&head, &tail, &i_data)) { fprintf(stderr, "[E3] Head deletion failed (1). "); return 3; } if (i_data != data_used[loop]) { fprintf(stderr, "[E4] Head deletion failed (2). "); return 4; } } if (headDelete(&head, &tail, &i_data)) { fprintf(stderr, "[E5] Head deletion failed (3). "); return 5; } printf(" headDelete performed okay. ");

/** * [3] Create a list with tailInsert */ printf(" Perform tailInsert at phase %d ", phase); for (loop = 0 ; loop < MAX_NUM ; loop++) { if (data_used[loop] < 0) break; if (!tailInsert(&head, &tail, data_used[loop])) { fprintf(stderr, "[E6] Tail insertion failed(1). "); return 6; } printf(" a node added to tail :"); printList(head); printf(" "); } if (tail->link) { fprintf(stderr, "[E7] Tail insertion failed(2). "); return 7; } num = loop; // number of data at linked list printf(" tailInsert expected :"); for (loop = 0 ; loop < num ; loop++) // print expected values printf(" %d", data_used[loop]); printf(" ");

/** * [4] Delete next to head nodes by using secondDelete() */ printf(" Perform secondDelete at phase %d ", phase); for (loop = 0 ; loop < num ; loop++) { int expected_index = loop+1; if (loop == (num-1)) expected_index = 0; printf(" deleting the next-to-head node :"); printList(head); printf(" "); if (!secondDelete(&head, &tail, &i_data)) { fprintf(stderr, "[E8] Second deletion failed (1). "); return 8; } if (i_data != data_used[expected_index]) { fprintf(stderr, "[E9] Second deletion failed (2). "); return 9; } } if (secondDelete(&head, &tail, &i_data)) { fprintf(stderr, "[E10] Second deletion failed (3). "); return 10; } printf(" secondDelete performed okay. ");

/** * [5] Test deleteList() */ // Build a linked list for deletion for (loop = 0 ; loop < MAX_NUM ; loop++) { if (data_used[loop] < 0) break; if (!headInsert(&head, &tail, data_used[loop])) { fprintf(stderr, "[E11] Head insertion failed(3). "); return 11; } } if (tail->link) { fprintf(stderr, "[E12] Head insertion failed(4). "); return 12; } // Delete the list deleteList(&head, &tail);

/** * [6] Check the list, and perform the same operation once more. */ if (head || tail) { fprintf(stderr, "[E13] List is not properly deleted. "); return 13; } printf("End of this phase. "); }

/** * [7] Epilog : check memory used by this program. * WARNING: DO NOT REMOVE THE FOLLOWING FUNCTION CALL. */ check_memory(); return 0; }

/** * Print a list from head to tail */ static void printList(NODE *head) { NODE *node = head;

while (node) { printf(" %d", node->data); node = node->link; } }

---------------------------------------------------------------------

memcheck.h

/** * Copyright (c) 2012-2017 by Hyoung Bok Min, All rights reserved. * For copyright and license information, please visit * http://class.icc.skku.ac.kr/~min/program/license.html * * File name : memcheck.h, revision c176 * * ================================================================= * There are three functions which are written to make sure that * your memory management is good enough. * * void *mymalloc(unsigned int byte_count); * Use this function as a substitute for "malloc()". * * void myfree(void *ptr); * Use this function as a substitute for "free()". * * void check_memory(void); * You have to call this function immediately before "return" * statements in your "main()" function. If you do not honor * this rule, your grade will be 0, absolutely. * * The following functions are used as subsitutes of fopen() and fclose() * to make sure that you're using those functions correctly. * * FILE *myfopen(const char *path, const char *mode); * Use this function as a substitute for "fopen()". * * int myfclose(FILE *stream); * Use this function as a substitute for "fclose()". * * PLEASE DO NOT MODIFY ANY PROGRAM CODES IN THIS FILE. * ================================================================= */

#ifndef _MEMCHECK_H #define _MEMCHECK_H

#ifdef _MEMCHECK_H_EXTERN #ifdef _MEMCHECK_H_SRCFILE extern void *mymymalloc(unsigned int byte_count, char *srcfile, int srcline); extern void mymyfree(void *ptr, char *srcfile, int srcline); #else extern void *mymalloc(unsigned int byte_count); extern void myfree(void *ptr); #endif extern void check_memory(void); extern void *_memcheck_h_do_not_use(char *); #ifndef O_NOT_USE_MEMCHECK_H_FOPEN extern FILE *myfopen(const char *path, const char *mode); extern int myfclose(FILE *stream); #endif #else #include #include #include #include

#ifdef UINT_PTR_T #error Please change the string UINT_PTR_T to another in memcheck.h. #endif

#if __GNUC__ #if __x86_64__ || __ppc64__ #define UINT_PTR_T unsigned long long int static UINT_PTR_T _mem_masks[] = { 0xffffffffff000000, 0xffffffff00000000, 0xffffff0000000000, 0xffff000000000000, 0xff00000000000000}; #else #define UINT_PTR_T unsigned long int static UINT_PTR_T _mem_masks[] = {0xffffff00, 0xffff0000, 0xff000000}; #endif #else #if _WIN32 #define UINT_PTR_T unsigned long int static UINT_PTR_T _mem_masks[] = {0xffffff00, 0xffff0000, 0xff000000}; #else #define UINT_PTR_T unsigned long long int static UINT_PTR_T _mem_masks[] = { 0xffffffffff000000, 0xffffffff00000000, 0xffffff0000000000, 0xffff000000000000, 0xff00000000000000}; #endif #endif /* __GNUC__ */

typedef struct _mem_chunk { struct _mem_chunk *next; void *ptr; UINT_PTR_T *pcode; UINT_PTR_T code; UINT_PTR_T mask; UINT_PTR_T size; #ifdef _MEMCHECK_H_SRCFILE char *srcfile; int srcline; #endif } _MEM_CHUNK;

static int _peak_mems = 0; static int _peak_num_mems = 0; static int _largest_mems = 0; static int _current_mems = 0; static int _size_mems = 0; static int _num_mems = 0; static void *_mems_used = 0; static _MEM_CHUNK **_mems_table = 0;

#ifndef O_NOT_USE_MEMCHECK_H_FOPEN typedef struct _mem_files_chunk { struct _mem_files_chunk *next; FILE *fp; char *path; char *mode; } _MEM_FILES_CHUNK;

#define _MEM_FILES_MAX 256 #define _MEM_FILES_MODE_MAX 3 static int _mem_num_files = 0; static int _mem_num_peak_files = 0; static _MEM_FILES_CHUNK *_mem_files_head = 0; #endif

/** * Get a mask of leading 1's in which the number of bits of 1's are equal to * the number of leading zero's at the given 'number'. */ static UINT_PTR_T _get_leading_zeros(UINT_PTR_T number) { UINT_PTR_T mask; int i, k, num_mem_masks = sizeof(_mem_masks) / sizeof(UINT_PTR_T); for (i = 0 ; i < num_mem_masks ; i++) { if ((number & ~(_mem_masks[i])) == number) { if (i == 0) return _mem_masks[i]; mask = _mem_masks[i-1] << 1; for (k = 0 ; k < 8 ; k++) { if ((number & ~mask) == number) return mask; mask <<= 1; } } } mask = _mem_masks[num_mem_masks-1] << 1; for (k = 0 ; k < 8 ; k++) { if ((number & ~mask) == number) return mask; mask <<= 1; } return 0; }

/** * hash function, courtesy of Bob Jenkins from * http://burtleburtle.net/bob/hash/integer.html * This function is declared in public domain at the above web page. * You may also find good hash functions at github, * https://gist.github.com/badboy/6267743 */ static int _mem_hash(UINT_PTR_T val, UINT_PTR_T size) { val = val ^ (val >> 4); val = (val ^ 0xdeadbeef) + (val << 5); val = val ^ (val >> 11); val = val % size; return (int)val; }

/* Extract item of key 'ptr' from hash table. */ static _MEM_CHUNK *_mem_extract(void *ptr) { _MEM_CHUNK *item, *prev = (_MEM_CHUNK *)0; int hash = _mem_hash((UINT_PTR_T)ptr, (UINT_PTR_T)_size_mems); assert(hash >= 0 && hash < _size_mems); item = _mems_table[hash]; while (item) { if (item->ptr == ptr) { if (prev) prev->next = item->next; else _mems_table[hash] = item->next; return item; } prev = item; item = item->next; } return (_MEM_CHUNK *)0; }

/* Insert an item into hash table. */ static void _mem_insert(_MEM_CHUNK *item) { int hash = _mem_hash((UINT_PTR_T)(item->ptr), (UINT_PTR_T)_size_mems); assert(hash >= 0 && hash < _size_mems); item->next = _mems_table[hash]; _mems_table[hash] = item; }

/* Get a new hash table size. */ static int _mem_new_size(int size) { int num, index; int primes[7] = { 3, 5, 7, 11, 13, 17, 19}; int begin = size + size + 1; if (begin < 0) return size; for (num = begin ; num > 0 ; num += 2) { for (index = 0 ; index < 7 ; index++) { if (num % primes[index] == 0) break; } if (index >= 7) return num; } return size; }

/* Create a new hash table with size of twice. */ static void _mem_rehash(void) { int i, old_size = _size_mems; _MEM_CHUNK **old_table = _mems_table;

_size_mems = _mem_new_size(old_size); if (_size_mems == old_size) return; _mems_table = (_MEM_CHUNK **)malloc(_size_mems*sizeof(_MEM_CHUNK *)); if (!_mems_table) { _mems_table = old_table; _size_mems = old_size; return; } for (i = 0 ; i < _size_mems ; i++) _mems_table[i] = (_MEM_CHUNK *)0; i = 0; for ( ; i < old_size ; i++) { _MEM_CHUNK *item = old_table[i]; while (item) { _MEM_CHUNK *nextitem = item->next; _mem_insert(item); item = nextitem; } } free(old_table); }

#ifdef _MEMCHECK_H_SRCFILE void print_leaked_mems(void) { _MEM_CHUNK *item; int i, first = 1; if (!_mems_table) return;

for (i = 0 ; i < _size_mems ; i++) { item = _mems_table[i]; while (item) { if (first) { first = 0; fprintf(stderr, "[NOTE] The above %d ", _num_mems); fprintf(stderr, "chunks of memories are as follows. "); } fprintf(stderr, " %lld bytes by mymalloc", (long long)(item->size)); fprintf(stderr, " at line %d", item->srcline); fprintf(stderr, " of file '%s' ", item->srcfile); item->size; item = item->next; } } } #endif

/** * Substitute for malloc() */ #ifdef _MEMCHECK_H_SRCFILE void *mymymalloc(unsigned int byte_count, char *srcfile, int srcline) { #else void *mymalloc(unsigned int byte_count) { #endif _MEM_CHUNK *the_mem; UINT_PTR_T for_code; #ifdef _MEMCHECK_H_SRCFILE int length; #endif unsigned int ptr_size = sizeof(char *); unsigned char *char_ptr, *to_user; int index;

if (byte_count <= 0) { #ifdef _MEMCHECK_H_SIZE_OVER fprintf(stderr, " [WARNING] You're requesting memory of size 0 "); fprintf(stderr, "bytes. Are you sure ? "); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above warning is given by mymalloc"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); #endif #endif return (void *)0; }

#if _MEMCHECK_H_SIZE_OVER > 1 if (byte_count > _MEMCHECK_H_SIZE_OVER) { fprintf(stderr, " [WARNING] You're requesting memory of size "); fprintf(stderr, "%d bytes. Are you sure ? ", byte_count); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above warning is given by mymalloc"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); #endif #ifdef _MEMCHECK_H_SIZE_OVER_NOTE fprintf(stderr, "[NOTE] If you want to suppress the above warning, "); fprintf(stderr, "remove the line which defines "); fprintf(stderr, "_MEMCHECK_H_SIZE_OVER in your program file. "); #endif } #endif

the_mem = (_MEM_CHUNK *)malloc(sizeof(_MEM_CHUNK)); if (!the_mem) return (void *)0;

char_ptr = (unsigned char *)malloc(byte_count + 2*ptr_size); to_user = char_ptr + ptr_size; the_mem->ptr = (void *)to_user; if (!char_ptr) { free(the_mem); return (void *)0; } the_mem->next = (_MEM_CHUNK *)0; the_mem->size = byte_count; for_code = (UINT_PTR_T)(the_mem->ptr); the_mem->mask = _get_leading_zeros(for_code); the_mem->code = the_mem->size ^ (for_code | the_mem->mask); the_mem->pcode = (UINT_PTR_T *)malloc(sizeof(UINT_PTR_T)); if (!(the_mem->pcode)) { free(char_ptr); free(the_mem); return (void *)0; } *(the_mem->pcode) = the_mem->code; #ifdef _MEMCHECK_H_SRCFILE length = strlen(srcfile); the_mem->srcfile = (char *)malloc((length+1)*sizeof(char)); if (!(the_mem->srcfile)) { free(char_ptr); free(the_mem->pcode); free(the_mem); return (void *)0; } strcpy(the_mem->srcfile, srcfile); the_mem->srcline = srcline; #endif _mems_used = the_mem;

if (!_mems_table) { int i; _size_mems = 10091; /* 10091, 99991 */ _mems_table = (_MEM_CHUNK **)malloc(_size_mems*sizeof(_MEM_CHUNK *)); assert(_mems_table); for (i = 0 ; i < _size_mems ; i++) { _mems_table[i] = (_MEM_CHUNK *)0; } } else if (_num_mems >= _size_mems) { _mem_rehash(); }

_mem_insert(the_mem); _num_mems++; if (byte_count > _largest_mems) _largest_mems = byte_count; if (_num_mems > _peak_num_mems) _peak_num_mems = _num_mems; _current_mems += byte_count; if (_current_mems > _peak_mems) _peak_mems = _current_mems;

// 0xff for leadning and trailing memory of pointer size for (index = 0 ; index < ptr_size ; index++) { *(char_ptr+index) = 0xff; *(char_ptr+ptr_size+byte_count+index) = 0xff; } return (void *)(char_ptr+ptr_size); } /* end of mymalloc */

/** * Substitute for free() */ #ifdef _MEMCHECK_H_SRCFILE void mymyfree(void *ptr, char *srcfile, int srcline) { #else void myfree(void *ptr) { #endif UINT_PTR_T for_code, size; _MEM_CHUNK *item; unsigned int ptr_size = sizeof(char *); int index, is_error; unsigned char *char_ptr;

if (!ptr) return; assert(_mems_table); assert(_size_mems > 0); assert(_num_mems > 0);

item = _mem_extract(ptr); if (!item) { char *msg = " [ERROR] Address provided to argument, which is " "used to call \"myfree()\", is invalid, and it is not " "elligibe for freeing a memory block. This message may " "be given due to one of the following reasons: " "(1) The argument may be a memory address which has " "already been made free by previous myfree() call, " "(2) The argument may be a memory address which has " "never been allocated by mymalloc() call, " "(3) The argument may be value of a pointer " "variable which has never been initialized, " "(4) There may be another unknown reason."; fprintf(stderr, "%s ", msg); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above error is given by myfree()"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); #endif exit(125); } if (item->code != *(item->pcode)) { fprintf(stderr, " [ERROR] Memory corrupted (1). "); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above error is given by myfree"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); fprintf(stderr, "[NOTE] The above corrupted memory is allocated by"); fprintf(stderr, " mymalloc at line %d", item->srcline); fprintf(stderr, " at file '%s'. ", item->srcfile); #endif exit(127); }

for_code = (UINT_PTR_T)ptr; size = (item->code & ~(item->mask)) ^ for_code;

if (item->size != size) { fprintf(stderr, " [ERROR] Memory corrupted (2). "); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above error is given by myfree"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); fprintf(stderr, "[NOTE] The above corrupted memory is allocated by"); fprintf(stderr, " mymalloc at line %d", item->srcline); fprintf(stderr, " at file '%s'. ", item->srcfile); #endif exit(126); }

// check overflow is_error = 0; char_ptr = (unsigned char *)ptr - ptr_size; // actual address of memory for (index = 0 ; index < ptr_size ; index++) { if (*(char_ptr+index) != 0xff) { fprintf(stderr, " [ERROR] Memory overflow (1). "); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above error is given by myfree"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); fprintf(stderr, "[NOTE] The above corrupted memory is allocated "); fprintf(stderr, " by mymalloc at line %d", item->srcline); fprintf(stderr, " at file '%s'. ", item->srcfile); #endif if (is_error & 2) break; is_error |= 1; } if (*(char_ptr+ptr_size+size+index) != 0xff) { fprintf(stderr, " [ERROR] Memory overflow (2). "); #ifdef _MEMCHECK_H_SRCFILE fprintf(stderr, "[NOTE] The above error is given by myfree"); fprintf(stderr, " at line %d at file '%s'. ", srcline, srcfile); fprintf(stderr, "[NOTE] The above corrupted memory is allocated "); fprintf(stderr, " by mymalloc at line %d", item->srcline); fprintf(stderr, " at file '%s'. ", item->srcfile); #endif if (is_error & 1) break; is_error |= 2; } }

// dispose memory _current_mems -= item->size; memset(item->ptr, -1, item->size);

free(item->pcode); #ifdef _MEMCHECK_H_SRCFILE free(item->srcfile); #endif free(char_ptr); // free(item->ptr); free(item); _num_mems--;

if (!_num_mems) { free(_mems_table); _mems_table = (_MEM_CHUNK **)0; _size_mems = 0; } } /* end of myfree */

#ifndef O_NOT_USE_MEMCHECK_H_FOPEN /* Search by path name */ static _MEM_FILES_CHUNK *_mem_files_search_by_path(const char *path) { _MEM_FILES_CHUNK *chunk = _mem_files_head;

while (chunk) { if (!strcmp(chunk->path, path)) return chunk; chunk = chunk->next; } return (_MEM_FILES_CHUNK *)0; }

/* Search by file pointer */ static _MEM_FILES_CHUNK *_mem_files_search_by_fp( FILE *fp, _MEM_FILES_CHUNK **prev) { _MEM_FILES_CHUNK *prev_chunk = (_MEM_FILES_CHUNK *)0; _MEM_FILES_CHUNK *chunk = _mem_files_head;

while (chunk) { if (chunk->fp == fp) { *prev = prev_chunk; return chunk; } prev_chunk = chunk; chunk = chunk->next; } return (_MEM_FILES_CHUNK *)0; }

/** * Substitute for fopen() */ FILE *myfopen(const char *path, const char *mode) { FILE *fp; _MEM_FILES_CHUNK *chunk; int lenpath, lenmode;

assert(path); assert(mode); lenpath = strlen(path); lenmode = strlen(mode); if (lenpath > _MEM_FILES_MAX) { fprintf(stderr, " [WARNING] File name is too long. "); fprintf(stderr, "The name is '%s'. ", path); } if (lenmode > _MEM_FILES_MODE_MAX) { fprintf(stderr, " [ERROR] File mode is too long. "); fprintf(stderr, "The mode is '%s'. ", mode); exit(140); }

chunk = _mem_files_search_by_path(path); if (chunk) { fprintf(stderr, " [ERROR] File '%s' has already been opened ", path); fprintf(stderr, "with mode '%s'. ", chunk->mode); exit(141); }

fp = fopen(path, mode); if (!fp) return fp;

chunk = (_MEM_FILES_CHUNK *)malloc(sizeof(_MEM_FILES_CHUNK)); assert(chunk); chunk->fp = fp; chunk->path = (char *)malloc((lenpath+1)*sizeof(char)); assert(chunk->path); strcpy(chunk->path, path); chunk->mode = (char *)malloc((lenmode+1)*sizeof(char)); assert(chunk->mode); strcpy(chunk->mode, mode); chunk->next = _mem_files_head; _mem_files_head = chunk; _mem_num_files++; if (_mem_num_files > _mem_num_peak_files) _mem_num_peak_files = _mem_num_files; return fp; }

/** * Substitute for fclose() */ int myfclose(FILE *stream) { _MEM_FILES_CHUNK *chunk, *prev;

if (!stream) { fprintf(stderr, " [ERROR] File pointer to 'myfclose()' is NULL. "); exit(145); }

chunk = _mem_files_search_by_fp(stream, &prev); if (!chunk) { fprintf(stderr, " [ERROR] File given to 'myfclose()' "); fprintf(stderr, "has never been opened, "); fprintf(stderr, "or the file has already been closed. "); exit(146); } if (prev) prev->next = chunk->next; else _mem_files_head = chunk->next; free(chunk->path); free(chunk->mode); free(chunk); _mem_num_files--; return fclose(stream); } #endif /* O_NOT_USE_MEMCHECK_H_FOPEN */

/** * Check memeory management at the end of main(). */ void check_memory(void) { printf("+++++ Checking memory... +++++ "); #ifdef _MEMCHECK_H_GRADE #if _MEMCHECK_H_GRADE > 9 #ifndef _MEMCHECK_H_SIZE_OVER printf("[WARNING] _MEMCHECK_H_SIZE_OVER is NOT defined. "); #else #if _MEMCHECK_H_SIZE_OVER != _MEMCHECK_H_GRADE printf("[WARNING] Value of _MEMCHECK_H_SIZE_OVER has been modified. "); #endif #endif #endif printf("largest memory requested = %d bytes. ", _largest_mems); printf("%d bytes in %d chunks at peak. ", _peak_mems, _peak_num_mems); #endif if (_num_mems > 0) { fprintf(stderr, "[ERROR] %d chunks of memories ", _num_mems); fprintf(stderr, "allocated by mymalloc() are not "); fprintf(stderr, "given back to operating system. "); #ifdef _MEMCHECK_H_SRCFILE print_leaked_mems(); #endif exit(124); } #ifdef _MEMCHECK_H_WARNING if (!_mems_used) { fprintf(stderr, "[WARNING] You have not used mymalloc()/myfree() "); fprintf(stderr, "for dynamic memory allocation. "); } #endif #ifndef O_NOT_USE_MEMCHECK_H_FOPEN #ifdef _MEMCHECK_H_GRADE printf("%d files have been opened at peak. ", _mem_num_peak_files); #endif if (_mem_files_head) { _MEM_FILES_CHUNK *chunk = _mem_files_head; fprintf(stderr, "[ERROR] %d file(s) have been opened,", _mem_num_files); fprintf(stderr, " but they have never been closed. "); while (chunk) { fprintf(stderr, "'%s' with mode '%s' ", chunk->path, chunk->mode); chunk = chunk->next; } exit(150); } #endif printf("+++++ Memory is okay. +++++ "); } /* end of check_memory */

/* To prohibit malloc/calloc/realloc/free/fopen/fclose/fdopen/freopen */ void *_memcheck_h_do_not_use(char *which) { fprintf(stderr, " "); fprintf(stderr, "---------------------------- "); fprintf(stderr, "[ERROR] DO NOT USE %s(). ", which); fprintf(stderr, "---------------------------- "); exit(122); }

#ifdef UINT_PTR_T #undef UINT_PTR_T #endif #endif /* _MEM_CHECK_H_EXTERN */

#define malloc(a) _memcheck_h_do_not_use("malloc") #define calloc(a, b) _memcheck_h_do_not_use("calloc") #define realloc(a, b) _memcheck_h_do_not_use("realloc") #define free(a) _memcheck_h_do_not_use("free")

#ifndef O_NOT_USE_MEMCHECK_H_FOPEN #define fopen(a, b) _memcheck_h_do_not_use("fopen") #define fdopen(a, b) _memcheck_h_do_not_use("fdopen") #define freopen(a, b, c) _memcheck_h_do_not_use("freopen") #define fclose(a) _memcheck_h_do_not_use("fclose") #endif /* O_NOT_USE_MEMCHECK_H_FOPEN */

#ifdef _MEMCHECK_H_SRCFILE #define mymalloc(x) mymymalloc((x), __FILE__, __LINE__) #define myfree(x) mymyfree((x), __FILE__, __LINE__) #endif /* _MEMCHECK_H_SRCFILE */ #endif /* _MEMCHECK_H */ /*----------- end of memcheck.h -----------*/

operation result

Perform headInsert at phase 0 a node added to head : 99 a node added to head : 89 99 a node added to head : 76 89 99 a node added to head : 65 76 89 99 a node added to head : 51 65 76 89 99 a node added to head : 43 51 65 76 89 99 a node added to head : 23 43 51 65 76 89 99 a node added to head : 18 23 43 51 65 76 89 99 a node added to head : 9 18 23 43 51 65 76 89 99 headInsert expected : 9 18 23 43 51 65 76 89 99 Perform headDelete at phase 0 deleting a head node : 9 18 23 43 51 65 76 89 99 deleting a head node : 18 23 43 51 65 76 89 99 deleting a head node : 23 43 51 65 76 89 99 deleting a head node : 43 51 65 76 89 99 deleting a head node : 51 65 76 89 99 deleting a head node : 65 76 89 99 deleting a head node : 76 89 99 deleting a head node : 89 99 deleting a head node : 99 headDelete performed okay. Perform tailInsert at phase 0 a node added to tail : 99 a node added to tail : 99 89 a node added to tail : 99 89 76 a node added to tail : 99 89 76 65 a node added to tail : 99 89 76 65 51 a node added to tail : 99 89 76 65 51 43 a node added to tail : 99 89 76 65 51 43 23 a node added to tail : 99 89 76 65 51 43 23 18 a node added to tail : 99 89 76 65 51 43 23 18 9 tailInsert expected : 99 89 76 65 51 43 23 18 9 Perform secondDelete at phase 0 deleting the next-to-head node : 99 89 76 65 51 43 23 18 9 deleting the next-to-head node : 99 76 65 51 43 23 18 9 deleting the next-to-head node : 99 65 51 43 23 18 9 deleting the next-to-head node : 99 51 43 23 18 9 deleting the next-to-head node : 99 43 23 18 9 deleting the next-to-head node : 99 23 18 9 deleting the next-to-head node : 99 18 9 deleting the next-to-head node : 99 9 deleting the next-to-head node : 99 secondDelete performed okay. End of this phase. Perform headInsert at phase 1 a node added to head : 512 a node added to head : 415 512 a node added to head : 328 415 512 a node added to head : 256 328 415 512 a node added to head : 128 256 328 415 512 headInsert expected : 128 256 328 415 512 Perform headDelete at phase 1 deleting a head node : 128 256 328 415 512 deleting a head node : 256 328 415 512 deleting a head node : 328 415 512 deleting a head node : 415 512 deleting a head node : 512 headDelete performed okay. Perform tailInsert at phase 1 a node added to tail : 512 a node added to tail : 512 415 a node added to tail : 512 415 328 a node added to tail : 512 415 328 256 a node added to tail : 512 415 328 256 128 tailInsert expected : 512 415 328 256 128 Perform secondDelete at phase 1 deleting the next-to-head node : 512 415 328 256 128 deleting the next-to-head node : 512 328 256 128 deleting the next-to-head node : 512 256 128 deleting the next-to-head node : 512 128 deleting the next-to-head node : 512 secondDelete performed okay. End of this phase. +++++ Checking memory... +++++ +++++ Memory is okay. +++++