sscanf

  1. /* Function: read_line
  2.  * --------------------
  3.  * Reads one line from file and stores in buf. Skips lines that are all-white or beginning with
  4.  * comment char #. Increments pass-by-ref counter of number of lines read/skipped. Removes
  5.  * trailing newline. Returns true if did read valid line, false otherwise.
  6.  */
  7. static bool read_line(char buf[], size_t bufsz, FILE *fp, int *pnread)
  8. {
  9.     while (true) {
  10.         if (fgets(buf, bufsz, fp) == NULL) return false;
  11.         (*pnread)++;
  12.         if (buf[strlen(buf)-1] == '\n') buf[strlen(buf)-1] ='\0'; // remove trailing newline
  13.         char ch;
  14.         if (sscanf(buf, " %c", &ch) == 1 && ch != '#') // scan first non-white char, check not #
  15.             return true;
  16.     }
  17. }

image.png
The scanf() function reads input from the standard input stream stdin, fscanf() reads input from the stream pointer stream, and sscanf() reads its input from the character string pointed to by str.
image.png

1) Code study: test harness

  1. // struct for a single allocator request
  2. typedef struct {
  3.     enum {ALLOC=1, FREE, REALLOC} op;    // type of request
  4.     int id;                // id for free() to use later
  5.     size_t size;        // num bytes for alloc/realloc request
  6.     int lineno;         // which line in file
  7. } request_t;
  9. // struct for facts about a single malloc'ed node
  10. typedef struct {
  11.     void *ptr;
  12.     size_t size;
  13. } block_t;
  15. // struct for info for one script file
  16. typedef struct {
  17.     char name[128];        // short name of script
  18.     request_t *ops;        // array of requests read from script
  19.     int num_ops;        // number of requests
  20.     int num_ids;        // number of distinct block ids
  21.     block_t *blocks;    // array of blocks returned by malloc when executing
  22.     size_t peak, lifetime, segment_size;
  23. } script_t;
  1. /* Function: eval_correctness
  2.  * --------------------------
  3.  * Check the allocator for correctness on given script. Interprets the earlier parsed
  4.  * script operation-by-operation and reports if it detects any "obvious"
  5.  * errors (returning blocks outside the heap, unaligned, overlapping blocks, etc.)
  6.  */
  7. static bool eval_correctness(script_t *script)
  8. {
  9.     init_heap_segment(script->segment_size);
  10.     if (!myinit(heap_segment_start(), heap_segment_size())) {
  11.         allocator_error(script, 0, "myinit() returned false");
  12.         return false;
  13.     }
  14.     if (!validate_heap()) { // check heap consistency after init
  15.         allocator_error(script, 0, "validate_heap() returned false, called after myinit");
  16.         return false;
  17.     }
  18.     memset(script->blocks, 0, script->num_ids*sizeof(script->blocks[0]));
  20.     for (int req = 0; req < script->num_ops; req++) {
  21.         int id = script->ops[req].id;
  22.         size_t requested_size = script->ops[req].size;
  23.         size_t old_size = script->blocks[id].size;
  24.         void *p, *newp, *oldp = script->blocks[id].ptr;
  26.         switch (script->ops[req].op) {
  28.             case ALLOC:
  29.                 if ((p = mymalloc(requested_size)) == NULL && requested_size != 0) {
  30.                     allocator_error(script, script->ops[req].lineno, "heap exhausted, malloc returned NULL");
  31.                     return false;
  32.                 }
  33.                 // Test new block for correctness: must be properly aligned
  34.                 // and must not overlap any currently allocated block.
  35.                 if (!verify_block(p, requested_size, script, script->ops[req].lineno))
  36.                     return false;
  38.                 // Fill new block with the low-order byte of new id
  39.                 // can be used later to verify data copied when realloc'ing
  40.                 memset(p, id & 0xFF, requested_size);
  41.                 script->blocks[id] = (block_t){.ptr = p, .size = requested_size};
  42.                 break;
  44.             case REALLOC:
  45.                 if (!verify_payload(oldp, old_size, id, script, script->ops[req].lineno, "realloc-ing"))
  46.                     return false;
  47.                 if ((newp = myrealloc(oldp, requested_size)) == NULL && requested_size != 0) {
  48.                     allocator_error(script, script->ops[req].lineno, "heap exhausted, realloc returned NULL");
  49.                     return false;
  50.                 }
  52.                 old_size = script->blocks[id].size;
  53.                 script->blocks[id].size = 0;
  54.                 if (!verify_block(newp, requested_size, script, script->ops[req].lineno))
  55.                     return false;
  56.                 // Verify new block contains the data from the old block
  57.                 for (size_t j = 0; j < (old_size < requested_size ? old_size : requested_size); j++) {
  58.                     if (*((unsigned char *)newp + j) != (id & 0xFF)) {
  59.                         allocator_error(script, script->ops[req].lineno, "realloc did not preserve the data from old block");
  60.                         return false;
  61.                     }
  62.                 }
  63.                 // Fill new block with the low-order byte of new id
  64.                 memset(newp, id & 0xFF, requested_size);
  65.                 script->blocks[id] = (block_t){.ptr = newp, .size = requested_size};
  66.                 break;
  68.             case FREE:
  69.                 old_size = script->blocks[id].size;
  70.                 p = script->blocks[id].ptr;
  71.                 // verify payload intact before free
  72.                 if (!verify_payload(p, old_size, id, script, script->ops[req].lineno, "freeing"))
  73.                     return false;
  74.                 script->blocks[id] = (block_t){.ptr = NULL, .size = 0};
  75.                 myfree(p);
  76.                 break;
  77.         }
  79.         if (!validate_heap()) { // check heap consistency after each request
  80.             allocator_error(script, script->ops[req].lineno, "validate_heap() returned false, called in-between requests");
  81.             return false;   // stop at first sign of error
  82.         }
  83.     }
  85.     // verify payload is still intact for any block still allocated
  86.     for (int id = 0;  id < script->num_ids;  id++)
  87.         if (!verify_payload(script->blocks[id].ptr, script->blocks[id].size, id, script, -1, "at exit"))
  88.             return false;
  89.     return true;
  90. }

