heap.c

   1 static char RCSId[] = "$Id: heap.c,v 1.3 1993/07/04 04:04:21 root Exp root $";
   2 static char Copyright[] = "Copyright  Robert J. Amstadt, 1993";
   3
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include "prototypes.h"
   7 #include "segmem.h"
   8 #include "heap.h"
   9
  10 MDESC *LOCAL_FreeList;
  11
  12 /**********************************************************************
  13  *                                      HEAP_Init
  14  */
  15 void
  16 HEAP_Init(MDESC **free_list, void *start, int length)
  17 {
  18     *free_list = (MDESC *) start;
  19     (*free_list)->prev = NULL;
  20     (*free_list)->next = NULL;
  21     (*free_list)->length = length - sizeof(MDESC);
  22 }
  23
  24 /**********************************************************************
  25  *                                      HEAP_Alloc
  26  */
  27 void *
  28 HEAP_Alloc(MDESC **free_list, int flags, int bytes)
  29 {
  30     MDESC *m, *m_new;
  31
  32 #ifdef DEBUG_HEAP
  33     printf("HeapAlloc: free_list %08x, flags %x, bytes %d\n",
  34            free_list, flags, bytes);
  35 #endif
  36
  37     /*
  38      * Find free block big enough.
  39      */
  40     for (m = *free_list; m != NULL; m = m->next)
  41     {
  42         if (m->length >= bytes && m->length < bytes + 4 * sizeof(MDESC))
  43         {
  44             break;
  45         }
  46         else if (m->length > bytes)
  47         {
  48             m_new = m + (bytes / sizeof(MDESC)) + 2;
  49             if (m->prev == NULL)
  50                 *free_list = m_new;
  51             else
  52                 m->prev->next = m_new;
  53
  54             if (m->next != NULL)
  55                 m->next->prev = m_new;
  56
  57             m_new->next = m->next;
  58             m_new->prev = m->prev;
  59             m_new->length = m->length - ((int) m_new - (int) m);
  60             m->length -= (m_new->length + sizeof(MDESC));
  61
  62             m->prev = m;
  63             m->next = m;
  64             return (void *) (m + 1);
  65         }
  66     }
  67
  68     if (m != NULL)
  69     {
  70         if (m->prev == NULL)
  71             *free_list = m->next;
  72         else
  73             m->prev->next = m->next;
  74
  75         if (m->next != NULL)
  76             m->next->prev = m->prev;
  77
  78         m->prev = m;
  79         m->next = m;
  80         return (void *) (m + 1);
  81     }
  82
  83     return 0;
  84 }
  85
  86 /**********************************************************************
  87  *                                      HEAP_Free
  88  */
  89 void
  90 HEAP_Free(MDESC **free_list, void *block)
  91 {
  92     MDESC *m_free;
  93     MDESC *m;
  94     MDESC *m_prev;
  95
  96     /*
  97      * Validate pointer.
  98      */
  99     m_free = (MDESC *) block - 1;
 100     if (m_free->prev != m_free || m_free->next != m_free ||
 101         ((int) m_free & 0xffff0000) != ((int) *free_list & 0xffff0000))
 102     {
 103 #ifdef DEBUG_HEAP
 104         printf("Attempt to free bad pointer,"
 105                "m_free = %08x, *free_list = %08x\n",
 106                m_free, free_list);
 107 #endif
 108         return;
 109     }
 110
 111     /*
 112      * Find location in free list.
 113      */
 114     m_prev = NULL;
 115     for (m = *free_list; m != NULL && m < m_free; m = m->next)
 116         m_prev = m;
 117
 118     if (m_prev != NULL && (int) m_prev + m_prev->length > (int) m_free)
 119     {
 120 #ifdef DEBUG_HEAP
 121         printf("Attempt to free bad pointer,"
 122                "m_free = %08x, m_prev = %08x (length %x)\n",
 123                m_free, m_prev, m_prev->length);
 124 #endif
 125         return;
 126     }
 127
 128     if ((m != NULL && (int) m_free + m_free->length > (int) m) ||
 129         (int) m_free + m_free->length > ((int) m_free | 0xffff))
 130     {
 131 #ifdef DEBUG_HEAP
 132         printf("Attempt to free bad pointer,"
 133                "m_free = %08x (length %x), m = %08x\n",
 134                m_free, m_free->length, m);
 135 #endif
 136         return;
 137     }
 138
 139     /*
 140      * Put block back in free list.
 141      * Does it merge with the previos block?
 142      */
 143     if (m_prev != NULL)
 144     {
 145         if ((int) m_prev + m_prev->length == (int) m_free)
 146         {
 147             m_prev->length += sizeof(MDESC) + m_free->length;
 148             m_free = m_prev;
 149         }
 150         else
 151         {
 152             m_prev->next = m_free;
 153             m_free->prev = m_prev;
 154         }
 155     }
 156     else
 157     {
 158         *free_list = m_free;
 159         m_free->prev = NULL;
 160     }
 161
 162     /*
 163      * Does it merge with the next block?
 164      */
 165     if (m != NULL)
 166     {
 167         if ((int) m_free + m_free->length == (int) m)
 168         {
 169             m_free->length += sizeof(MDESC) + m->length;
 170             m_free->next = m->next;
 171         }
 172         else
 173         {
 174             m->prev = m_free;
 175             m_free->next = m;
 176         }
 177     }
 178     else
 179     {
 180         m_free->next = NULL;
 181     }
 182 }
 183
 184 /**********************************************************************
 185  *                                      HEAP_LocalInit
 186  */
 187 void
 188 HEAP_LocalInit(void *start, int length)
 189 {
 190     HEAP_Init(&LOCAL_FreeList, start, length);
 191 }
 192
 193 /**********************************************************************
 194  *                                      HEAP_LocalAlloc
 195  */
 196 void *
 197 HEAP_LocalAlloc(int flags, int bytes)
 198 {
 199     void *m;
 200
 201 #ifdef DEBUG_HEAP
 202     printf("LocalAlloc: flags %x, bytes %d\n", flags, bytes);
 203 #endif
 204
 205     m = HEAP_Alloc(&LOCAL_FreeList, flags, bytes);
 206
 207 #ifdef DEBUG_HEAP
 208         printf("LocalAlloc: returning %x\n", (int) m);
 209 #endif
 210     return m;
 211 }