ipc/shm_fragment.c

   1 /***************************************************************************
   2  * Copyright 1995, Technion, Israel Institute of Technology
   3  * Electrical Eng, Software Lab.
   4  * Author:    Michael Veksler.
   5  ***************************************************************************
   6  * File:      shm_fragment.c
   7  * Purpose:   Data fragments and free list items. Allocate and free blocks.
   8  ***************************************************************************
   9  */
  10 #include <stdio.h>                 /* for debugging only */
  11 #include <stddebug.h>
  12 #include <debug.h>                 /* for "stddeb" */
  13
  14 #include "shm_fragment.h"
  15 #include "shm_block.h"
  16
  17 /******************************************************************************
  18  *
  19  * Free list: all fragments are ordered according to memory location.
  20  *            new fragments are inserted in this way.
  21  *
  22  ******************************************************************************
  23  */
  24
  25 #define FRAG_PTR(block,ofs) ((struct shm_fragment *) ((char *) block + ofs) )
  26 #define NEXT_FRAG(block,ofs) ( FRAG_PTR(block,ofs)->info.next )
  27
  28 /* setup first item in the free list */
  29 void shm_FragmentInit(struct shm_block *block,int first, int size)
  30 {
  31   struct shm_fragment *fragment;
  32
  33   /* round up to nearest 16 byte boundary */
  34   first=(first+15)& ~15;
  35   block->free_list=first;
  36
  37   /* make all the block (exluding the header) free */
  38   fragment= FRAG_PTR(block, first);
  39   block->free=  fragment->size=  size-first;
  40   fragment->info.next=0;
  41 }
  42
  43 void shm_FragPtrFree(struct shm_block *block, void *ptr)
  44 {
  45   /* ptr points to fragment->info.data, find pointer to fragment,
  46    * find the offset of this pointer in block.
  47    */
  48   if (ptr)
  49      shm_FragmentFree(block, PTR2REL(block, ptr));
  50 }
  51 void shm_FragmentFree(struct shm_block *block, int fragment_ofs)
  52 {
  53   struct shm_fragment *fragment=NULL;
  54   int prev;
  55   int next;
  56
  57   fragment_ofs-=(int )&fragment->info.data;
  58   fragment= FRAG_PTR(block, fragment_ofs);
  59
  60   block->free+=fragment->size;
  61   /* scan free list to find candidates for merging with fragment */
  62   for (prev=0, next=block->free_list;
  63        (next!=0) && (fragment_ofs > next)  ;
  64        prev=next, next=NEXT_FRAG(block,next) )
  65      ;
  66
  67   /* insert fragment between, prev and next
  68    *  prev==0: fragment will be the first item in free list
  69    *  next==0: fragment will be the last item in free list
  70    */
  71
  72
  73   /* update fragment (point to next, or merge with next) */
  74
  75   if ( fragment_ofs+fragment->size == next ) {
  76      /* merge with the next free block */
  77      fragment->size+=    FRAG_PTR(block,next)->size;
  78      fragment->info.next=FRAG_PTR(block,next)->info.next;
  79   } else
  80      /* fragment should be inserted before the next fragment or end of */
  81      /* list. (not merged)  */
  82      fragment->info.next=next;
  83   /* now fragment has all the information about the rest of the list */
  84
  85
  86   /* upate prev fragment (point or merge with fragment) */
  87
  88   if (prev==0)             /* first item in free list */
  89      block->free_list=fragment_ofs;
  90   else if ( prev+FRAG_PTR(block,prev)->size == fragment_ofs ) {
  91      /* merge fragment with previous fragment */
  92      FRAG_PTR(block,prev)->size+=    fragment->size;
  93      FRAG_PTR(block,prev)->info.next=fragment->info.next;
  94   } else
  95      /* insert fragment after previous fragment */
  96      FRAG_PTR(block,prev)->info.next=fragment_ofs;
  97 }
  98
  99 /* use "first fit" algorithm,
 100  * return: offset to data in fragment.
 101  */
 102 int shm_FragmentAlloc(struct shm_block *block, int size)
 103 {
 104   int prev;
 105   int candidate;
 106   struct shm_fragment *fragment;
 107   struct shm_fragment *ret_fragment;
 108
 109   if (size <= 0)
 110      return NIL;
 111   /* add size of  "fragment->size" */
 112   size+= (char *)&fragment->info.data - (char *)fragment ;
 113
 114   /* round "size" to nearest 16 byte value */
 115   size= (size+15) & ~15;
 116   if (size > block->free)
 117      return NIL;
 118   /* scan free list to find candidates for allocation */
 119   for (prev=0, candidate=block->free_list;
 120        candidate!=0 ;
 121        prev=candidate, candidate= fragment->info.next )
 122   {
 123      fragment=FRAG_PTR(block,candidate);
 124      if (fragment->size >= size)
 125         break;
 126   }
 127
 128   if (candidate == 0)
 129      return NIL;
 130
 131   block->free-=size;
 132   if (fragment->size == size) {
 133      if (prev == 0)
 134         block->free_list= fragment->info.next;
 135      else
 136         FRAG_PTR(block,prev)->info.next= fragment->info.next;
 137      return PTR2REL(block, &fragment->info.data);
 138   }
 139
 140   /* fragment->size > size */
 141
 142   /* Split fragment in two, return one part, put the other in free list.  */
 143   /* The part that starts at the old location - will stay in the free list. */
 144   fragment->size -= size;
 145
 146   ret_fragment=FRAG_PTR(block, candidate + fragment->size);
 147   ret_fragment->size= size;
 148   return PTR2REL(block, ret_fragment->info.data);
 149 }
 150
 151 /* like shm_FragmentAlloc, returns pointer instead of offset */
 152 char *shm_FragPtrAlloc(struct shm_block *block, int size)
 153 {
 154   int ofs;
 155   ofs= shm_FragmentAlloc(block,size);
 156   if (ofs == NIL)
 157      return NULL;
 158   else
 159      return (char *) REL2PTR(block, ofs);
 160 }
 161 /* This is used for debugging only */
 162 void shm_print_free_list(struct shm_block *block)
 163 {
 164   struct shm_fragment *fragment;
 165   int item;
 166
 167   item=block->free_list;
 168   if (item==0) {
 169      fprintf(stddeb,"no free fragments");
 170   } else {
 171      for (; item ; item=fragment->info.next) {
 172         fragment=FRAG_PTR(block,item);
 173         fprintf(stddeb,"{0x%04x,0x%04x} ",item,fragment->size);
 174      }
 175   }
 176   fprintf(stddeb," [total free=%04x]\n",block->free);
 177   fflush(stddeb);
 178 }