fprintf

C 库函数 int fprintf(FILE stream, const char format, …) 发送格式化输出到流 stream 中。
image.png

memset

image.png

2) Code study: bump allocator

  1. /*
  2.  * File: bump.c
  3.  * ------------
  4.  * A very simple "bump" allocator.
  5.  * An allocation request is serviced by tacking on the requested
  6.  * space to the end of the heap thus far. 
  7.  * Free is a no-op: blocks are never coalesced or reused.
  8.  * Realloc is implemented using malloc/memcpy/free. Operations
  9.  * are fast, but utilization is terrible.
  10.  *
  11.  * Shows the very simplest of approaches; there are better options!
  12.  */
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <string.h>
  16. #include "allocator.h"
  18. #define ALIGNMENT 8
  20. static void *next_avail, *heap_max;
  22. // Efficient bitwise round up to nearest multiple (you saw this code in lab1)
  23. // NOTE: mult has to be power of 2 for the bitwise trick to work!
  24. size_t roundup(size_t sz, size_t mult)
  25. {
  26.     return (sz + mult-1) & ~(mult-1);
  27. }
  29. // initialize global variables based on segment boundaries
  30. bool myinit(void *segment_start, size_t segment_size)
  31. {
  32.     next_avail = segment_start;
  33.     heap_max = (char *)segment_start + segment_size;
  34.     return true;
  35. }
  37. // place block at end of heap
  38. // no search means fast but no recycle makes for terrible utilization
  39. void *mymalloc(size_t requestedsz)
  40. {
  41.     size_t needed = roundup(requestedsz, ALIGNMENT);
  42.     if ((char *)next_avail + needed > (char *)heap_max)
  43.         return NULL;
  44.     void *alloc = next_avail;
  45.     next_avail = (char *)next_avail + needed;
  46.     return alloc;
  47. }
  49. // free does nothing.  fast!... but lame :(
  50. void myfree(void *ptr)
  51. {
  52. }
  54. // realloc built on malloc/memcpy/free is easy to write but not particularly efficient
  55. void *myrealloc(void *oldptr, size_t newsz)
  56. {
  57.     void *newptr = mymalloc(newsz);
  58.     if (!newptr) return NULL;
  59.     memcpy(newptr, oldptr, newsz);
  60.     myfree(oldptr);
  61.     return newptr;
  62. }
  64. // debugging routine to detect/report inconsistencies in heap data structures
  65. bool validate_heap()
  66. {
  67.     if (next_avail > heap_max) {
  68.         printf("Oops! Next available spot is beyond heap end!!\n");
  69.         return false;
  70.     }
  71.     return true;
  72. }

