Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*******************************************************************************
  2.  *   Copyright (C) 2009 Vasiliy Kosenko                                        *
  3.  *                                                                             *
  4.  *   This program is free software; you can redistribute it and/or modify      *
  5.  *   it under the terms of the GNU General Public License as published by      *
  6.  *   the Free Software Foundation; either version 3 of the License, or         *
  7.  *   (at your option) any later version.                                       *
  8.  *                                                                             *
  9.  *   This program is distributed in the hope that it will be useful,           *
  10.  *   but WITHOUT ANY WARRANTY; without even the implied warranty of            *
  11.  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
  12.  *   GNU General Public License for more details.                              *
  13.  *                                                                             *
  14.  *   You should have received a copy of the GNU General Public License         *
  15.  *   along with this program; if not, write to the Free Software               *
  16.  *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
  17.  *******************************************************************************/
  18.  
  19. /*******************************************************************************
  20.  *   This is my heap realization adapted for KolibriOS                         *
  21.  *******************************************************************************/
  22.  
  23. #include "kolibri.h"
  24. #include "heap.h"
  25. #include "defs.h"
  26.  
  27. void *halMemAlloc(Heap *wheap, unsigned long nbytes){
  28.         MemBlock *heap = wheap->free, *best = 0;
  29.         int good_best = 0;                                              // Such memory block, that no memory will left
  30.         unsigned long nblocks = (nbytes-1)/sizeof(MemBlock)+1;
  31.        
  32.         if (heap) {
  33.                 while (heap) {
  34.                         if (heap->nblocks > nblocks && (!best || heap->nblocks < best->nblocks) && (!good_best || heap->nblocks > nblocks+1)) {
  35.                                 best = heap;
  36.                                 if (heap->nblocks > nblocks+1) {
  37.                                         good_best = 1;
  38.                                 }
  39.                         } else if (heap->nblocks == nblocks) {
  40.                                 best = heap;
  41.                                 good_best = 0;
  42.                                 break;
  43.                         }
  44.                         heap = heap->next;
  45.                 }
  46.         }
  47.        
  48.         if (best && good_best) {
  49.                 heap = best+best->nblocks-nblocks;
  50.                 heap->nblocks = nblocks;
  51.                 wheap->allocated = halMemBlockAdd(wheap->allocated, heap, false);
  52.                 best->nblocks -= nblocks+1;
  53.                 best = heap;
  54.         } else if (best) {
  55.                 wheap->free = halMemBlockRemove(best);
  56.                 wheap->allocated = halMemBlockAdd(wheap->allocated, best, false);
  57.         } else {
  58.                 // We need some memory for heap
  59.                 int npages = ((nblocks+1)-1)/(PAGE_SIZE/sizeof(MemBlock))+1;
  60.                 void *pages;
  61.                
  62. //              debug(DEBUG_MESSAGE, 4, "no enough memory in heap, needed %d page%s", npages, npages == 1 ? "" : "s");
  63.                
  64.                 // Try to get npages at once
  65.                 pages = wheap->alloc(wheap, npages*PAGE_SIZE);
  66.                 if (pages) {
  67. //                      debug(DEBUG_MESSAGE, 5, "physic pages allocated");
  68.                         best = (MemBlock *) pages;
  69.                         if (npages*PAGE_SIZE <= (nblocks+2)*sizeof(MemBlock)) {
  70.                                 best->nblocks = npages*PAGE_SIZE/sizeof(MemBlock)-1;
  71.                         } else {
  72.                                 best->nblocks = nblocks;
  73.                                 heap = best+best->nblocks+1;
  74.                                 heap->nblocks = npages*PAGE_SIZE/sizeof(MemBlock)-(nblocks+1)-1;
  75.                                 wheap->free = halMemBlockAdd(wheap->free, heap, true);
  76.                         }
  77.                         wheap->allocated = halMemBlockAdd(wheap->allocated, best, false);
  78.                 } else {
  79. //                      debug(DEBUG_WARNING, 3, "no available physic pages");
  80.                         return NULL;
  81.                 }
  82.         }
  83.        
  84. //      debug(DEBUG_MESSAGE, 5, "memory allocated");
  85.        
  86.         return (void *) (best + 1);
  87. }
  88.  
  89. void halMemFree(Heap *wheap, void *addr){
  90.         MemBlock *heap = wheap->allocated;
  91.         MemBlock *block = (MemBlock *)addr - 1;
  92.        
  93.         while (heap->next && block < heap) {
  94.                 heap = heap->next;
  95.         }
  96.        
  97.         if (block != heap) {
  98.                 return;
  99.         }
  100.        
  101.         wheap->allocated = halMemBlockRemove(block);
  102.         wheap->free = halMemBlockAdd(wheap->free, block, true);
  103. }
  104.  
  105. void halMemHeapInit(Heap *wheap, void *(*alloc)(Heap *heap, int nbytes), void *st_addr, int size){
  106.         MemBlock *st_unit = (MemBlock *)st_addr;
  107.        
  108.         if (st_unit) {
  109.                 st_unit->nblocks = size/sizeof(MemBlock)-1;
  110.                 wheap->free = halMemBlockAdd(NULL, st_unit, true);
  111.         } else {
  112.                 wheap->free = NULL;
  113.         }
  114.         wheap->allocated = NULL;
  115.         wheap->alloc = alloc;
  116. }
  117.  
  118. /////////////////////////////////////////////////////////////////////////////////
  119. // inside functions                                                            //
  120. /////////////////////////////////////////////////////////////////////////////////
  121. MemBlock *halMemBlockAdd(MemBlock *heap, MemBlock *unit, bool optimize){
  122.         MemBlock *heap_st = heap;
  123. //      int optimize = (heap_st != wheap->allocated);
  124.        
  125.         if (!heap || (heap > unit)) {
  126.                 heap_st = unit;
  127.                 if (heap) {
  128.                         heap->previos = unit;
  129.                 }
  130.                 unit->next = heap;
  131.                 unit->previos = NULL;
  132.         } else {
  133.                 if (heap->next) {
  134.                         while (heap->next && (heap < unit)) {
  135.                                 heap = heap->next;
  136.                         }
  137.                         heap = heap->previos;
  138.                 }
  139.                 unit->next = heap->next;
  140.                 unit->previos = heap;
  141.                 if (heap->next) {
  142.                         heap->next->previos = unit;
  143.                 }
  144.                 heap->next = unit;
  145.         }
  146.        
  147.         if (optimize) {
  148.                 if (unit->previos && unit->previos+unit->previos->nblocks == unit) {
  149.                         halMemBlockRemove(unit);
  150.                         unit->previos->nblocks += unit->nblocks+1;
  151.                 }
  152.                
  153.                 if (unit->next && unit+unit->nblocks == unit->next) {
  154.                         unit->nblocks += unit->next->nblocks+1;
  155.                         halMemBlockRemove(unit->next);
  156.                 }
  157.         }
  158.        
  159.         return heap_st;
  160. }
  161.  
  162. MemBlock *halMemBlockRemove(MemBlock *unit) {
  163.         if (unit->next) {
  164.                 unit->next->previos = unit->previos;
  165.         }
  166.        
  167.         if (unit->previos) {
  168.                 unit->previos->next = unit->next;
  169.                 while (unit->previos) {
  170.                         unit = unit->previos;
  171.                 }
  172.                 return unit;
  173.         } else {
  174.                 return unit->next;
  175.         }
  176. }
  177.