malloc.c 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127
  1. /*
  2. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  3. * See the copyright notice in the ACK home directory, in the file "Copyright".
  4. */
  5. /* $Header$ */
  6. #include <stdlib.h>
  7. #define CLICK_SIZE 4096
  8. #if EM_WSIZE == EM_PSIZE
  9. typedef unsigned int vir_bytes;
  10. #else
  11. typedef long vir_bytes;
  12. #endif
  13. #define ALIGN(x, a) (((x) + (a - 1)) & ~(a - 1))
  14. #define BUSY 1
  15. #define NEXT(p) (* (void **) (p))
  16. #ifdef pdp
  17. #define BUGFIX 64 /* cannot set break in top 64 bytes */
  18. #else
  19. #define BUGFIX 0
  20. #endif
  21. extern void bcopy(void *, void *, size_t);
  22. extern void *sbrk(unsigned int);
  23. extern void *brk(unsigned int);
  24. static void *bottom, *top;
  25. static int
  26. grow(size_t len)
  27. {
  28. register void *p;
  29. register int click = CLICK_SIZE;
  30. p = sbrk(0);
  31. len += (void *) ALIGN((vir_bytes) p, sizeof(void *)) - p;
  32. while (click >= 4) {
  33. size_t len1 = ALIGN((vir_bytes)p+len+sizeof(char *),click)-(vir_bytes)p;
  34. void *p1 = p;
  35. if (p + len1 + BUGFIX < p || (p1 = sbrk(len1)) == (void *) -1) {
  36. click >>= 1;
  37. continue;
  38. }
  39. p = p1;
  40. if (top + sizeof(void *) != p) {
  41. /* someone else has done an sbrk */
  42. NEXT(top) = (void *) ((vir_bytes) p | BUSY);
  43. } else {
  44. for (p = bottom; NEXT(p) != NULL; p = (void *) (* (vir_bytes *) p & ~BUSY))
  45. ;
  46. }
  47. top = p + len1 - sizeof(void *);
  48. NEXT(p) = top;
  49. NEXT(top) = NULL;
  50. return 1;
  51. }
  52. return 0;
  53. }
  54. void *
  55. malloc(size_t size)
  56. {
  57. register void *p, *next, *new;
  58. register size_t len = ALIGN(size, sizeof(void *)) + sizeof(void *);
  59. if ((p = bottom) == NULL) {
  60. p = sbrk(sizeof(void *));
  61. sbrk((void *) ALIGN((vir_bytes) p, sizeof(void *)) - p);
  62. p = (void *) ALIGN((vir_bytes) p, sizeof(void *));
  63. top = bottom = p;
  64. NEXT(p) = NULL;
  65. }
  66. while ((next = NEXT(p)) != NULL)
  67. if ((vir_bytes) next & BUSY) /* already in use */
  68. p = (void *) ((vir_bytes) next & ~BUSY);
  69. else {
  70. while ((new = NEXT(next)) != NULL
  71. && !((vir_bytes) new & BUSY))
  72. next = new;
  73. if (next - p >= len) { /* fits */
  74. if ((new = p + len) < next) /* too big */
  75. NEXT(new) = next;
  76. NEXT(p) = (void *) ((vir_bytes) new | BUSY);
  77. return(p + sizeof(void *));
  78. }
  79. p = next;
  80. }
  81. return grow(len) ? malloc(size) : (void *)NULL;
  82. }
  83. void *
  84. realloc(void *old, size_t size)
  85. {
  86. register void *p = old - sizeof(void *), *next, *new;
  87. register size_t len = ALIGN(size, sizeof(void *)) + sizeof(void *), n;
  88. next = (void *) (* (vir_bytes *) p & ~BUSY);
  89. n = next - old; /* old size */
  90. while ((new = NEXT(next)) != NULL && !((vir_bytes) new & BUSY))
  91. next = new;
  92. if (next - p >= len) { /* does it still fit */
  93. if ((new = p + len) < next) { /* even too big */
  94. NEXT(new) = next;
  95. NEXT(p) = (void *) ((vir_bytes) new | BUSY);
  96. }
  97. else
  98. NEXT(p) = (void *) ((vir_bytes) next | BUSY);
  99. return(old);
  100. }
  101. if ((new = malloc(size)) == NULL) /* it didn't fit */
  102. return((void *)NULL);
  103. bcopy(old, new, n); /* n < size */
  104. * (vir_bytes *) p &= ~BUSY;
  105. return(new);
  106. }
  107. void
  108. free(void *p)
  109. {
  110. if (p != (void *)NULL)
  111. *(vir_bytes *) (p - sizeof(void *)) &= ~BUSY;
  112. }