log.c 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129
  1. /* $Id$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. #include "param.h"
  7. #include "impl.h"
  8. #include "check.h"
  9. #include "log.h"
  10. /* Logical manipulations.
  11. The chunks are properly chained in the physical chain.
  12. */
  13. privatedata mallink *free_list[MAX_FLIST+1];
  14. public
  15. link_free_chunk(register mallink *ml)
  16. {
  17. /* The free chunk ml is inserted in its proper logical
  18. chain.
  19. */
  20. register mallink **mlp = &free_list[0];
  21. register size_type n = size_of(ml);
  22. register mallink *ml1;
  23. assert(n < (1L << LOG_MAX_SIZE));
  24. do {
  25. n >>= 1;
  26. mlp++;
  27. }
  28. while (n >= MIN_SIZE);
  29. ml1 = *--mlp;
  30. set_log_prev(ml, MAL_NULL);
  31. set_log_next(ml, ml1);
  32. calc_checksum(ml);
  33. if (ml1) {
  34. /* link backwards
  35. */
  36. set_log_prev(ml1, ml);
  37. calc_checksum(ml1);
  38. }
  39. *mlp = ml;
  40. }
  41. public
  42. unlink_free_chunk(register mallink *ml)
  43. {
  44. /* Unlinks a free chunk from (the middle of) the
  45. logical chain.
  46. */
  47. register mallink *next = log_next_of(ml);
  48. register mallink *prev = log_prev_of(ml);
  49. if (!prev) {
  50. /* it is the first in the chain */
  51. register mallink **mlp = &free_list[-1];
  52. register size_type n = size_of(ml);
  53. assert(n < (1L << LOG_MAX_SIZE));
  54. do {
  55. n >>= 1;
  56. mlp++;
  57. }
  58. while (n >= MIN_SIZE);
  59. *mlp = next;
  60. }
  61. else {
  62. set_log_next(prev, next);
  63. calc_checksum(prev);
  64. }
  65. if (next) {
  66. set_log_prev(next, prev);
  67. calc_checksum(next);
  68. }
  69. }
  70. public mallink *
  71. search_free_list(int class, size_t n)
  72. {
  73. /* Searches the free_list[class] for a chunk of at least size n;
  74. since it is searching a slightly undersized list,
  75. such a block may not be there.
  76. */
  77. register mallink *ml;
  78. for (ml = free_list[class]; ml; ml = log_next_of(ml))
  79. if (size_of(ml) >= n)
  80. return ml;
  81. return MAL_NULL; /* nothing found */
  82. }
  83. public mallink *
  84. first_present(int class)
  85. {
  86. /* Find the index i in free_list[] such that:
  87. i >= class && free_list[i] != MAL_NULL.
  88. Return MAL_NULL if no such i exists;
  89. Otherwise, return the first block of this list, after
  90. unlinking it.
  91. */
  92. register mallink **mlp, *ml;
  93. for (mlp = &free_list[class]; mlp < &free_list[MAX_FLIST]; mlp++) {
  94. if ((ml = *mlp) != MAL_NULL) {
  95. *mlp = log_next_of(ml); /* may be MAL_NULL */
  96. if (*mlp) {
  97. /* unhook backward link
  98. */
  99. set_log_prev(*mlp, MAL_NULL);
  100. calc_checksum(*mlp);
  101. }
  102. return ml;
  103. }
  104. }
  105. return MAL_NULL;
  106. }
  107. #ifdef CHECK
  108. public mallink *
  109. free_list_entry(int i) {
  110. /* To allow maldump.c access to log.c's private data.
  111. */
  112. return free_list[i];
  113. }
  114. #endif /* CHECK */