3) Implement implicit free list

  1. #include "allocator.h"
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <stdio.h>
  6. #define ALIGNMENT 8
  7. #define SIZE_T 8
  8. #define MINBLK 24
  9. #define MINBLK_NOHEADFOOT 8
  10. #define HEADFOOT_NOCONTENT 16
  11. #define ONE     0x0000000000000001
  12. #define MULT8   0xFFFFFFFFFFFFFFF8
  13. #define NOT_ONE 0xFFFFFFFFFFFFFFFE
  15. //min acceptable ptr: seg min rounded up
  16. static char *heap_min;
  17. //max acceptable ptr: (seg min + seg sz) rounded down - min blk sz
  18. static char *heap_max;
  20. /*
  21. assumptions
  22. - when given a block pointer char*ptr, it's ok to access its header and footer
  23. */
  24. size_t rounddown(size_t, size_t);
  25. inline size_t rounddown(size_t sz, size_t mult){
  26.   return ~(mult-1) & sz;
  27. }
  29. size_t roundup(size_t, size_t);
  30. inline size_t roundup(size_t sz, size_t mult){
  31.   return (sz + mult-1) & ~(mult-1);
  32. }
  34. char *getsizeptr1(char *);
  35. inline char *getsizeptr1(char *ptr){
  36.   return ptr;
  37. }
  39. size_t ptr2size(char *);
  40. inline size_t ptr2size(char *ptr){
  41.   return *(size_t*)ptr & MULT8;
  42. }
  44. size_t getsize(char *);
  45. inline size_t getsize(char *ptr){
  46.   return ptr2size(getsizeptr1(ptr));
  47. }
  49. char *getsizeptr2(char *);
  50. inline char *getsizeptr2(char *ptr){
  51.   ptr += getsize(ptr) - SIZE_T;
  52.   return ptr;
  53. }
  55. void setsize_setfree(char *, size_t);
  56. inline void setsize_setfree(char *ptr, size_t sz){
  57.   *(size_t*)ptr = sz;
  58.   ptr += sz - SIZE_T;
  59.   *(size_t*)ptr = sz;
  60. }
  62. void setsize_setalloc(char *, size_t);
  63. inline void setsize_setalloc(char *ptr, size_t sz){
  64.   *(size_t*)ptr = sz | ONE;
  65.   ptr += sz - SIZE_T;
  66.   *(size_t*)ptr = sz | ONE;
  67. }
  69. bool isalloc(char *);
  70. inline bool isalloc(char *ptr){
  71.   return *getsizeptr1(ptr) & 0x01;
  72. }
  74. bool setalloc(char *);
  75. inline bool setalloc(char *ptr){
  76.   char *sizeptr1 = getsizeptr1(ptr);
  77.   char *sizeptr2 = getsizeptr2(ptr);
  78.   bool orig = *sizeptr1 & 0x01;
  79.   *sizeptr1 = *sizeptr1 | 0x01;
  80.   *sizeptr2 = *sizeptr1;
  81.   return orig;
  82. }
  84. bool setfree(char *);
  85. inline bool setfree(char *ptr){
  86.   char *sizeptr1 = getsizeptr1(ptr);
  87.   char *sizeptr2 = getsizeptr2(ptr);
  88.   bool orig = *sizeptr1 & 0x01;
  89.   *sizeptr1 = *sizeptr1 & 0xFE;
  90.   *sizeptr2 = *sizeptr1;
  91.   return orig;
  92. }
  94. //sz must be getsize(ptr)
  95. char *upstairs2(char *, size_t);
  96. inline char *upstairs2(char *ptr, size_t sz){
  97.   ptr += sz;
  98.   if (ptr > heap_max)
  99.     return NULL;
  100.   return ptr;
  101. }
  103. char *upstairs1(char *);
  104. inline char *upstairs1(char *ptr){
  105.   return upstairs2(ptr, getsize(ptr));
  106. }
  108. char *downstairs(char *);
  109. inline char *downstairs(char *ptr){
  110.   if (ptr < heap_min + MINBLK)
  111.     return NULL;
  112.   return ptr - ptr2size(ptr - SIZE_T);
  113. }
  115. //how about a while loop
  116. //sz must be &(getsize(ptr))
  117. void check_up(char *, size_t *);
  118. inline void check_up(char *ptr, size_t *sz){
  119.   ptr = upstairs2(ptr, *sz);
  120.   if (ptr != NULL && !isalloc(ptr)){
  121.     *sz += getsize(ptr);
  122.   }
  123. }
  125. void check_down(char **, size_t *);
  126. inline void check_down(char **ptr, size_t *sz){
  127.   char *down = downstairs(*ptr);
  128.   if (down != NULL && !isalloc(down)){
  129.     *sz += getsize(down);
  130.     *ptr = down;
  131.   }
  132. }
  134. //given ptr and sz of a blk, initialize blk to free
  135. //attach blk to front of free list
  136. void initutil(char *, size_t);
  137. inline void initutil(char *ptr, size_t sz){
  138.   check_up(ptr, &sz);
  139.   check_down(&ptr, &sz);
  140.   setsize_setfree(ptr, sz);
  141. }
  143. //input requested size
  144. //output aligned block size
  145. size_t pumpsz(size_t);
  146. inline size_t pumpsz(size_t sz){
  147.   if (sz <= MINBLK_NOHEADFOOT)
  148.     return MINBLK;
  149.   sz = roundup(sz, ALIGNMENT);
  150.   return sz + HEADFOOT_NOCONTENT;
  151. }
  153. ////////////////////////////////////////
  155. bool myinit(void *, size_t);
  156. inline bool myinit(void *reqstart, size_t reqsz){
  157.   if (reqstart == NULL)
  158.     return false;
  159.   char *reqend = (char *)reqstart + reqsz;
  160.   // are these aligned already?
  161.   char *start = (char*)roundup((size_t)reqstart, ALIGNMENT);
  162.   char *end = (char*)rounddown((size_t)reqend, ALIGNMENT);
  163.   size_t sz = end - start;
  164.   heap_min = (char*)start;
  165.   heap_max = (char*)start + sz - MINBLK;
  166.   initutil(start, sz);
  167.   return true;
  168. }
  170. void *mymalloc(size_t sz){
  171.   sz = pumpsz(sz);
  172.   char *ptr = heap_min;
  173.   //first fit
  174.   while (ptr <= heap_max){
  175.     if (isalloc(ptr)){
  176.       ptr = upstairs1(ptr);
  177.       continue;
  178.     }
  179.     size_t blocksz = getsize(ptr);
  181.     //has needed space +  min free block in bytes. split
  182.     if (blocksz >= sz + MINBLK){
  183.       setsize_setalloc(ptr, sz);
  184.       initutil(ptr + sz, blocksz - sz);
  185.       return ptr + SIZE_T;//internal -> client ptr
  186.     }
  187.     //not enough to split. allocate whole
  188.     if (blocksz >= sz){
  189.       setalloc(ptr);
  190.       return ptr + SIZE_T;
  191.     }
  192.     ptr = upstairs2(ptr, blocksz);
  193.   }
  194.   return NULL;
  195. }
  197. void myfree(void *);
  198. inline void myfree(void *ptrv){
  199.   char *ptr = (char *)ptrv - SIZE_T;//client -> internal ptr
  200.   if (ptr < heap_min ||
  201.       ptr > heap_max ||
  202.       !isalloc(ptr)){
  203.     //printf("\ninvalid free\nheap_min %lx\nheap_max %lx\nptr %lx\n",
  204.     //       (size_t)heap_min, (size_t)heap_max, (size_t)ptr);
  205.     //exit(1346347);
  206.   }else{
  207.     initutil(ptr, getsize(ptr));
  208.   }
  209. }
  211. void *myrealloc(void *oldptrv, size_t newsz){
  212.   char *oldptr = (char *)oldptrv - SIZE_T;//client -> internal ptr
  213.   newsz = pumpsz(newsz);
  214.   size_t oldsz = getsize(oldptr);
  215.   if (oldsz >= newsz + MINBLK){
  216.     setsize_setalloc(oldptr, newsz);
  217.     initutil(oldptr + newsz, oldsz - newsz);
  218.     return oldptrv;//client ptr
  219.   }
  220.   if (oldsz >= newsz)
  221.     return oldptrv;//client ptr
  223.   char *up = upstairs2(oldptr, oldsz);
  224.   char *down = downstairs(oldptr);
  225.   size_t szup = (up != NULL && !isalloc(up))?
  226.                 getsize(up):0;
  227.   size_t szdown = (down != NULL && !isalloc(down))?
  228.                 getsize(down):0;
  230.   if (oldsz + szup >= newsz + MINBLK){
  231.     setsize_setalloc(oldptr, newsz);
  232.     initutil(oldptr + newsz, oldsz + szup - newsz);
  233.     return oldptr + SIZE_T;//internal -> client ptr
  234.   }
  235.   if (oldsz + szup >= newsz){
  236.     setsize_setalloc(oldptr, oldsz + szup);
  237.     return oldptr + SIZE_T;//internal -> client ptr
  238.   }
  239.   if (oldsz + szdown >= newsz + MINBLK){
  240.     char *newptr = oldptr + oldsz - newsz;
  241.     memmove(newptr, oldptr, oldsz);
  242.     setsize_setalloc(newptr, newsz);
  243.     initutil(down, oldsz + szdown - newsz);
  244.     return newptr + SIZE_T;//internal -> client ptr
  245.   }
  246.   if (oldsz + szdown >= newsz){
  247.     memmove(down, oldptr, oldsz);
  248.     setsize_setalloc(down, oldsz + szdown);
  249.     return down + SIZE_T;//internal -> client ptr
  250.   }
  251.   if (oldsz + szdown + szup >= newsz + MINBLK){
  252.     char *newptr = oldptr + oldsz + szup - newsz;
  253.     memmove(newptr, oldptr, oldsz);
  254.     setsize_setalloc(newptr, newsz);
  255.     initutil(down, oldsz + szup + szdown - newsz);
  256.     return newptr + SIZE_T;//internal -> client ptr
  257.   }
  258.   if (oldsz + szdown + szup >= newsz){
  259.     memmove(down, oldptr, oldsz);
  260.     setsize_setalloc(down, oldsz + szdown + szup);
  261.     return down + SIZE_T;//internal -> client ptr
  262.   }
  263.   char *ptr = heap_min;
  264.   while (ptr <= heap_max){
  265.     if (isalloc(ptr)){
  266.       ptr = upstairs1(ptr);
  267.       continue;
  268.     }
  269.     size_t ptrsz = getsize(ptr);
  270.     if (ptrsz >= newsz + MINBLK){
  271.       memcpy(ptr, oldptr, oldsz);
  272.       //what if newsz real small? no way. newsz > oldsz here
  273.       setsize_setalloc(ptr, newsz);
  274.       initutil(ptr + newsz, ptrsz - newsz);
  275.       initutil(oldptr, oldsz);
  276.       return ptr + SIZE_T;//internal -> client ptr
  277.     }
  278.     if (ptrsz >= newsz){
  279.       memcpy(ptr, oldptr, oldsz);
  280.       setsize_setalloc(ptr, ptrsz);
  281.       initutil(oldptr, oldsz);
  282.       return ptr + SIZE_T;//internal -> client ptr
  283.     }
  284.     ptr = upstairs2(ptr, ptrsz);
  285.   }
  286.   return NULL;
  287. }
  289. bool validate_heap(){
  290.   return true;
  291. }

