l4/pkg/l4re-core/cxx/lib/util/src/alloc_list.cc

   1 /*
   2  * (c) 2004-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
   3  *     economic rights: Technische Universität Dresden (Germany)
   4  *
   5  * This file is part of TUD:OS and distributed under the terms of the
   6  * GNU General Public License 2.
   7  * Please see the COPYING-GPL-2 file for details.
   8  *
   9  * As a special exception, you may use this file as part of a free software
  10  * library without restriction.  Specifically, if other files instantiate
  11  * templates or use macros or inline functions from this file, or you compile
  12  * this file and link it with other files to produce an executable, this
  13  * file does not by itself cause the resulting executable to be covered by
  14  * the GNU General Public License.  This exception does not however
  15  * invalidate any other reasons why the executable file might be covered by
  16  * the GNU General Public License.
  17  */
  18
  19 #include <l4/cxx/alloc.h>
  20
  21 namespace L4 {
  22
  23   void Alloc_list::free( void *blk, unsigned long size )
  24   {
  25     Elem *n = reinterpret_cast<Elem*>(blk);
  26     Elem **c = &_free;
  27     while (*c)
  28       {
  29         if (reinterpret_cast<char*>(*c) + (*c)->size == blk)
  30           {
  31             (*c)->size += size;
  32             blk = 0;
  33             break;
  34           }
  35
  36         if (reinterpret_cast<char*>(*c) > blk)
  37           break;
  38
  39         c = &((*c)->next);
  40       }
  41
  42     if (blk)
  43       {
  44         n->next = *c;
  45         n->size = size;
  46         *c = n;
  47       }
  48
  49     while (*c && reinterpret_cast<char*>(*c)+(*c)->size == (char*)((*c)->next))
  50       {
  51         (*c)->size += (*c)->next->size;
  52         (*c)->next = (*c)->next->next;
  53       }
  54   }
  55
  56   void *Alloc_list::alloc( unsigned long size )
  57   {
  58     if (!_free)
  59       return 0;
  60
  61     // best fit;
  62     Elem **min = 0;
  63     Elem **c = &_free;
  64
  65     while(*c)
  66       {
  67         if ((*c)->size >= size && (!min || (*min)->size > (*c)->size))
  68           min = c;
  69
  70         c = &((*c)->next);
  71       }
  72
  73     if (!min)
  74       return 0;
  75
  76
  77     void *r;
  78     if ( (*min)->size > size )
  79       {
  80         r = reinterpret_cast<char*>(*min) + ((*min)->size - size);
  81         (*min)->size -= size;
  82       }
  83     else
  84       {
  85         r = *min;
  86         *min = (*min)->next;
  87       }
  88
  89     return r;
  90   }
  91
  92 }
  93