lang/cem/libcc.ansi/stdlib/malloc/log.c

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