4) Implement explicit free list

  1. #include "allocator.h"
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <stdio.h>
  6. #define ALIGNMENT 8
  7. #define SIZE_T 8
  8. #define MINBLK 32
  9. #define PTRSZ 16
  10. #define HEADFOOT_NOPTR 16
  11. #define ONE     0x0000000000000001
  12. #define MULT8   0xFFFFFFFFFFFFFFF8
  13. #define NOT_ONE 0xFFFFFFFFFFFFFFFE
  15. //head of free list
  16. static char *head;
  17. //min acceptable ptr: seg min rounded up
  18. static char *heap_min;
  19. //max acceptable ptr: (seg min + seg sz) rounded down - min blk sz
  20. static char *heap_max;
  22. /*
  23. assumptions
  24. - when given a block pointer char*ptr, it's ok to access its header and footer
  25. */
  26. size_t rounddown(size_t, size_t);
  27. inline size_t rounddown(size_t sz, size_t mult){
  28.   return ~(mult-1) & sz;
  29. }
  31. size_t roundup(size_t, size_t);
  32. inline size_t roundup(size_t sz, size_t mult){
  33.   return (sz + mult-1) & ~(mult-1);
  34. }
  36. char *getsizeptr1(char *);
  37. inline char *getsizeptr1(char *ptr){
  38.   return ptr;
  39. }
  41. size_t ptr2size(char *);
  42. inline size_t ptr2size(char *ptr){
  43.   return *(size_t*)ptr & MULT8;
  44. }
  46. size_t getsize(char *);
  47. inline size_t getsize(char *ptr){
  48.   return ptr2size(getsizeptr1(ptr));
  49. }
  51. char *getsizeptr2(char *);
  52. inline char *getsizeptr2(char *ptr){
  53.   ptr += getsize(ptr) - SIZE_T;
  54.   return ptr;
  55. }
  57. void setsize_setfree(char *, size_t);
  58. inline void setsize_setfree(char *ptr, size_t sz){
  59.   *(size_t*)ptr = sz;
  60.   ptr += sz - SIZE_T;
  61.   *(size_t*)ptr = sz;
  62. }
  64. void setsize_setalloc(char *, size_t);
  65. inline void setsize_setalloc(char *ptr, size_t sz){
  66.   *(size_t*)ptr = sz | ONE;
  67.   ptr += sz - SIZE_T;
  68.   *(size_t*)ptr = sz | ONE;
  69. }
  71. bool isalloc(char *);
  72. inline bool isalloc(char *ptr){
  73.   return *getsizeptr1(ptr) & 0x01;
  74. }
  76. bool setalloc(char *);
  77. inline bool setalloc(char *ptr){
  78.   char *sizeptr1 = getsizeptr1(ptr);
  79.   char *sizeptr2 = getsizeptr2(ptr);
  80.   bool orig = *sizeptr1 & 0x01;
  81.   *sizeptr1 = *sizeptr1 | 0x01;
  82.   *sizeptr2 = *sizeptr1;
  83.   return orig;
  84. }
  86. bool setfree(char *);
  87. inline bool setfree(char *ptr){
  88.   char *sizeptr1 = getsizeptr1(ptr);
  89.   char *sizeptr2 = getsizeptr2(ptr);
  90.   bool orig = *sizeptr1 & 0x01;
  91.   *sizeptr1 = *sizeptr1 & 0xFE;
  92.   *sizeptr2 = *sizeptr1;
  93.   return orig;
  94. }
  96. char *getprevptr(char *ptr);
  97. inline char *getprevptr(char *ptr){
  98.   return (char *)*(size_t*)(ptr + SIZE_T);
  99. }
  101. void setprevptr(char *, char *);
  102. inline void setprevptr(char *ptr, char *prev){
  103.   ptr += SIZE_T;
  104.   *(size_t*)ptr = (size_t)prev;
  105. }
  107. char *getnextptr(char *ptr);
  108. inline char *getnextptr(char *ptr){
  109.   return (char *)*(size_t*)(ptr + 2*SIZE_T);;
  110. }
  112. void setnextptr(char *, char *);
  113. inline void setnextptr(char *ptr, char *next){
  114.   ptr += 2*SIZE_T;
  115.   *(size_t*)ptr = (size_t)next;
  116. }
  118. //given ptr of a free blk, remove blk from free list
  119. void bypasslist(char *);
  120. inline void bypasslist(char *ptr){
  121.   char *prev = getprevptr(ptr);
  122.   char *next = getnextptr(ptr);
  123.   if (prev != NULL)
  124.     setnextptr(prev, next);
  125.   if (next != NULL)
  126.     setprevptr(next, prev);
  127.   if (head == ptr)
  128.     head = next;
  129. }
  131. //sz must be getsize(ptr)
  132. char *upstairs2(char *, size_t);
  133. inline char *upstairs2(char *ptr, size_t sz){
  134.   ptr += sz;
  135.   if (ptr > heap_max)
  136.     return NULL;
  137.   return ptr;
  138. }
  140. char *upstairs1(char *);
  141. inline char *upstairs1(char *ptr){
  142.   return upstairs2(ptr, getsize(ptr));
  143. }
  145. char *downstairs(char *);
  146. inline char *downstairs(char *ptr){
  147.   if (ptr < heap_min + MINBLK)
  148.     return NULL;
  149.   return ptr - ptr2size(ptr - SIZE_T);
  150. }
  152. //how about a while loop
  153. //sz must be &(getsize(ptr))
  154. void check_bypass_up(char *, size_t *);
  155. inline void check_bypass_up(char *ptr, size_t *sz){
  156.   ptr = upstairs2(ptr, *sz);
  157.   if (ptr != NULL && !isalloc(ptr)){
  158.     *sz += getsize(ptr);
  159.     bypasslist(ptr);
  160.   }
  161. }
  163. void check_bypass_down(char **, size_t *);
  164. inline void check_bypass_down(char **ptr, size_t *sz){
  165.   char *down = downstairs(*ptr);
  166.   if (down != NULL && !isalloc(down)){
  167.     *sz += getsize(down);
  168.     bypasslist(down);
  169.     *ptr = down;
  170.   }
  171. }
  173. //given ptr and sz of a blk, initialize blk to free
  174. //attach blk to front of free list
  175. void initutil(char *, size_t);
  176. inline void initutil(char *ptr, size_t sz){
  177.   check_bypass_up(ptr, &sz);
  178.   check_bypass_down(&ptr, &sz);
  179.   if (head != NULL){
  180.     setprevptr(head, ptr);
  181.   }
  182.   setnextptr(ptr, head);
  183.   setprevptr(ptr, NULL);
  184.   setsize_setfree(ptr, sz);
  185.   head = ptr;
  186. }
  188. //input requested size
  189. //output aligned block size
  190. size_t pumpsz(size_t);
  191. inline size_t pumpsz(size_t sz){
  192.   if (sz < PTRSZ)
  193.     return MINBLK;
  194.   sz = roundup(sz, ALIGNMENT);
  195.   return sz + HEADFOOT_NOPTR;
  196. }
  198. ////////////////////////////////////////
  200. bool myinit(void *, size_t);
  201. inline bool myinit(void *reqstart, size_t reqsz){
  202.   if (reqstart == NULL)
  203.     return false;
  204.   char *reqend = (char *)reqstart + reqsz;
  205.   // are these aligned already?
  206.   char *start = (char*)roundup((size_t)reqstart, ALIGNMENT);
  207.   char *end = (char*)rounddown((size_t)reqend, ALIGNMENT);
  208.   size_t sz = end - start;
  209.   heap_min = (char*)start;
  210.   heap_max = (char*)start + sz - MINBLK;
  211.   head = NULL;
  212.   initutil(start, sz);
  213.   return true;
  214. }
  216. void *mymalloc(size_t sz){
  217.   sz = pumpsz(sz);
  218.   char *ptr = head;
  219.   //first fit
  220.   while (ptr != NULL){
  221.     size_t blocksz = getsize(ptr);
  223.     //has needed space +  min free block in bytes. split
  224.     if (blocksz >= sz + MINBLK){
  225.       bypasslist(ptr);
  226.       setsize_setalloc(ptr, sz);
  227.       initutil(ptr + sz, blocksz - sz);
  228.       return ptr + SIZE_T;//internal -> client ptr
  229.     }
  230.     //not enough to split. allocate whole
  231.     if (blocksz >= sz){
  232.       bypasslist(ptr);
  233.       setalloc(ptr);
  234.       return ptr + SIZE_T;
  235.     }
  236.     ptr = getnextptr(ptr);
  237.   }
  238.   return NULL;
  239. }
  241. void myfree(void *);
  242. inline void myfree(void *ptrv){
  243.   char *ptr = (char *)ptrv - SIZE_T;//client -> internal ptr
  244.   if (ptr < heap_min ||
  245.       ptr > heap_max ||
  246.       !isalloc(ptr)){
  247.     //printf("\ninvalid free\nheap_min %lx\nheap_max %lx\nptr %lx\n",
  248.     //       (size_t)heap_min, (size_t)heap_max, (size_t)ptr);
  249.     //exit(1346347);
  250.   }else{
  251.     initutil(ptr, getsize(ptr));
  252.   }
  253. }
  255. void *myrealloc(void *oldptrv, size_t newsz){
  256.   char *oldptr = (char *)oldptrv - SIZE_T;//client -> internal ptr
  257.   newsz = pumpsz(newsz);
  258.   size_t oldsz = getsize(oldptr);
  259.   if (oldsz >= newsz + MINBLK){
  260.     setsize_setalloc(oldptr, newsz);
  261.     initutil(oldptr + newsz, oldsz - newsz);
  262.     return oldptrv;//client ptr
  263.   }
  264.   if (oldsz >= newsz)
  265.     return oldptrv;//client ptr
  267.   char *up = upstairs2(oldptr, oldsz);
  268.   char *down = downstairs(oldptr);
  269.   size_t szup = (up != NULL && !isalloc(up))?
  270.                 getsize(up):0;
  271.   size_t szdown = (down != NULL && !isalloc(down))?
  272.                 getsize(down):0;
  274.   if (oldsz + szup >= newsz + MINBLK){
  275.     bypasslist(up);
  276.     setsize_setalloc(oldptr, newsz);
  277.     initutil(oldptr + newsz, oldsz + szup - newsz);
  278.     return oldptr + SIZE_T;//internal -> client ptr
  279.   }
  280.   if (oldsz + szup >= newsz){
  281.     bypasslist(up);
  282.     setsize_setalloc(oldptr, oldsz + szup);
  283.     return oldptr + SIZE_T;//internal -> client ptr
  284.   }
  285.   if (oldsz + szdown >= newsz + MINBLK){
  286.     bypasslist(down);
  287.     char *newptr = oldptr + oldsz - newsz;
  288.     memmove(newptr, oldptr, oldsz);
  289.     setsize_setalloc(newptr, newsz);
  290.     initutil(down, oldsz + szdown - newsz);
  291.     return newptr + SIZE_T;//internal -> client ptr
  292.   }
  293.   if (oldsz + szdown >= newsz){
  294.     bypasslist(down);
  295.     memmove(down, oldptr, oldsz);
  296.     setsize_setalloc(down, oldsz + szdown);
  297.     return down + SIZE_T;//internal -> client ptr
  298.   }
  299.   if (oldsz + szdown + szup >= newsz + MINBLK){
  300.     bypasslist(up);
  301.     bypasslist(down);
  302.     char *newptr = oldptr + oldsz + szup - newsz;
  303.     memmove(newptr, oldptr, oldsz);
  304.     setsize_setalloc(newptr, newsz);
  305.     initutil(down, oldsz + szup + szdown - newsz);
  306.     return newptr + SIZE_T;//internal -> client ptr
  307.   }
  308.   if (oldsz + szdown + szup >= newsz){
  309.     bypasslist(up);
  310.     bypasslist(down);
  311.     memmove(down, oldptr, oldsz);
  312.     setsize_setalloc(down, oldsz + szdown + szup);
  313.     return down + SIZE_T;//internal -> client ptr
  314.   }
  315.   char *ptr = head;
  316.   while (ptr != NULL){
  317.     size_t ptrsz = getsize(ptr);
  318.     if (ptrsz >= newsz + MINBLK){
  319.       bypasslist(ptr);
  320.       memcpy(ptr, oldptr, oldsz);
  321.       //what if newsz real small? no way. newsz > oldsz here
  322.       setsize_setalloc(ptr, newsz);
  323.       initutil(ptr + newsz, ptrsz - newsz);
  324.       initutil(oldptr, oldsz);
  325.       return ptr + SIZE_T;//internal -> client ptr
  326.     }
  327.     if (ptrsz >= newsz){
  328.       bypasslist(ptr);
  329.       memcpy(ptr, oldptr, oldsz);
  330.       setsize_setalloc(ptr, ptrsz);
  331.       initutil(oldptr, oldsz);
  332.       return ptr + SIZE_T;//internal -> client ptr
  333.     }
  334.     ptr = getnextptr(ptr);
  335.   }
  336.   return NULL;
  337. }
  339. bool validate_heap(){
  340.   return true;
  341. }