freelist.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
*
* All rights reserved.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* to whom the Software is furnished to do so, provided that the above
* copyright notice(s) and this permission notice appear in all copies of
* the Software and that both the above copyright notice(s) and this
* permission notice appear in supporting documentation.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
* OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
* INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
* NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
* WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*
* Except as contained in this notice, the name of a copyright holder
* shall not be used in advertising or otherwise to promote the sale, use
* or other dealings in this Software without prior written authorization
* of the copyright holder.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "freelist.h"
typedef struct FreeListBlock FreeListBlock;
struct FreeListBlock {
char *nodes; /* The array of free-list nodes */
};
struct FreeList {
unsigned blocking_factor; /* The number of nodes per block */
long nbusy; /* The number of nodes that are in use */
long ntotal; /* The total number of nodes in the free list */
void *free_list; /* The free-list of nodes */
};
/*.......................................................................
* Allocate a new free-list from blocks of 'blocking_factor' objects of size
* node_size.
*
* Input:
* node_size size_t The size of the free-list nodes to be returned
* by _new_FreeListNode(). Use sizeof() to
* determine this.
* blocking_factor unsigned The number of objects of size 'object_size'
* to allocate per block.
* Output:
* return FreeList * The new freelist, or NULL on error.
*/
{
/*
* When a free-list node is on the free-list, it is used as a (void *)
* link field. Roundup node_size to a mulitple of the size of a void
* pointer. This, plus the fact that the array of nodes is obtained via
* malloc, which returns memory suitably aligned for any object, will
* ensure that the first sizeof(void *) bytes of each node will be
* suitably aligned to use as a (void *) link pointer.
*/
node_size = sizeof(void *) *
((node_size + sizeof(void *) - 1) / sizeof(void *));
/*
* Enfore a minimum block size.
*/
if(blocking_factor < 1)
blocking_factor = 1;
/*
* Allocate the container of the free list.
*/
if(!fl) {
return NULL;
};
/*
* Before attempting any operation that might fail, initialize the
* container at least up to the point at which it can safely be passed
* to _del_FreeList().
*/
/*
* Allocate the first block of memory.
*/
};
/*
* Add the new list of nodes to the free-list.
*/
/*
* Return the free-list for use.
*/
return fl;
}
/*.......................................................................
* Re-thread a freelist to reclaim all allocated nodes.
* This function should not be called unless if it is known that none
* of the currently allocated nodes are still being used.
*
* Input:
* fl FreeList * The free-list to be reset, or NULL.
*/
{
if(fl) {
/*
* Re-thread the nodes of each block into individual free-lists.
*/
/*
* Link all of the block freelists into one large freelist.
*/
/*
* Locate the last node of the current block.
*/
/*
* Make the link-field of the last node point to the first
* node of the current freelist, then make the first node of the
* new block the start of the freelist.
*/
};
/*
* All allocated nodes have now been returned to the freelist.
*/
};
}
/*.......................................................................
* Delete a free-list.
*
* Input:
* fl FreeList * The free-list to be deleted, or NULL.
* force int If force==0 then _del_FreeList() will complain
* and refuse to delete the free-list if any
* of nodes have not been returned to the free-list.
* If force!=0 then _del_FreeList() will not check
* whether any nodes are still in use and will
* always delete the list.
* Output:
* return FreeList * Always NULL (even if the list couldn't be
* deleted).
*/
{
if(fl) {
/*
* Check whether any nodes are in use.
*/
return NULL;
};
/*
* Delete the list blocks.
*/
{
while(next) {
};
};
/*
* Discard the container.
*/
};
return NULL;
}
/*.......................................................................
* Allocate a new object from a free-list.
*
* Input:
* fl FreeList * The free-list to return an object from.
* Output:
* return void * A new object of the size that was specified via
* the node_size argument of _new_FreeList() when
* the free-list was created, or NULL if there
* is insufficient memory, or 'fl' is NULL.
*/
{
void *node; /* The node to be returned */
/*
* Check arguments.
*/
if(!fl)
return NULL;
/*
* If the free-list has been exhausted extend it by allocating
* another block of nodes.
*/
if(!block)
return NULL;
/*
* Prepend the new block to the list of free-list blocks.
*/
/*
* Add the new list of nodes to the free-list.
*/
};
/*
* Remove and return a node from the front of the free list.
*/
/*
* Record the loss of a node from the free-list.
*/
/*
* Return the node.
*/
return node;
}
/*.......................................................................
* Return an object to the free-list that it was allocated from.
*
* Input:
* fl FreeList * The free-list from which the object was taken.
* object void * The node to be returned.
* Output:
* return void * Always NULL.
*/
{
/*
* Check arguments.
*/
if(!fl)
return NULL;
/*
* Return the node to the head of the free list.
*/
if(object) {
/*
* Record the return of the node to the free-list.
*/
};
return NULL;
}
/*.......................................................................
* Return a count of the number of nodes that are currently allocated.
*
* Input:
* fl FreeList * The list to count wrt, or NULL.
* Output:
* return long The number of nodes (or 0 if fl==NULL).
*/
{
}
/*.......................................................................
* Query the number of allocated nodes in the freelist which are
* currently unused.
*
* Input:
* fl FreeList * The list to count wrt, or NULL.
* Output:
* return long The number of unused nodes (or 0 if fl==NULL).
*/
{
}
/*.......................................................................
* Allocate a new list of free-list nodes. On return the nodes will
* be linked together as a list starting with the node at the lowest
* address and ending with a NULL next pointer.
*
* Input:
* fl FreeList * The free-list to allocate the list for.
* Output:
* return FreeListBlock * The new linked block of free-list nodes,
* or NULL on error.
*/
{
/*
* Allocate the container.
*/
if(!block)
return NULL;
/*
* Before attempting any operation that might fail, initialize the
* container at least up to the point at which it can safely be passed
* to _del_FreeListBlock().
*/
/*
* Allocate the block of nodes.
*/
return _del_FreeListBlock(block);
/*
* Initialize the block as a linked list of FreeListNode's.
*/
/*
* Update the record of the number of nodes in the freelist.
*/
return block;
}
/*.......................................................................
* Link each node of a freelist block to the node that follows it.
*
* Input:
* fl FreeList * The freelist that contains the block.
* block FreeListBlock * The block to be threaded.
*/
{
int i;
}
/*.......................................................................
* Delete a free-list block.
*
* Input:
* fl FreeListBlock * The block to be deleted, or NULL.
* Output:
* return FreeListBlock * Always NULL.
*/
{
if(fl) {
};
return NULL;
}