Logo Search packages:      
Sourcecode: adun.app version File versions  Download package

AdunLinkedList.m

/*
   Project: Adun

   Copyright (C) 2006 Michael Johnston & Jordi Villa-Freixa

   Author: Michael Johnston

   This application is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This application is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA.
*/

#include "AdunKernel/AdunLinkedList.h"

00025 @implementation AdLinkedList

- (id) init
{
      return [self initWithBlocksize: 524288];
}

- (id) initWithBlocksize: (int) size
{
      if(self = [super init])
      {
            block_count = 0;
            block_no = 0;
            current_block_no = 0;
            current_block = blocks;
            BLOCKSIZE = size;
//          freeElementsCapacity = 10000;
            freeElementsCount = 0;

      /*    freedElementsList = (ListElement*)malloc(sizeof(ListElement));
            freeElementsEnd = AdLinkedListCreate(freedElementsList);*/

            freeElements = [NSMutableArray new];

            getElement = (id (*)(id, SEL))[freeElements 
                        methodForSelector:@selector(lastObject)];
            removeElement = (void (*)(id, SEL))[freeElements
                        methodForSelector:@selector(removeLastObject)];
            addElement = (void (*)(id, SEL, id))[freeElements 
                        methodForSelector:@selector(addObject:)];

      //    freeElements = (ListElement**)malloc(freeElementsCapacity*sizeof(ListElement*));

            linkedList = (ListElement*)malloc(sizeof(ListElement));
            linkedListEnd = AdLinkedListCreate(linkedList);
            listCount = 0;
      }

      return self;
}

- (void) dealloc
{
      int i;

      [freeElements release];

      //free all allocated blocks
      //this frees all linked list elements
      //except for the first and last

      for(i=0; i<block_no; i++)
            free(blocks[i]);

      block_count = 0;
      current_block_no = 0;
      current_block = blocks;
      //freeElementsCount = 0;

      //free start and end of list

      free(linkedList);
      free(linkedListEnd);

      [super dealloc];
}

/*******************************

Interaction List Memory Management 

********************************/

- (ListElement*) createNewListBlock
{
      ListElement* listPointer;

      if(block_no == 50)
      {
            NSLog(@"Not Enough space in block array for a new block!!");
            exit(1);
      }

      block_no++;
      NSDebugLLog(@"AdListMemoryManagement", @"Creating New Block - There are now %d blocks", block_no);
      //On 64 bit machines we should align on a 64 bit boundary

      posix_memalign((void**)&listPointer, 32, BLOCKSIZE*sizeof(ListElement));
      blocks = listPointer;

      return blocks;
}

/*
- (void) _reinsertElement: (ListElement*) list_p
{
      //find block
      //search if address is between block_adress + blocksize

      for(i=0; i<block_no; i++)
      {
            index = list_p - (blocks + i);
            if(index < blocksize*sizeof(ListElement))
            {
                  block = i;
                  index /= sizeof(ListElement);
                  break;
            }
      }
            
      //search for next nearest address - watching for block changes

      for(i=index+1; i<blocksize; i++)
            if(blockBin[i] == 1)
            {
                  //set
            }     

      //search for previous address - watching for block changes

      for(i=index-1; i>0; i--)
            if(blockBin[i] == 1)
            {
                  //set
            }     
      
      //set bin value to 1

      blockBin[index] = 1;
}*/


//This method returns newly created listelement structures that are
//retreived from previously malloced blocks of memory.
//if their are no free blocks a new block is assigned and ListElements 
//are returned from it

- (ListElement*) getNewListElement
{
      ListElement* el_p;

      listCount++;
      if(block_no == 0)
      {     
            //if there are no blocks make one
            
            current_block = [self createNewListBlock];
            block_count = 0;
            el_p = &current_block;
            block_count++;
      }
      else if(freeElementsCount > 0)
      {
            //else return the last previously freed element
            
            el_p = [[freeElements lastObject] pointerValue];
            el_p =      [getElement(freeElements, @selector(getNewListElement)) pointerValue];
            [freeElements removeLastObject];
            removeElement(freeElements, @selector(removeLastObject));

            //return the last element in freeElements array
            //and then decrement the boundary

            freeElementsCount--;
      }                 
      else if(block_count != BLOCKSIZE)
      {
            //else return memory from the current block
            el_p = &current_block;
            block_count++;
      }
      else if(current_block_no+1 != block_no)
      {
            //else move to the next available block
                  
            current_block_no++;
            current_block = blocks;
            block_count = 0;
            el_p = &current_block;
            block_count++;
      }     
      else
      {
            //else create a new block
            current_block = [self createNewListBlock];
            block_count = 0;
            el_p = &current_block;
            current_block_no++;
            block_count++;
      }

      AdUnsafeLinkedListAdd(el_p, linkedListEnd, 0);
      return el_p;
}

- (void) freeListElement: (ListElement*) list_p
{
      
      //Remove the element from the linked list. 
      //Wipe its data and add its address
      //to the freed element list. We can then return
      //from this list first when an element structure
      //is requested to avoid thrasing memory

      list_p->bond = 0;
      list_p->bond = 0;
      list_p->length = 0;

      AdUnsafeLinkedListExtract(list_p);
      [freeElements addObject: [NSValue valueWithPointer: list_p]];
      addElement(freeElements, 
            @selector(addObject), 
            [NSValue valueWithPointer:list_p]);

      freeElementsCount++;
      listCount--;
}

- (ListElement*) listStart
{
      return linkedList;
}

- (ListElement*) listEnd
{
      return linkedListEnd;
}

- (int) listCount
{
      return listCount;
}

@end


Generated by  Doxygen 1.6.0   Back to index