Subversion Repositories Kolibri OS

Rev

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

  1. #ifndef __MEMORY_HEAP_RBTREE_H_INCLUDED_
  2. #define __MEMORY_HEAP_RBTREE_H_INCLUDED_
  3.  
  4. namespace MemoryHeap
  5. {
  6.         typedef unsigned int TMemItem;
  7.  
  8.         enum {NumTreeSmall = 8 * sizeof(TMemItem)};
  9.  
  10. // Memory heap interface.
  11.  
  12.         struct TFreeSpace
  13.         {
  14.                 TMemItem Small[NumTreeSmall], Min, SmallMask;
  15.         };
  16.  
  17.         struct TMemBlock
  18.         {
  19.                 TMemItem *Begin;
  20.         };
  21.  
  22.         bool BlockValid(const TMemBlock &block);   // Is the given memory block valid?
  23.         void *BlockBegin(const TMemBlock &block);   // Return the beginning address of the block.
  24.         void *BlockEnd(const TMemBlock &block);   // Return the ending address of the block.
  25.         TFreeSpace &BlockFreeSpace(const TMemBlock &block);   // Return the free space of the block.
  26.  
  27.         void InitFreeSpace(TFreeSpace &fs);   // Initialize the free space.
  28.         TMemBlock NullBlock();   // Return null invalid block.
  29.         TMemBlock CreateBlock(void *begin, void *end, TFreeSpace &fs);
  30.                         // Create a memory block with the given begin and end and add free space of it to (fs),
  31.                         //_ give (BlockAddSize) bytes of the block for it's data.
  32.                         //_ (Program can alloc (end - begin - BlockAddSize) bytes after it,
  33.                         //_ that must be not less than (MemMinSize) ).
  34.         TMemBlock CreateBlock(void *begin, void *end);
  35.                         // Create a memory block with the given begin and end and new free space for it,
  36.                         //_ give (BlockAddSizeFS) bytes of the block for it's data.
  37.                         //_ (Program can alloc (end - begin - BlockAddSizeFS) bytes after it,
  38.                         //_ that must be not less than (MemMinSize) ).
  39.         void ResizeBlock(TMemBlock block, void *new_end);   // Resize the memory block to the given new end.
  40.         void RemoveBlock(TMemBlock block);   // Remove the given memory block.
  41.  
  42.         void *BlockEndFor(TMemBlock block, unsigned int size);
  43.                         // Return the new end of the block needed for (ResizeBlock) to alloc the given size of memory.
  44.         unsigned int BlockSize(TMemBlock block);   // Return the size of the given block.
  45.         unsigned int MemSize(void *mem);   // Return the size of the allocced memory.
  46.  
  47.         void *Alloc(TFreeSpace &fs, unsigned int size);
  48.                         // Alloc a memory in the given free space, give (MemAddSize) bytes for it's data.
  49.         void *ReAlloc(TFreeSpace &fs, unsigned int size, void *mem);
  50.                         // ReAlloc the given memory, it must lie in the block with the given free space.
  51.         void Free(TFreeSpace &fs, void *mem);
  52.                         // Free the given memory, it must lie in the block with the given free space.
  53.  
  54. // Macro definitions.
  55.  
  56. #define MEMORY_HEAP_ALIGN_DOWN(s)  (MemoryHeap::TMemItem(s) & ~(MemoryHeap::MemAlign - 1))
  57. #define MEMORY_HEAP_ALIGN_UP(s)    ((MemoryHeap::TMemItem(s) + (MemoryHeap::MemAlign - 1)) & ~(MemoryHeap::MemAlign - 1))
  58. #define MEMORY_HEAP_ITEM(s,k)  ( ((MemoryHeap::TMemItem*)(s))[(k)] )
  59. #define MEMORY_HEAP_NEXT(s)    (MEMORY_HEAP_ITEM((s),-1))
  60. #define MEMORY_HEAP_PREV(s)    (MEMORY_HEAP_ITEM((s),-2))
  61. #define MEMORY_HEAP_FREE(s)    (MEMORY_HEAP_ITEM((s),-1) & 1)
  62.  
  63. // Constants.
  64.  
  65.         enum {MemAlign = sizeof(TMemItem)};
  66.         enum {MemAddSize = MEMORY_HEAP_ALIGN_UP(2 * sizeof(TMemItem))};
  67.         enum {BlockEndSize = MemAddSize};
  68.         enum {BlockAddSize = MEMORY_HEAP_ALIGN_UP(4 * sizeof(TMemItem)) + BlockEndSize};
  69.         enum {BlockAddSizeFS = BlockAddSize + BlockEndSize + MEMORY_HEAP_ALIGN_UP(sizeof(TFreeSpace))};
  70.         enum {MemMinSize = MEMORY_HEAP_ALIGN_UP(2 * sizeof(TMemItem))};
  71.  
  72. // Inline functions.
  73.  
  74.         inline bool BlockValid(const TMemBlock &block) {return block.Begin != 0;}
  75.  
  76.         inline void *BlockBegin(const TMemBlock &block) {return (void*)block.Begin;}
  77.  
  78.         inline void *BlockEnd(const TMemBlock &block) {return block.Begin ? (void*)block.Begin[1] : 0;}
  79.  
  80.         inline TFreeSpace &BlockFreeSpace(const TMemBlock &block) {return *(TFreeSpace*)block.Begin[0];}
  81.  
  82.         inline TMemBlock NullBlock() {TMemBlock block; block.Begin = 0; return block;}
  83.  
  84.         inline void *BlockEndFor(TMemBlock block, unsigned int size)
  85.         {
  86.                 TMemItem last = (TMemItem)block.Begin[1];
  87.                 TMemItem prevlast = MEMORY_HEAP_PREV(last);
  88.                 return (void*)( (MEMORY_HEAP_FREE(prevlast) ? prevlast : last) + MemAddSize +
  89.                                                 ((size <= MemMinSize) ? MemMinSize : MEMORY_HEAP_ALIGN_UP(size)) );
  90.         }
  91.  
  92.         inline unsigned int BlockSize(TMemBlock block)
  93.         {
  94.                 if (!block.Begin) return 0;
  95.                 return (unsigned int)(block.Begin[1] - (TMemItem)block.Begin);
  96.         }
  97.  
  98.         inline unsigned int MemSize(void *mem)
  99.         {
  100.                 if (!mem) return 0;
  101.                 TMemItem c = (TMemItem)mem;
  102.                 return MEMORY_HEAP_NEXT(c) - c - MemAddSize;
  103.         }
  104.  
  105. // Free space item functions.
  106.  
  107.         TMemItem _FirstNotZeroBit(TMemItem i)
  108.         {
  109.                 TMemItem r = 0;
  110.                 while ((i >>= 1) != 0) r++;
  111.                 return r;
  112.         }
  113.  
  114.         void _RBTreeRotate(TMemItem parent, TMemItem item, int side)
  115.         {
  116.                 TMemItem temp = MEMORY_HEAP_ITEM(parent,0);
  117.                 MEMORY_HEAP_ITEM(item,0) = temp;
  118.                 if (temp)
  119.                 {
  120.                         if (MEMORY_HEAP_ITEM(temp,2) == parent)
  121.                         {
  122.                                 MEMORY_HEAP_ITEM(temp,2) = item;
  123.                         }
  124.                         else MEMORY_HEAP_ITEM(temp,3) = item;
  125.                 }
  126.                 temp = MEMORY_HEAP_ITEM(item,side^1);
  127.                 if (temp) MEMORY_HEAP_ITEM(temp,0) = parent;
  128.                 MEMORY_HEAP_ITEM(parent,side) = temp;
  129.                 MEMORY_HEAP_ITEM(parent,0) = item;
  130.                 MEMORY_HEAP_ITEM(item,side^1) = parent;
  131.                 temp = MEMORY_HEAP_ITEM(parent,1);
  132.                 MEMORY_HEAP_ITEM(parent,1) = MEMORY_HEAP_ITEM(item,1);
  133.                 MEMORY_HEAP_ITEM(item,1) = temp;
  134.         }
  135.  
  136.         void InitFreeSpace(TFreeSpace &fs)
  137.         {
  138.                 TMemItem i;
  139.                 for (i = 0; i <= NumTreeSmall; i++) fs.Small[i] = 0;
  140.                 fs.Min = 0; fs.SmallMask = 0;
  141.         }
  142.  
  143.         void _FreeAdd(TFreeSpace &fs, TMemItem item)
  144.         {
  145.                 TMemItem size = MEMORY_HEAP_NEXT(item) - item;
  146.                 if (size < MemAddSize + MemMinSize + MemAlign * NumTreeSmall)
  147.                 {
  148.                         TMemItem s = (size - (MemAddSize + MemMinSize)) / MemAlign;
  149.                         TMemItem &addto = fs.Small[s];
  150.                         MEMORY_HEAP_ITEM(item,1) = (TMemItem)(&addto);
  151.                         MEMORY_HEAP_ITEM(item,0) = (TMemItem)addto;
  152.                         if (addto) MEMORY_HEAP_ITEM(addto,1) = item;
  153.                         addto = item;
  154.                         fs.SmallMask |= TMemItem(1) << s;
  155.                         return;
  156.                 }
  157.                 TMemItem addto = fs.Min, parent, temp;
  158.                 MEMORY_HEAP_ITEM(item,2) = 0;
  159.                 MEMORY_HEAP_ITEM(item,3) = 0;
  160.                 if (!addto)
  161.                 {
  162.                         MEMORY_HEAP_ITEM(item,0) = 0;
  163.                         MEMORY_HEAP_ITEM(item,1) = 1;
  164.                         fs.Min = item;
  165.                         return;
  166.                 }
  167.                 MEMORY_HEAP_ITEM(item,1) = 0;
  168.                 TMemItem side = 2;
  169.                 if (MEMORY_HEAP_NEXT(addto) - addto >= size) fs.Min = item;
  170.                 else
  171.                 {
  172.                         for (;;)
  173.                         {
  174.                                 parent = MEMORY_HEAP_ITEM(addto,0);
  175.                                 if (!parent) break;
  176.                                 if (MEMORY_HEAP_NEXT(parent) - parent < size) addto = parent;
  177.                                 else break;
  178.                         }
  179.                         for (;;)
  180.                         {
  181.                                 if (MEMORY_HEAP_NEXT(addto) - addto < size)
  182.                                 {
  183.                                         temp = MEMORY_HEAP_ITEM(addto,3);
  184.                                         if (!temp) {side = 3; break;}
  185.                                         addto = temp;
  186.                                 }
  187.                                 else
  188.                                 {
  189.                                         temp = MEMORY_HEAP_ITEM(addto,2);
  190.                                         if (!temp) break;
  191.                                         addto = temp;
  192.                                 }
  193.                         }
  194.                 }
  195.                 MEMORY_HEAP_ITEM(item,0) = addto;
  196.                 MEMORY_HEAP_ITEM(addto,side) = item;
  197.                 for (;;)
  198.                 {
  199.                         if (MEMORY_HEAP_ITEM(addto,1) != 0) return;
  200.                         parent = MEMORY_HEAP_ITEM(addto,0);
  201.                         temp = MEMORY_HEAP_ITEM(parent,2);
  202.                         if (temp == addto)
  203.                         {
  204.                                 temp = MEMORY_HEAP_ITEM(parent,3);
  205.                                 side = 2;
  206.                         }
  207.                         else side = 3;
  208.                         if (!temp || MEMORY_HEAP_ITEM(temp,1) != 0) break;
  209.                         MEMORY_HEAP_ITEM(addto,1) = 1;
  210.                         MEMORY_HEAP_ITEM(temp,1) = 1;
  211.                         item = parent;
  212.                         addto = MEMORY_HEAP_ITEM(item,0);
  213.                         if (!addto) return;
  214.                         MEMORY_HEAP_ITEM(item,1) = 0;
  215.                 }
  216.                 if (MEMORY_HEAP_ITEM(addto,side) != item)
  217.                 {
  218.                         temp = MEMORY_HEAP_ITEM(item,side);
  219.                         if (temp) MEMORY_HEAP_ITEM(temp,0) = addto;
  220.                         MEMORY_HEAP_ITEM(addto,side^1) = temp;
  221.                         MEMORY_HEAP_ITEM(addto,0) = item;
  222.                         MEMORY_HEAP_ITEM(item,side) = addto;
  223.                         MEMORY_HEAP_ITEM(item,0) = parent;
  224.                         MEMORY_HEAP_ITEM(parent,side) = item;
  225.                 }
  226.                 else item = addto;
  227.                 _RBTreeRotate(parent, item, side);
  228.         }
  229.  
  230.         void _FreeDel(TFreeSpace &fs, TMemItem item)
  231.         {
  232.                 TMemItem size = MEMORY_HEAP_NEXT(item) - item;
  233.                 if (size < MemAddSize + MemMinSize + MemAlign * NumTreeSmall)
  234.                 {
  235.                         TMemItem prev = MEMORY_HEAP_ITEM(item,1);
  236.                         TMemItem next = MEMORY_HEAP_ITEM(item,0);
  237.                         MEMORY_HEAP_ITEM(prev,0) = next;
  238.                         if (next) MEMORY_HEAP_ITEM(next,1) = prev;
  239.                         else
  240.                         {
  241.                                 TMemItem s = (size - (MemAddSize + MemMinSize)) / MemAlign;
  242.                                 if (!fs.Small[s]) fs.SmallMask &= ~(TMemItem(1) << s);
  243.                         }
  244.                         return;
  245.                 }
  246.                 TMemItem parent, temp, second, add;
  247.                 TMemItem side = 2;
  248.                 temp = MEMORY_HEAP_ITEM(item,3);
  249.                 if (temp)
  250.                 {
  251.                         for (;;)
  252.                         {
  253.                                 second = temp;
  254.                                 temp = MEMORY_HEAP_ITEM(temp,2);
  255.                                 if (!temp) break;
  256.                         }
  257.                         if (fs.Min == item) fs.Min = second;
  258.                         add = MEMORY_HEAP_ITEM(second,3);
  259.                         parent = MEMORY_HEAP_ITEM(second,0);
  260.                         if (parent == item) {parent = second; side = 3;}
  261.                         else
  262.                         {
  263.                                 temp = MEMORY_HEAP_ITEM(item,3);
  264.                                 MEMORY_HEAP_ITEM(second,3) = temp;
  265.                                 MEMORY_HEAP_ITEM(temp,0) = second;
  266.                         }
  267.                         temp = MEMORY_HEAP_ITEM(item,2);
  268.                         MEMORY_HEAP_ITEM(second,2) = temp;
  269.                         if (temp) MEMORY_HEAP_ITEM(temp,0) = second;
  270.                         temp = MEMORY_HEAP_ITEM(item,0);
  271.                         MEMORY_HEAP_ITEM(second,0) = temp;
  272.                         if (temp)
  273.                         {
  274.                                 if (MEMORY_HEAP_ITEM(temp,2) == item)
  275.                                 {
  276.                                         MEMORY_HEAP_ITEM(temp,2) = second;
  277.                                 }
  278.                                 else MEMORY_HEAP_ITEM(temp,3) = second;
  279.                         }
  280.                         MEMORY_HEAP_ITEM(parent,side) = add;
  281.                         if (add) MEMORY_HEAP_ITEM(add,0) = parent;
  282.                         bool color = MEMORY_HEAP_ITEM(second,1);
  283.                         MEMORY_HEAP_ITEM(second,1) = MEMORY_HEAP_ITEM(item,1);
  284.                         if (!color) return;
  285.                 }
  286.                 else
  287.                 {
  288.                         if (fs.Min == item) fs.Min = MEMORY_HEAP_ITEM(item,0);
  289.                         add = MEMORY_HEAP_ITEM(item,2);
  290.                         parent = MEMORY_HEAP_ITEM(item,0);
  291.                         if (add) MEMORY_HEAP_ITEM(add,0) = parent;
  292.                         if (parent)
  293.                         {
  294.                                 if (MEMORY_HEAP_ITEM(parent,2) == item)
  295.                                 {
  296.                                         MEMORY_HEAP_ITEM(parent,2) = add;
  297.                                 }
  298.                                 else
  299.                                 {
  300.                                         MEMORY_HEAP_ITEM(parent,3) = add;
  301.                                         side = 3;
  302.                                 }
  303.                         }
  304.                         else
  305.                         {
  306.                                 if (add) MEMORY_HEAP_ITEM(add,1) = 1;
  307.                                 return;
  308.                         }
  309.                         if (!MEMORY_HEAP_ITEM(item,1)) return;
  310.                 }
  311.                 if (add && !MEMORY_HEAP_ITEM(add,1))
  312.                 {
  313.                         MEMORY_HEAP_ITEM(add,1) = 1;
  314.                         return;
  315.                 }
  316.                 for (;;)
  317.                 {
  318.                         second = MEMORY_HEAP_ITEM(parent,side^1);
  319.                         if (!MEMORY_HEAP_ITEM(second,1))
  320.                         {
  321.                                 _RBTreeRotate(parent, second, side^1);
  322.                                 second = MEMORY_HEAP_ITEM(parent,side^1);
  323.                         }
  324.                         temp = MEMORY_HEAP_ITEM(second,side^1);
  325.                         if (temp && !MEMORY_HEAP_ITEM(temp,1))
  326.                         {
  327.                                 MEMORY_HEAP_ITEM(temp,1) = 1;
  328.                                 break;
  329.                         }
  330.                         temp = MEMORY_HEAP_ITEM(second,side);
  331.                         if (temp && !MEMORY_HEAP_ITEM(temp,1))
  332.                         {
  333.                                 _RBTreeRotate(second, temp, side);
  334.                                 MEMORY_HEAP_ITEM(second,1) = 1;
  335.                                 second = temp;
  336.                                 break;
  337.                         }
  338.                         MEMORY_HEAP_ITEM(second,1) = 0;
  339.                         if (!MEMORY_HEAP_ITEM(parent,1))
  340.                         {
  341.                                 MEMORY_HEAP_ITEM(parent,1) = 1;
  342.                                 return;
  343.                         }
  344.                         second = parent;
  345.                         parent = MEMORY_HEAP_ITEM(second,0);
  346.                         if (!parent) return;
  347.                         if (MEMORY_HEAP_ITEM(parent,2) == second) side = 2;
  348.                         else side = 3;
  349.                 }
  350.                 _RBTreeRotate(parent, second, side^1);
  351.         }
  352.  
  353.         TMemItem _FreeFindAfter(TMemItem item, TMemItem size)
  354.         {
  355.                 if (!item) return 0;
  356.                 TMemItem paritem, s;
  357.                 if (MEMORY_HEAP_NEXT(item) - item >= size) return item;
  358.                 for (;;)
  359.                 {
  360.                         paritem = MEMORY_HEAP_ITEM(item,0);
  361.                         if (!paritem) break;
  362.                         s = MEMORY_HEAP_NEXT(paritem) - paritem;
  363.                         if (s == size) return paritem;
  364.                         if (s < size) item = paritem;
  365.                         else break;
  366.                 }
  367.                 MEMORY_HEAP_ITEM(item,3);
  368.                 for (;;)
  369.                 {
  370.                         if (!item) return paritem;
  371.                         s = MEMORY_HEAP_NEXT(item) - item;
  372.                         if (s == size) return item;
  373.                         if (s < size) item = MEMORY_HEAP_ITEM(item,3);
  374.                         else
  375.                         {
  376.                                 paritem = item;
  377.                                 item = MEMORY_HEAP_ITEM(item,2);
  378.                         }
  379.                 }
  380.         }
  381.  
  382.         TMemItem _FreeFind(TFreeSpace &fs, TMemItem size)
  383.         {
  384.                 TMemItem item, nextitem, s;
  385.                 if (size < MemAddSize + MemMinSize + MemAlign * NumTreeSmall)
  386.                 {
  387.                         TMemItem m, t;
  388.                         s = (size - (MemAddSize + MemMinSize)) / MemAlign;
  389.                         item = fs.Small[s];
  390.                         if (item) return item;
  391.                         if (size < MemAlign * NumTreeSmall)
  392.                         {
  393.                                 t = size / MemAlign;
  394.                                 m = fs.SmallMask >> t;
  395.                                 if (m) return fs.Small[t + _FirstNotZeroBit(m)];
  396.                                 else if (fs.Min) return fs.Min;
  397.                         }
  398.                         else
  399.                         {
  400.                                 item = _FreeFindAfter(fs.Min, size + 1 + MemAddSize + MemMinSize);
  401.                                 if (item) return item;
  402.                         }
  403.                         m = fs.SmallMask >> s;
  404.                         if (m) return fs.Small[s + _FirstNotZeroBit(m)];
  405.                         else return fs.Min;
  406.                 }
  407.                 item = _FreeFindAfter(fs.Min, ++size);
  408.                 if (!item) return 0;
  409.                 s = MEMORY_HEAP_NEXT(item) - item;
  410.                 if (s == size) return item;
  411.                 size += MemAddSize + MemMinSize;
  412.                 if (s >= size) return item;
  413.                 nextitem = _FreeFindAfter(item, size);
  414.                 return nextitem ? nextitem : item;
  415.         }
  416.  
  417. // Block functions.
  418.  
  419.         inline void _CreateBlockEnd(TMemBlock &block, TFreeSpace &fs, TMemItem c, TMemItem e)
  420.         {
  421.                 block.Begin[0] = (TMemItem)(&fs);
  422.                 if (e - c < TMemItem(MemAddSize + MemMinSize))
  423.                 {
  424.                         MEMORY_HEAP_NEXT(c) = 0;
  425.                         block.Begin[1] = c;
  426.                 }
  427.                 else
  428.                 {
  429.                         MEMORY_HEAP_NEXT(c) = e + 1;
  430.                         _FreeAdd(fs, c);
  431.                         MEMORY_HEAP_PREV(e) = c;
  432.                         MEMORY_HEAP_NEXT(e) = 0;
  433.                         block.Begin[1] = e;
  434.                 }
  435.         }
  436.  
  437.         TMemBlock CreateBlock(void *begin, void *end, TFreeSpace &fs)
  438.         {
  439.                 TMemBlock block = {0};
  440.                 TMemItem b = MEMORY_HEAP_ALIGN_UP(begin);
  441.                 TMemItem e = MEMORY_HEAP_ALIGN_DOWN(end);
  442.                 if (e <= b || e - b < TMemItem(BlockAddSize - MemAddSize)) return block;
  443.                 block.Begin = (TMemItem*)b;
  444.                 b += MEMORY_HEAP_ALIGN_UP(4 * sizeof(TMemItem));
  445.                 MEMORY_HEAP_PREV(b) = 0;
  446.                 _CreateBlockEnd(block, fs, b, e);
  447.                 return block;
  448.         }
  449.  
  450.         TMemBlock CreateBlock(void *begin, void *end)
  451.         {
  452.                 TMemBlock block = {0};
  453.                 TMemItem b = MEMORY_HEAP_ALIGN_UP(begin);
  454.                 TMemItem e = MEMORY_HEAP_ALIGN_DOWN(end);
  455.                 if (e <= b || e - b < TMemItem(BlockAddSizeFS - MemAddSize)) return block;
  456.                 block.Begin = (TMemItem*)b;
  457.                 b += MEMORY_HEAP_ALIGN_UP(4 * sizeof(TMemItem));
  458.                 TMemItem c = b + MemAddSize + MEMORY_HEAP_ALIGN_UP(sizeof(TFreeSpace));
  459.                 MEMORY_HEAP_PREV(b) = 0;
  460.                 MEMORY_HEAP_NEXT(b) = c;
  461.                 MEMORY_HEAP_PREV(c) = b;
  462.                 InitFreeSpace(*(TFreeSpace*)b);
  463.                 _CreateBlockEnd(block, *(TFreeSpace*)b, c, e);
  464.                 return block;
  465.         }
  466.  
  467.         void ResizeBlock(TMemBlock block, void *new_end)
  468.         {
  469.                 if (!BlockValid(block)) return;
  470.                 TMemItem e = MEMORY_HEAP_ALIGN_DOWN(new_end);
  471.                 TMemItem c = block.Begin[1];
  472.                 TFreeSpace &fs = *(TFreeSpace*)block.Begin[0];
  473.                 do
  474.                 {
  475.                         if (c == e) return;
  476.                         else if (c > e)
  477.                         {
  478.                                 while ((c = MEMORY_HEAP_PREV(c)) > e)
  479.                                 {
  480.                                         if (MEMORY_HEAP_FREE(c)) _FreeDel(fs, c);
  481.                                 }
  482.                                 if (!c) {block.Begin = 0; return;}
  483.                                 if (MEMORY_HEAP_FREE(c))
  484.                                 {
  485.                                         _FreeDel(fs, c);
  486.                                         if (e - c < TMemItem(MemAddSize + MemMinSize)) e = c;
  487.                                         else
  488.                                         {
  489.                                                 MEMORY_HEAP_NEXT(c) = e + 1;
  490.                                                 _FreeAdd(*(TFreeSpace*)block.Begin[0], c);
  491.                                                 break;
  492.                                         }
  493.                                 }
  494.                                 else if (e - c >= TMemItem(MemAddSize + MemMinSize))
  495.                                 {
  496.                                         MEMORY_HEAP_NEXT(c) = e; break;
  497.                                 }
  498.                                 MEMORY_HEAP_NEXT(c) = 0;
  499.                                 block.Begin[1] = c;
  500.                                 if (c == e) return;
  501.                         }
  502.                         TMemItem pc = MEMORY_HEAP_PREV(c);
  503.                         if (pc && MEMORY_HEAP_FREE(pc)) _FreeDel(fs, c = pc);
  504.                         else if (e - c < TMemItem(MemAddSize + MemMinSize)) return;
  505.                         MEMORY_HEAP_NEXT(c) = e + 1;
  506.                         _FreeAdd(fs, c);
  507.                 } while(false);
  508.                 MEMORY_HEAP_PREV(e) = c;
  509.                 MEMORY_HEAP_NEXT(e) = 0;
  510.                 block.Begin[1] = e;
  511.         }
  512.  
  513.         void RemoveBlock(TMemBlock block)
  514.         {
  515.                 if (!BlockValid(block)) return;
  516.                 TMemItem e = block.Begin[1];
  517.                 TFreeSpace &fs = *(TFreeSpace*)block.Begin[0];
  518.                 while ((e = MEMORY_HEAP_PREV(e)) != 0)
  519.                 {
  520.                         if (MEMORY_HEAP_FREE(e)) _FreeDel(fs, e);
  521.                 }
  522.                 block.Begin = 0;
  523.         }
  524.  
  525. // Free space functions.
  526.  
  527.         void _CopyMemItemArray(TMemItem dest, TMemItem src, TMemItem end)
  528.         {
  529.                 TMemItem k = (end - src) / sizeof(TMemItem);
  530.                 TMemItem *d = (TMemItem*)dest;
  531.                 TMemItem *s = (TMemItem*)src;
  532.                 while (k--) *(d++) = *(s++);
  533.         }
  534.  
  535.         void *Alloc(TFreeSpace &fs, unsigned int size)
  536.         {
  537.                 if (!size) return 0;
  538.                 TMemItem s = MEMORY_HEAP_ALIGN_UP(size) + MemAddSize;
  539.                 if (s < MemAddSize + MemMinSize) s = MemAddSize + MemMinSize;
  540.                 TMemItem c = _FreeFind(fs, s);
  541.                 if (!c) return 0;
  542.                 _FreeDel(fs, c);
  543.                 TMemItem nc = --MEMORY_HEAP_NEXT(c);
  544.                 TMemItem mc = c + s;
  545.                 if (nc - (MemAddSize + MemMinSize) >= mc)
  546.                 {
  547.                         MEMORY_HEAP_NEXT(c) = mc;
  548.                         MEMORY_HEAP_PREV(mc) = c;
  549.                         MEMORY_HEAP_NEXT(mc) = nc + 1;
  550.                         MEMORY_HEAP_PREV(nc) = mc;
  551.                         _FreeAdd(fs, mc);
  552.                 }
  553.                 return (void*)c;
  554.         }
  555.  
  556.         void *ReAlloc(TFreeSpace &fs, void *mem, unsigned int size)
  557.         {
  558.                 if (!mem) return Alloc(fs, size);
  559.                 if (!size) {Free(fs, mem); return 0;}
  560.                 TMemItem s = MEMORY_HEAP_ALIGN_UP(size) + MemAddSize;
  561.                 TMemItem c = (TMemItem)mem;
  562.                 TMemItem mc = MEMORY_HEAP_NEXT(c);
  563.                 TMemItem nc = MEMORY_HEAP_NEXT(mc);
  564.                 if (--nc & 1) nc = mc;
  565.                 if (s < MemAddSize + MemMinSize) s = MemAddSize + MemMinSize;
  566.                 if (nc - c < s)
  567.                 {
  568.                         mem = Alloc(fs, size);
  569.                         if (mem)
  570.                         {
  571.                                 _CopyMemItemArray((TMemItem)mem, c, mc - MemAddSize);
  572.                                 Free(fs, (void*)c);
  573.                                 return mem;
  574.                         }
  575.                         else
  576.                         {
  577.                                 TMemItem pc = MEMORY_HEAP_PREV(c);
  578.                                 if (pc && MEMORY_HEAP_FREE(pc) && nc - pc >= s)
  579.                                 {
  580.                                         _FreeDel(fs, pc);
  581.                                         _CopyMemItemArray(pc, c, mc - MemAddSize);
  582.                                         c = pc;
  583.                                 }
  584.                                 else return 0;
  585.                         }
  586.                 }
  587.                 if (mc < nc) _FreeDel(fs, mc);
  588.                 mc = c + s;
  589.                 if (nc - (MemAddSize + MemMinSize) >= mc)
  590.                 {
  591.                         MEMORY_HEAP_NEXT(c) = mc;
  592.                         MEMORY_HEAP_PREV(mc) = c;
  593.                         MEMORY_HEAP_NEXT(mc) = nc + 1;
  594.                         MEMORY_HEAP_PREV(nc) = mc;
  595.                         _FreeAdd(fs, mc);
  596.                 }
  597.                 else
  598.                 {
  599.                         MEMORY_HEAP_NEXT(c) = nc;
  600.                         MEMORY_HEAP_PREV(nc) = c;
  601.                 }
  602.                 return (void*)c;
  603.         }
  604.  
  605.         int free_a = 0;
  606.  
  607.         void Free(TFreeSpace &fs, void *mem)
  608.         {
  609.                 TMemItem c = (TMemItem)mem;
  610.                 if (!c) return;
  611.                 TMemItem pc = MEMORY_HEAP_PREV(c);
  612.                 TMemItem mc = MEMORY_HEAP_NEXT(c);
  613.                 TMemItem nc = MEMORY_HEAP_NEXT(mc);
  614.                 if (--nc & 1) nc = mc;
  615.                 else _FreeDel(fs, mc);
  616.                 if (free_a == 1) return;
  617.                 if (pc && MEMORY_HEAP_FREE(pc)) _FreeDel(fs, c = pc);
  618.                 MEMORY_HEAP_NEXT(c) = nc + 1;
  619.                 MEMORY_HEAP_PREV(nc) = c;
  620.                 if (free_a == 2) return;
  621.                 _FreeAdd(fs, c);
  622.         }
  623. }
  624.  
  625. #endif  // ndef __MEMORY_HEAP_RBTREE_H_INCLUDED_
  626.  
  627.