X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fmesa%2Fmain%2Fmm.c;h=473e90fc2d5be879f13eb2ad7346ccb5494b60d2;hb=c1df492d03862f75698ba5d50d4f46cd528ffc0d;hp=14563b2591c1359c58687ee6321359c59b6f8eb5;hpb=005469005df6ba5f80e382d5371c6d069c27738b;p=mesa.git

diff --git a/src/mesa/main/mm.c b/src/mesa/main/mm.c
index 14563b2591c..473e90fc2d5 100644
--- a/src/mesa/main/mm.c
+++ b/src/mesa/main/mm.c
@@ -21,191 +21,263 @@
  * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  *
  */
-/* $XFree86: xc/lib/GL/mesa/src/drv/common/mm.c,v 1.4 2002/10/30 12:51:27 alanh Exp $ */
 
-#include <stdlib.h>
+#include <assert.h>
 #include <stdio.h>
+#include <stdlib.h>
 
+#include "compiler.h"
 #include "mm.h"
 
 
-void mmDumpMemInfo( memHeap_t *heap )
+void
+mmDumpMemInfo(const struct mem_block *heap)
 {
-   TMemBlock *p;
-
    fprintf(stderr, "Memory heap %p:\n", (void *)heap);
    if (heap == 0) {
       fprintf(stderr, "  heap == 0\n");
    } else {
-      p = (TMemBlock *)heap;
-      while (p) {
+      const struct mem_block *p;
+
+      for(p = heap->next; p != heap; p = p->next) {
 	 fprintf(stderr, "  Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
-		 p->free ? '.':'U',
+		 p->free ? 'F':'.',
 		 p->reserved ? 'R':'.');
-	 p = p->next;
       }
+
+      fprintf(stderr, "\nFree list:\n");
+
+      for(p = heap->next_free; p != heap; p = p->next_free) {
+	 fprintf(stderr, " FREE Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
+		 p->free ? 'F':'.',
+		 p->reserved ? 'R':'.');
+      }
+
    }
    fprintf(stderr, "End of memory blocks\n");
 }
 
-memHeap_t *mmInit(int ofs,
-		  int size)
+struct mem_block *
+mmInit(unsigned ofs, unsigned size)
 {
-   PMemBlock blocks;
+   struct mem_block *heap, *block;
   
-   if (size <= 0) {
+   if (!size) 
       return NULL;
-   }
-   blocks = (TMemBlock *) calloc(1,sizeof(TMemBlock));
-   if (blocks) {
-      blocks->ofs = ofs;
-      blocks->size = size;
-      blocks->free = 1;
-      return (memHeap_t *)blocks;
-   } else
+
+   heap = calloc(1, sizeof(struct mem_block));
+   if (!heap) 
+      return NULL;
+   
+   block = calloc(1, sizeof(struct mem_block));
+   if (!block) {
+      free(heap);
       return NULL;
+   }
+
+   heap->next = block;
+   heap->prev = block;
+   heap->next_free = block;
+   heap->prev_free = block;
+
+   block->heap = heap;
+   block->next = heap;
+   block->prev = heap;
+   block->next_free = heap;
+   block->prev_free = heap;
+
+   block->ofs = ofs;
+   block->size = size;
+   block->free = 1;
+
+   return heap;
 }
 
 
-static TMemBlock* SliceBlock(TMemBlock *p, 
-			     int startofs, int size, 
-			     int reserved, int alignment)
+static struct mem_block *
+SliceBlock(struct mem_block *p, 
+           unsigned startofs, unsigned size, 
+           unsigned reserved, unsigned alignment)
 {
-   TMemBlock *newblock;
+   struct mem_block *newblock;
 
-   /* break left */
+   /* break left  [p, newblock, p->next], then p = newblock */
    if (startofs > p->ofs) {
-      newblock = (TMemBlock*) calloc(1,sizeof(TMemBlock));
+      newblock = calloc(1, sizeof(struct mem_block));
       if (!newblock)
 	 return NULL;
       newblock->ofs = startofs;
       newblock->size = p->size - (startofs - p->ofs);
       newblock->free = 1;
+      newblock->heap = p->heap;
+
       newblock->next = p->next;
-      p->size -= newblock->size;
+      newblock->prev = p;
+      p->next->prev = newblock;
       p->next = newblock;
+
+      newblock->next_free = p->next_free;
+      newblock->prev_free = p;
+      p->next_free->prev_free = newblock;
+      p->next_free = newblock;
+
+      p->size -= newblock->size;
       p = newblock;
    }
 
-   /* break right */
+   /* break right, also [p, newblock, p->next] */
    if (size < p->size) {
-      newblock = (TMemBlock*) calloc(1,sizeof(TMemBlock));
+      newblock = calloc(1, sizeof(struct mem_block));
       if (!newblock)
 	 return NULL;
       newblock->ofs = startofs + size;
       newblock->size = p->size - size;
       newblock->free = 1;
+      newblock->heap = p->heap;
+
       newblock->next = p->next;
-      p->size = size;
+      newblock->prev = p;
+      p->next->prev = newblock;
       p->next = newblock;
+
+      newblock->next_free = p->next_free;
+      newblock->prev_free = p;
+      p->next_free->prev_free = newblock;
+      p->next_free = newblock;
+	 
+      p->size = size;
    }
 
    /* p = middle block */
-   p->align = alignment;
    p->free = 0;
+
+   /* Remove p from the free list: 
+    */
+   p->next_free->prev_free = p->prev_free;
+   p->prev_free->next_free = p->next_free;
+
+   p->next_free = 0;
+   p->prev_free = 0;
+
    p->reserved = reserved;
    return p;
 }
 
-PMemBlock mmAllocMem( memHeap_t *heap, int size, int align2, int startSearch)
+
+struct mem_block *
+mmAllocMem(struct mem_block *heap, unsigned size, unsigned align2, unsigned startSearch)
 {
-   int mask,startofs,endofs;
-   TMemBlock *p;
+   struct mem_block *p;
+   const unsigned mask = (1 << align2)-1;
+   unsigned startofs = 0;
+   unsigned endofs;
 
-   if (!heap || align2 < 0 || size <= 0)
+   if (!heap || !size)
       return NULL;
-   mask = (1 << align2)-1;
-   startofs = 0;
-   p = (TMemBlock *)heap;
-   while (p) {
-      if ((p)->free) {
-	 startofs = (p->ofs + mask) & ~mask;
-	 if ( startofs < startSearch ) {
-	    startofs = startSearch;
-	 }
-	 endofs = startofs+size;
-	 if (endofs <= (p->ofs+p->size))
-	    break;
+
+   for (p = heap->next_free; p != heap; p = p->next_free) {
+      assert(p->free);
+
+      startofs = (p->ofs + mask) & ~mask;
+      if ( startofs < startSearch ) {
+	 startofs = startSearch;
       }
-      p = p->next;
+      endofs = startofs+size;
+      if (endofs <= (p->ofs+p->size))
+	 break;
    }
-   if (!p)
+
+   if (p == heap) 
       return NULL;
+
+   assert(p->free);
    p = SliceBlock(p,startofs,size,0,mask+1);
-   p->heap = heap;
+
    return p;
 }
 
-PMemBlock mmFindBlock( memHeap_t *heap, int start)
+
+struct mem_block *
+mmFindBlock(struct mem_block *heap, unsigned start)
 {
-   TMemBlock *p = (TMemBlock *)heap;
+   struct mem_block *p;
 
-   while (p) {
-      if (p->ofs == start && p->free) 
+   for (p = heap->next; p != heap; p = p->next) {
+      if (p->ofs == start) 
 	 return p;
-
-      p = p->next;
    }
 
    return NULL;
 }
 
 
-static __inline__ int Join2Blocks(TMemBlock *p)
+static inline int
+Join2Blocks(struct mem_block *p)
 {
-   if (p->free && p->next && p->next->free) {
-      TMemBlock *q = p->next;
+   /* XXX there should be some assertions here */
+
+   /* NOTE: heap->free == 0 */
+
+   if (p->free && p->next->free) {
+      struct mem_block *q = p->next;
+
+      assert(p->ofs + p->size == q->ofs);
       p->size += q->size;
+
       p->next = q->next;
+      q->next->prev = p;
+
+      q->next_free->prev_free = q->prev_free; 
+      q->prev_free->next_free = q->next_free;
+     
       free(q);
       return 1;
    }
    return 0;
 }
 
-int mmFreeMem(PMemBlock b)
+int
+mmFreeMem(struct mem_block *b)
 {
-   TMemBlock *p,*prev;
-
    if (!b)
       return 0;
-   if (!b->heap) {
-      fprintf(stderr, "no heap\n");
+
+   if (b->free) {
+      fprintf(stderr, "block already free\n");
       return -1;
    }
-   p = b->heap;
-   prev = NULL;
-   while (p && p != b) {
-      prev = p;
-      p = p->next;
-   }
-   if (!p || p->free || p->reserved) {
-      if (!p)
-	 fprintf(stderr, "block not found in heap\n");
-      else if (p->free)
-	 fprintf(stderr, "block already free\n");
-      else
-	 fprintf(stderr, "block is reserved\n");
+   if (b->reserved) {
+      fprintf(stderr, "block is reserved\n");
       return -1;
    }
-   p->free = 1;
-   Join2Blocks(p);
-   if (prev)
-      Join2Blocks(prev);
+
+   b->free = 1;
+   b->next_free = b->heap->next_free;
+   b->prev_free = b->heap;
+   b->next_free->prev_free = b;
+   b->prev_free->next_free = b;
+
+   Join2Blocks(b);
+   if (b->prev != b->heap)
+      Join2Blocks(b->prev);
+
    return 0;
 }
 
 
-void mmDestroy(memHeap_t *heap)
+void
+mmDestroy(struct mem_block *heap)
 {
-   TMemBlock *p,*q;
+   struct mem_block *p;
 
    if (!heap)
       return;
-   p = (TMemBlock *)heap;
-   while (p) {
-      q = p->next;
+
+   for (p = heap->next; p != heap; ) {
+      struct mem_block *next = p->next;
       free(p);
-      p = q;
+      p = next;
    }
+
+   free(heap);
 }