modules/src/malloc/log.c

   1 /* $Id: log.c,v 1.7 1994/06/24 11:17:51 ceriel Exp $ */
   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
  11 /*      Logical manipulations.
  12         The chunks are properly chained in the physical chain.
  13 */
  14
  15 privatedata mallink *free_list[MAX_FLIST];
  16
  17 public
  18 link_free_chunk(ml)
  19         register mallink *ml;
  20 {
  21         /*      The free chunk ml is inserted in its proper logical
  22                 chain.
  23         */
  24         register mallink **mlp = &free_list[-1];
  25         register size_type n = size_of(ml);
  26         register mallink *ml1;
  27
  28         assert(n < (1L << LOG_MAX_SIZE));
  29
  30         do {
  31                 n >>= 1;
  32                 mlp++;
  33         }
  34         while (n >= MIN_SIZE);
  35
  36         ml1 = *mlp;
  37         set_log_prev(ml, MAL_NULL);
  38         set_log_next(ml, ml1);
  39         calc_checksum(ml);
  40         if (ml1) {
  41                 /* link backwards
  42                 */
  43                 set_log_prev(ml1, ml);
  44                 calc_checksum(ml1);
  45         }
  46         *mlp = ml;
  47 }
  48
  49 public
  50 unlink_free_chunk(ml)
  51         register mallink *ml;
  52 {
  53         /*      Unlinks a free chunk from (the middle of) the
  54                 logical chain.
  55         */
  56         register mallink *next = log_next_of(ml);
  57         register mallink *prev = log_prev_of(ml);
  58
  59         if (!prev)      {
  60                 /* it is the first in the chain */
  61                 register mallink **mlp = &free_list[-1];
  62                 register size_type n = size_of(ml);
  63
  64                 assert(n < (1L << LOG_MAX_SIZE));
  65                 do {
  66                         n >>= 1;
  67                         mlp++;
  68                 }
  69                 while (n >= MIN_SIZE);
  70                 *mlp = next;
  71         }
  72         else    {
  73                 set_log_next(prev, next);
  74                 calc_checksum(prev);
  75         }
  76         if (next) {
  77                 set_log_prev(next, prev);
  78                 calc_checksum(next);
  79         }
  80 }
  81
  82 public mallink *
  83 search_free_list(class, n)
  84         unsigned int n;
  85 {
  86         /*      Searches the free_list[class] for a chunk of at least size n;
  87                 since it is searching a slightly undersized list,
  88                 such a block may not be there.
  89         */
  90         register mallink *ml;
  91
  92         for (ml = free_list[class]; ml; ml = log_next_of(ml))
  93                 if (size_of(ml) >= n)
  94                         return ml;
  95         return MAL_NULL;                /* nothing found */
  96 }
  97
  98 public mallink *
  99 first_present(class)
 100         int class;
 101 {
 102         /*      Find the index i in free_list[] such that:
 103                         i >= class && free_list[i] != MAL_NULL.
 104                 Return MAL_NULL if no such i exists;
 105                 Otherwise, return the first block of this list, after
 106                 unlinking it.
 107         */
 108         register mallink **mlp, *ml;
 109
 110         for (mlp = &free_list[class]; mlp < &free_list[MAX_FLIST]; mlp++) {
 111                 if ((ml = *mlp) != MAL_NULL)    {
 112
 113                         *mlp = log_next_of(ml); /* may be MAL_NULL */
 114                         if (*mlp) {
 115                                 /* unhook backward link
 116                                 */
 117                                 set_log_prev(*mlp, MAL_NULL);
 118                                 calc_checksum(*mlp);
 119                         }
 120                         return ml;
 121                 }
 122         }
 123         return MAL_NULL;
 124 }
 125
 126 #ifdef  CHECK
 127 public mallink *
 128 free_list_entry(i)      {
 129         /*      To allow maldump.c access to log.c's private data.
 130         */
 131         return free_list[i];
 132 }
 133 #endif  /* CHECK */