/* @(#)Z 1.4 com/src/cm/FreeSpce.c, odstorage, od96nt, odnt9712d 97/03/21 16:47:55 (96/10/29 09:18:19) */
/*====START_GENERATED_PROLOG======================================
 */
/*
 *   COMPONENT_NAME: odstorage
 *
 *   CLASSES: none
 *
 *   ORIGINS: 82,27
 *
 *
 *   (C) COPYRIGHT International Business Machines Corp. 1995,1996
 *   All Rights Reserved
 *   Licensed Materials - Property of IBM
 *   US Government Users Restricted Rights - Use, duplication or
 *   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
 *   	
 *   IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 *   ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 *   PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR 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.
 */
/*====END_GENERATED_PROLOG========================================
 */

/*
	File:		FreeSpce.c 

	Contains:	Container Manager Free Space Value Management Routines

	Written by:	Ira L. Ruben

	Owned by:	Ed Lai

	Copyright:	© 1992-1994 by Apple Computer, Inc., all rights reserved.

	Change History (most recent first):

		 <6>	 9/26/95	EL		1286040: Make sure space from global names
									do not go to free space if it is not on
									disk.
		 <5>	 8/16/95	EL		1238951: Bento file has wrong deleted-space
													value.
		 <4>	 12/9/94	EL		#1182275 Optionally do not maintain
													continue flag. Keep all free space, no
													matter how small and delete small segment
													only on closing.
		 <3>	 9/30/94	EL		#1182275 rename mergeCandidate to
													updateMergeCandidate.
		 <2>	 8/26/94	EL		#1182275 Handling of temporary free list.
													Correct value in spaceDeletedValue in
													merging. Avoid giving out highly fragmented
													blocks.
		 <4>	 5/10/94	EL		#1162327. ValueDoNotFree is no longer
													needed.
		 <3>	  4/6/94	EL		Do not free free space property when it is
													taken over. #1150214
		 <2>	 3/31/94	EL		Check to see if new free space is just
													behind another free segment. #1150214
		 <1>	  2/3/94	EL		first checked in
		 <5>	 1/19/94	EL		Free space just released will not be used
													immediately, but will be keep in a
													temporary list that is merge to the
													permanent free list at close time.
		 <4>	  1/6/94	EL		Add cmTakeOverFreeList call to transfer the
													free list.
		 <3>	11/16/93	EL		Correct the value of spaceDeletedValue.
		 <2>	 11/4/93	EL		Do not put deleted space in target
													container into the free list. Arrange data
													in free list in ascending order so that it
													can be merged into larger blocks.

	To Do:
*/

/*---------------------------------------------------------------------------*
 |                                                                           |
 |                            <<< FreeSpce.c  >>>                            |
 |                                                                           |
 |          Container Manager Free Space Value Management Routines           |
 |                                                                           |
 |                               Ira L. Ruben                                |
 |                                 4/23/92                                   |
 |                                                                           |
 |                    Copyright Apple Computer, Inc. 1992-1994               |
 |                           All rights reserved.                            |
 |                                                                           |
 *---------------------------------------------------------------------------*
 
 This file contains routines for reusing deleted data space.  The routines record the
 deleted space and reuse it for value data writes.
 
 The free space is maintained as a list of value segment entries for a "free space"
 property belonging to the TOC ID 1 entry.  It is written to the container like other ID 1
 properties to keep track of all the deleted space.
 
 If a container is opened for reusing free space, we use the free list to reuse the space.
*/


#include <stddef.h>
#include <stdio.h>

#ifndef __CMTYPES__
#include "CMTypes.h"
#endif
#ifndef __CM_API__
#include "CMAPI.h"
#endif
#ifndef __LISTMGR__
#include "ListMgr.h"
#endif
#ifndef __TOCENTRIES__
#include "TOCEnts.h"   
#endif
#ifndef __TOCOBJECTS__
#include "TOCObjs.h"   
#endif
#ifndef __TOCIO__
#include "TOCIO.h"
#endif
#ifndef __GLOBALNAMES__
#include "GlbNames.h"   
#endif
#ifndef __CONTAINEROPS__
#include "Containr.h"  
#endif
#ifndef __HANDLERS__
#include "Handlers.h"
#endif
#ifndef __SESSIONDATA__
#include "Session.h"          
#endif
#ifndef __FREESPACE__
#include "FreeSpce.h" 
#endif
																	
																	
																	CM_CFUNCTIONS

/* The following generates a segment directive for Mac only due to 32K Jump Table 			*/
/* Limitations.  If you don't know what I'm talking about don't worry about it.  The		*/
/* default is not to generate the pragma.  Theoritically unknown pragmas in ANSI won't	*/
/* choke compilers that don't recognize them.  Besides why would they be looked at if		*/
/* it's being conditionally skipped over anyway?  I know, famous last words!						*/

#if CM_MPW
#pragma segment TOCEntries
#endif

/*----------------------------------------------------------------*
 | removeEmptyFreeSpace - remove free space header if it is empty |
 *----------------------------------------------------------------*
 
 Check to see if free space is empty. If it is, completely remove that property.
*/
 
static void CM_NEAR removeEmptyFreeSpace(ContainerPtr container)
{
	TOCObjectPtr	 theTOCObject;
	TOCPropertyPtr theFreeListProperty;
	/* If there are no more free list entries, delete the value header and the "free 			*/
	/* space" property from TOC ID 1...																										*/
		
	TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
	if (freeSpaceValueHdr) {
		if (cmIsEmptyList(&freeSpaceValueHdr->valueList)) {			/* if no more free list...	*/
			theFreeListProperty = freeSpaceValueHdr->theProperty;	/* ...get owning property		*/
			theTOCObject 				= theFreeListProperty->theObject;	/* ...get owning object (1)	*/
			CMfree(freeSpaceValueHdr);														/* ...clobber the value hdr	*/
			CMfree(cmDeleteListCell(&theTOCObject->propertyList, theFreeListProperty));
			container->freeSpaceValueHdr = NULL;									/* ...no more free list			*/
		}
#if CMKEEP_CONTINUE_FLAG
		else if (cmCountListCells(&freeSpaceValueHdr->valueList) == 1)
			freeSpaceValueHdr->valueFlags &= ~ValueContinued;			/* only 1, then no cont			*/
#endif
	}
}

/*------------------------------------------------*
 | deleteFreeListEntry - delete a free list entry |
 *------------------------------------------------*
 
 This routine removes the specified free list entry and frees up its space.  If this is 
 the last entry of the free list, the free list property itself (along with its value
 header, of course) are removed.
 
 Note, this routine is a low-level routine called from the other routines in this file.
 As such there are no error checks.  The caller is assumed "happy" with what its doing by
 the time it calls this routine.
*/

static void CM_NEAR deleteFreeListEntry(TOCValuePtr theValue)
{
	ContainerPtr 	 container = theValue->theValueHdr->container;
	TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
#if CMKEEP_CONTINUE_FLAG
	TOCValuePtr		 prevValue;
	
	prevValue = (TOCValuePtr) cmGetPrevListCell(theValue);
	if (prevValue) {
		prevValue->flags = theValue->flags;				/* if theValue is last, now you are last 	*/
	}
#endif

	/* Delete the value entry from its list and free its space...													*/
	
	freeSpaceValueHdr->size -= theValue->value.notImm.valueLen;
	CMfree(cmDeleteListCell(&freeSpaceValueHdr->valueList, theValue));
	
	removeEmptyFreeSpace(container);						/* remove the property if it is empty			*/
}

/*----------------------------------------------------------------------------------*
 | rearrangePermFreeList - arrange items in free list in ascending order and merged |
 *----------------------------------------------------------------------------------*

	!.0d5 or earlier code writes a free list that is not in sorted order.

	This version expects free list item to be in sorted order.
	
	We do this by moving all the items in the perm free list into the temp free list.
	Then we move it back from the temp free list to the perm free list.
	Since the 2nd operation always ensure list items are in ascending order and
	adjacent items would be combined into one. We can back the list we want.
	
	However we do not want to move items originally in the temp free list to the perm
	free list. So we save the temp free list in the beginning and restore the temp free 
	list at the end.
*/
 
static void CM_NEAR rearrangePermFreeList(ContainerPtr container)
{
	ListHdr 				saveList = container->tmpList;
	TOCValuePtr		 	theValue;
	CM_ULONG				size;
	
	cmInitList(&container->tmpList);	
	theValue = (TOCValuePtr)cmGetListHead(&container->freeSpaceValueHdr->valueList);
	
	while (theValue) {															/* scan the free space list...				*/
		size = theValue->value.notImm.valueLen;
		container->spaceDeletedValue->value.imm.ulongValue -= size;
		cmAddToTmpFreeList(container, theValue->value.imm.ulongValue, size);
		theValue = (TOCValuePtr)cmGetNextListCell(theValue);
	}	
	container->freeSpaceValueHdr->size = 0;										/* we removed everything		*/
	cmFreeAllListCells(&container->freeSpaceValueHdr->valueList, SESSION);
	cmCopyTmpFreeToTOC(container);			/* move from temp tmp list back to perm free list	*/
	
	container->tmpList = saveList;
}

/*------------------------------------------------------------------------*
 | addToPermFreeList - add freed space to the permanent "free space" list |
 *------------------------------------------------------------------------*

	This routine takes some free space and put it into the permanent free space property
	for use in future.

  As part of the freeing process, we scan the free list to see if the new space can be 
	combined with an already existing entry.  It's a sort of on-the-fly garbage collector.
	
	For new containers, there is no "free space" property initially for ID 1.  It is created
	here the first time we need to free space.  We remember the value header for the "free
	space" property so that we may efficiently get at the list on all future calls.
*/
 
static void CM_NEAR addToPermFreeList(ContainerPtr container,
										 	 CM_ULONG offset, CM_ULONG size)
{
	TOCObjectPtr 	 theTOCobject;
	TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
	TOCValuePtr		 theValue = NULL, nextValue;
	CM_ULONG	 		 valueStart, valueEndPlus1, prevStart;
	TOCValueBytes  valueBytes;
	void					 *toc;
	
		
	/* See if the space we're freeing can be combined with some already existing free			*/
	/* space.  If the new space is already freed (now how could that happen?) we ignore		*/
	/* the new space.  If the chunk of space we are about to free is less than the size		*/
	/* of a TOC entry, we ignore it (losing track of that space), since it would cost more*/
	/* to remember it.  However, if that space can be combined with already existing 			*/
	/* space, we do the combining.																												*/ 
	
	if (freeSpaceValueHdr != NULL) {								/* if free space list exists...				*/
		theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
		prevStart = 0;
		
		while (theValue) {														/* scan the free space list...				*/
			valueStart 		= theValue->value.imm.ulongValue;
			valueEndPlus1 = valueStart + theValue->value.notImm.valueLen;
			if (prevStart > valueStart) {
				/* the list is not in order, must have been written by 1.0d5 or earlier software*/
				rearrangePermFreeList(container);							/* make sure it is in order first	*/
				addToPermFreeList(container, offset, size);		/* now do it again								*/
				return;
			}
			prevStart = valueStart;
			if (offset >= valueStart) { 													/* this is after this				*/
				if (offset <= valueEndPlus1) { 											/* have overlap or concat		*/
					if (offset + size > valueEndPlus1) {			/* combine new amount with this entry*/
						size = (offset + size) - valueEndPlus1;	/* reduce actual size to add in				*/
						theValue->value.notImm.valueLen += size;/* this is what we combine in					*/
						freeSpaceValueHdr->size += size;				/* echo total size in header					*/
						container->spaceDeletedValue->value.imm.ulongValue += size;
						/* we may able to join with the next value to form a single value						*/
						valueEndPlus1 += size;
						nextValue = (TOCValuePtr)cmGetNextListCell(theValue);
						if (nextValue) 
							if (nextValue->value.imm.ulongValue <= valueEndPlus1) {
								/* we can combine with next value, absorb the next value in this one		*/
								theValue->value.notImm.valueLen = nextValue->value.imm.ulongValue +
									nextValue->value.notImm.valueLen - theValue->value.imm.ulongValue;
								/* we bump up the free space to cancel out deleteFreeListEntry					*/
								freeSpaceValueHdr->size += nextValue->value.imm.ulongValue;
								/* now everything in next value in in this one, we can delete next value*/
								deleteFreeListEntry(nextValue);
							}
					}
					return;																		/* exit since we updated "old" entry*/
				}
			} else if (offset + size >= valueStart) {			/* can combine from the lower end		*/
				theValue->value.imm.ulongValue = offset;		/* this is the low end							*/
				if (offset + size > valueEndPlus1)
					valueEndPlus1 = offset + size;
				size = valueEndPlus1 - offset - theValue->value.notImm.valueLen; /* increment */
				theValue->value.notImm.valueLen += size;/* this is what we combine in					*/
				freeSpaceValueHdr->size += size;				/* echo total size in header					*/
				container->spaceDeletedValue->value.imm.ulongValue += size;
				return;																		/* exit since we updated "old" entry	*/
			} else
				break;																			/* it should be inserted before here*/
			theValue = (TOCValuePtr)cmGetNextListCell(theValue);
		}
	} /* checking for combining */
	
#if 0	
	/* Since the cost of recording the free space in the container will be a TOC entry, we*/
	/* only record free space chucks whose size is LARGER than a TOC entry.  Since we 		*/
	/* couldn't combine it with already existing space, we simply exit and forget it.			*/

	#if TOC1_SUPPORT
	if (container->majorVersion == 1) {
		if (size <= TOCentrySize) return;
	} else 
		if (size <= MinTOCSize) return;
	#else
	if (size <= MinTOCSize) return;
	#endif
#endif
	/* If this is the first freed space in the container, create the "free space" property*/
	/* for the TOC object 1.  Otherwise, just use it. We remember the pointer to the value*/
	/* header for this property in the container.  Note, the TOC we want to deal with here*/
	/* is the container's own (private) TOC.  This will be different from the current TOC	*/
	/* when we're updating containers.																										*/
	
	if (freeSpaceValueHdr == NULL) {								/* if 1st free space for container...	*/
		toc = container->toc;													/* ...remember current TOC						*/
		container->toc = container->privateTOC;				/* use container's own (private) TOC	*/
		
		theTOCobject = cmDefineObject(container,			/* ...create "free space" property		*/
									 								CM_StdObjID_TOC, CM_StdObjID_TOC_Free,
																	CM_StdObjID_TOC_Type, NULL,
									 								container->generation, 0,
																	(ObjectObject | ProtectedObject),
									 								&freeSpaceValueHdr);
		
		container->toc = toc;													/* restore current container					*/
		if (theTOCobject == NULL) return;
		freeSpaceValueHdr->valueFlags |= ValueProtected;/* don't allow writing to this value*/
		container->freeSpaceValueHdr = freeSpaceValueHdr;
	} 

	/* At this point we want to create a new free list entry for the newly freed offset 	*/
	/* size.  The value list are standard value entries for the "free space" property of	*/
	/* TOC object ID 1.																																		*/

	container->spaceDeletedValue->value.imm.ulongValue += size;

	(void)cmSetValueBytes(container, &valueBytes, Value_NotImm, offset, size);
	
#if CMKEEP_CONTINUE_FLAG
	if (theValue) {																			/* it should come before this			*/
		/* create a new value, and insert before theValue																		*/
		/* if we are successful, then update the value header to reflect it									*/
		if (cmInsertBeforeListCell(&freeSpaceValueHdr->valueList, 
															 cmCreateValueSegment(freeSpaceValueHdr, &valueBytes, kCMContinued), 
															 theValue)) {
			freeSpaceValueHdr->valueFlags |= ValueContinued;/* also set a more convenient flag	*/
			freeSpaceValueHdr->size += size;								/* echo total size in header					*/
		}
	} else {																						/* we should put it at very end		*/
		theValue = (TOCValuePtr)cmGetListTail(&freeSpaceValueHdr->valueList);
		if (theValue) {
			theValue->flags |= kCMContinued;								/* flag the current value as cont'd	*/
			freeSpaceValueHdr->valueFlags |= ValueContinued;/* also set a more convenient flag	*/
		}
		cmAppendValue(freeSpaceValueHdr, &valueBytes, 0);
	}
#else
	if (theValue) {																			/* it should come before this			*/
		/* create a new value, and insert before theValue																		*/
		/* if we are successful, then update the value header to reflect it									*/
		if (cmInsertBeforeListCell(&freeSpaceValueHdr->valueList, 
															 cmCreateValueSegment(freeSpaceValueHdr, &valueBytes, 0), 
															 theValue)) {
			freeSpaceValueHdr->size += size;								/* echo total size in header					*/
		}
	} else {																						/* we should put it at very end		*/
		theValue = (TOCValuePtr)cmGetListTail(&freeSpaceValueHdr->valueList);
		cmAppendValue(freeSpaceValueHdr, &valueBytes, 0);
	}
#endif
}

/*-----------------------------------------------------------------------*
 | cmAddToTmpFreeList - add freed space to the temporary "free space" list |
 *-----------------------------------------------------------------------*

	This routine takes some free space and put it into the temporary free space property
	for use in future.
	
	We want to put thing in the temporary free list for two reasons.
	
	For container opened for writing, we don't want to write into the old container
	before we close it in case it crashes before it is closed, so we put it into
	the temporary free list.
	
	For container opened for updating, we have free space that can be reused if
	it is merged. Since we do not know whether we will just close the container
	or merge it, we put it in the temporary free list and put it on the real
	free list only if we do a merge at close time.

*/
 
void cmAddToTmpFreeList(ContainerPtr container, CM_ULONG offset, CM_ULONG size)
{
  FreeSpaceItem	*toBeFree;

	toBeFree = CMmalloc(sizeof(FreeSpaceItem));			/* so we can get rid of SCpp warning*/
	if (toBeFree) {
		toBeFree->offset = offset;
		toBeFree->size = size;
		cmAppendListCell(&container->tmpList, toBeFree);
	}
}

/*-----------------------------------------------------------------------------------*
 | cmAddValueToTmpFreeList - add space in a value to the temporary "free space" list |
 *-----------------------------------------------------------------------------------*

	This routine put all the free space used by a value into the temporary free list

*/
 
void cmAddValueToTmpFreeList(TOCValueHdrPtr theValueHdr)
{
	TOCValuePtr theValue = (TOCValuePtr)cmGetListHead(&theValueHdr->valueList);

	while (theValue) {
		/* use targetContainer->updatingContainer because during applyUpdate						*/
		/* updatingContainer point to itself, so we need to get the real updating cntr	*/
		cmAddToTmpFreeList(theValueHdr->container->targetContainer->updatingContainer,
											 theValue->value.notImm.value,
											 theValue->value.notImm.valueLen);
		theValue = (TOCValuePtr)cmGetNextListCell(theValue);
	}
}

/*----------------------------------------------------------------------*
 | cmAddToFreeList - add freed space to the permanent "free space" list |
 *----------------------------------------------------------------------*

 This routine is called whenever space for value data is to be freed.  The space is
 recorded in a free list. The free list entries are maintained as value segments belonging
 to the "free space" property of TOC object ID 1.
 
 The amount of space to be freed is specified in one of two possible ways:
 
 		1. By passing a pointer to a value segment in theValueToFree.  The offset and size
			 are extracted from the segment info.  If theValueToFree is for an immediate value,
			 we simply exit since there is no container space to actually free.  Global names,
			 as usual, are handled specially.  In particular, for no global names that have not
			 yet been written to the container yet (we keep 'em in memory unto we write the TOC
			 at container close time), then we ingore them just like immediates.  For "old"
			 global names we do account for the space.
			 
		2. If theValueToFree is passed as NULL, then an explicit size and offset may be
			 passed.  Note that a non-null theValueToFree has precedence over explicit offset
			 and size.
*/
 
void cmAddToFreeList(ContainerPtr container, TOCValuePtr theValueToFree,
		   							 CM_ULONG offset, CM_ULONG size)
{
	Boolean		mayGoToTmpList = false;

	/* We only track free space when a container is opened for writing or updating.  			*/
	/* However, even when writing there is an override switch to suppress the space				*/
	/* tracking.  This is done during applying updates during open time.  We don't want		*/
	/* to track what's going on then!																											*/
	
	if (!container->trackFreeSpace ||								/* if no tracking of free space or...	*/
		  (container->useFlags & kCMWriting) == 0)		/* ...not opened for writing/updating	*/
		return;																				/* ...exit														*/
	
	/* Get the offset and size from the value if it's specified. This is the amount being	*/
	/* freed.  If theValueToFree is NULL, then the offset and size must be explicitly 		*/
	/* specified, otherwise these parameters are ignored.  As a safety, if the value is		*/
	/* passed, but it is for an immediate value, there is no space being given up, so we	*/
	/* just exit.																																					*/
	
	if (theValueToFree != NULL) {										/* if value explicitly specified...		*/
		if ((theValueToFree->container->depth == 1) && (container->useFlags & kCMMerging))
			mayGoToTmpList = true;
		else if (theValueToFree->container != container)/* does it belong to this level?		*/
			return;																				/* no, then just return							*/
		if (theValueToFree->flags & kCMGlobalName) {	/* ...handle global names specially		*/
			if (theValueToFree->theValueHdr->valueRefCon == 0) 
				return; 																	/* not written, nothing to free				*/
			offset = theValueToFree->value.globalName.offset;	
			if (offset == 0) return; 										/* this is an extra precaution check */
			size = GetGlobalNameLength(theValueToFree->value.globalName.globalNameSymbol) + 1;
		} else if (theValueToFree->flags & kCMImmediate)
			return;																			/* ...ignore immediates...						*/
		else {																				/* ...have "normal" value							*/
			offset = theValueToFree->value.notImm.value;
			size 	 = theValueToFree->value.notImm.valueLen;
		}
	}
	
	if (size == 0) return;
	
	if (mayGoToTmpList || (container->useFlags & (kCMUpdateByAppend | kCMUpdateTarget) == 0)) {
		/* If the space is from previous container, or in the same container but we are not */
		/* doing an updating, do not reuse freespace until the container is closed.					*/
		/* So even if we crashes before the container is closed, old data is not destroyed	*/
		cmAddToTmpFreeList(container, offset, size);
	}
	else {	
		/* for updating, we do not touch the data in old container directly, so any free  	*/
		/* space comes from the new container and we can put it into the free list directly */
		addToPermFreeList(container, offset, size);
	}
}

/*------------------------------------------------------*
 | tmpListCB - add freed space to the "free space" list |
 *------------------------------------------------------*

 Action routine to take a free space and add it to the permanent free space list.
 */
 
static void CM_NEAR tmpListCB(void * theCell, CMRefCon refCon)
{
    FreeSpaceItem	*toBeFree = (FreeSpaceItem *)theCell;

    addToPermFreeList((ContainerPtr)refCon, toBeFree->offset, toBeFree->size);
}

/*---------------------------------------------------------------*
 | cmCopyTmpFreeToTOC - add freed space to the "free space" list |
 *---------------------------------------------------------------*

	This routine goes through the list of temporary free space and merge each one into
	the permanent free space. At the end the temporary free space are removed.
*/

void cmCopyTmpFreeToTOC(ContainerPtr container)
{
	cmForEachListCell(&container->tmpList, (CMRefCon)container, tmpListCB);

  cmFreeAllListCells(&container->tmpList, container->sessionData);
}

/*-----------------------------------------------------------------------*
 | cmRemoveSmallFreeSpace - remove segment too small to be worth keeping |
 *-----------------------------------------------------------------------*
 
 There is certain overhead of storing a value segment. If a free space segment is so small
 that the overhead of storing it is greater than the free space itself, then it is not
 worth to keep the free space. So we go through the free space list and remove the small
 segments.
 
 On the other hand, later we may free space that are are around these small segments.
 So if we ignore these small segments, we may cause fragmentation of the free space
 later. So we should revisit this issue to see if it is worthwhile to keep them anyway.
*/
 
void cmRemoveSmallFreeSpace(ContainerPtr container)
{
	TOCValuePtr		 theValue, nextValue;
	
	TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
	if (freeSpaceValueHdr) {
		theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
		while (theValue) {
			nextValue = (TOCValuePtr)cmGetNextListCell(theValue);
			/* If the free space is smaller than overhead of keeping track of it, remove it 			*/
			if (theValue->value.notImm.valueLen < MinTOCSize) {
				freeSpaceValueHdr->size -= theValue->value.notImm.valueLen;
				CMfree(cmDeleteListCell(&freeSpaceValueHdr->valueList, theValue));
			}
			theValue = nextValue;
		} /* while value */
		
		removeEmptyFreeSpace(container);
	}
}


/*--------------------------------------------------------------*
 | cmGetFreeListEntry - get a free space entry from "free list" |
 *--------------------------------------------------------------*
 
 This routine returns one free list entry (if one exists).  The offset from that entry is
 returned as the function result.  The size is returned in actualSize.  If there is no 
 free space, or we can't find one big enough (see mustAllFit below), 0 is returned as the
 function result and for the actualSize.  0's are also returned if the container was not
 opened to reuse free space.
 
 The desiredSize is passed as what the caller would like as the single free list entry
 amount, i.e., a "best fit".  It is also used when we find a bigger free list entry and
 only have to reduce part of it.
 
 If mustAllFit is true, then we MUST find a single free list segment big enough or 0 will
 be returned.  This is used for data that is not allowed to be continued with multiple
 value segments (e.g., global names).
 
 The free list is built by cmAddToFreeList() as value segments belonging to a value header
 of the "free space" property for TOC object ID 1.   If all the free list entries are
 exhausted, the value header is freed along with the property.  If space is ever given up
 after this through cmAddToFreeList(), it will recreate the "free space" property, its
 value header, and the free list value entry segments.
*/

CM_ULONG cmGetFreeListEntry(ContainerPtr container, 
														CM_ULONG desiredSize, Boolean mustAllFit,
														CM_ULONG *actualSize)
{
	TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
	TOCValuePtr		 theValue;
	CM_ULONG	 		 offset;
#if MinFragmentSize
	CM_ULONG	 		 minSegmentSize;
#endif

	/* Return null amount if there is no free list or not updating...											*/
	
	if (freeSpaceValueHdr == NULL || (container->useFlags & kCMReuseFreeSpace) == 0)
		return (*actualSize = 0);
	
	/* Use the next available free list entry (segment) no matter what it is unless we 		*/
	/* mustAllFit.  For mustAllFit we must scann the free list for a single entry large		*/
	/* enough to hold the entire data (desiredSize bytes).																*/
	
	/* Note as just said, when mustAllFit is false, we just use the first free list 			*/
	/* segment on the list.  A better algorithm might be to use the desired amount and 		*/
	/* find a "best fit" by scanning the free list just as in the mustAllFit case.  So 		*/
	/* which is better in time and/or space?  A scan each time or just reusing each entry */
	/* unconditionally.  The latter guarantees reuse of all available space.  But the 		*/
	/* former potentially uses less value segments.  For now I take the easy way.					*/
	
	/* Note we still need it to split larger free space entries when we don't need all		*/
	/* the space from an entry.																														*/
	
	theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
	
#if MinFragmentSize
	if ((mustAllFit) || (desiredSize <= MinFragmentSize))
		/* If the block is small, it does not make sense to have different segments. So we	*/
		/* treat it as a single segment to avoid fragmentation.															*/
		minSegmentSize = desiredSize;
	else {
		/* Even if it is a large block, we still don't want it to fragment too much.				*/
		/* This is especially true since the block may be an embedded container. So we try	*/
		/* to limit the number of segments																									*/
#if MaxFragmentCount
		minSegmentSize = desiredSize / MaxFragmentCount;
		if (minSegmentSize < MinFragmentSize)
			minSegmentSize = MinFragmentSize;
#else
		minSegmentSize = MinFragmentSize;
#endif
	}
	
	while (theValue) {																				/* ...scan free list				*/
		if (theValue->value.notImm.valueLen >= minSegmentSize) 	/* ...for one big enough		*/
			break;
		theValue = (TOCValuePtr)cmGetNextListCell(theValue);
	}
	if (theValue == NULL) return (*actualSize = 0);					/* if none found, too bad		*/
#else
	if (mustAllFit) {																					/* if must find single seg	*/
		while (theValue) {																			/* ...scan free list				*/
			if (theValue->value.notImm.valueLen >= desiredSize) 	/* ...for one big enough		*/
				break;
			theValue = (TOCValuePtr)cmGetNextListCell(theValue);
		}
		if (theValue == NULL) return (*actualSize = 0);					/* if none found, too bad		*/
	}
#endif
	
	offset 			= theValue->value.notImm.value;								/* set to return this offset*/
	*actualSize = theValue->value.notImm.valueLen;						/* and this size (maybe!)		*/
	
	/* If the free list entry is big enough to cover all that is desired, use only the		*/
	/* required amount and retain the free list entry.  It must, however, be reduced by		*/
	/* the amount used.																																		*/
	
	/* UNRESOLVED QUESTION! Since we never allow free list entries to be created when the */
	/* space is less than a TOC entry size, should we keep the split space here when it		*/
	/* becomes less than a TOC entry size?  What does it cost?														*/
	
	if (desiredSize < *actualSize) {													/* free entry is too big		*/
		theValue->value.notImm.value    += desiredSize;					/* ...cut it down						*/
		theValue->value.notImm.valueLen -= desiredSize;
		container->spaceDeletedValue->value.imm.ulongValue -= desiredSize; /* cut total			*/
		freeSpaceValueHdr->size -= desiredSize; 								/* less free space now			*/
		*actualSize = desiredSize;															/* return what was desired	*/
		return (offset);
	}
	
	/* Now that we used an entire an free list entry, delete it from the free list and 		*/
	/* free its memory.  If there are no more free list entries, delete the value header 	*/
	/* and the "free space" property from TOC ID 1...																			*/
	
	deleteFreeListEntry(theValue);
	
	container->spaceDeletedValue->value.imm.ulongValue -= *actualSize; /* cut total				*/
	
	return (offset);																					/* return new space to use	*/
}

/*--------------------------------------------------------------------------*
 | cmTakeOverFreeList - have one container take the free space from another |
 *--------------------------------------------------------------------------*
 
 When a target container is open by a container, we want to take over the
 free space in the target container so that we can reuse the free space
 in the target container. Since the target container is open read only, we
 cannot update the free space list there. So the update container move the list
 over so that it becomes the free list of the update container.
 
 This should only be done for one level, so the update container takes the
 free list of the target container. Any free list that is in container that
 is further down may be used already and should not be used.
*/
 
void cmTakeOverFreeList(ContainerPtr toContainer, ContainerPtr container)
{
	TOCValuePtr		 theValue;
	
	TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
	if (freeSpaceValueHdr) {
		theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
		while (theValue) {
			addToPermFreeList(toContainer,
												theValue->value.notImm.value, theValue->value.notImm.valueLen);
			theValue = (TOCValuePtr)cmGetNextListCell(theValue);
		} /* value */
	}
}

/*--------------------------------------------------------------------------*
 | cmWriteData - write data to container with possible resuse of free space |
 *--------------------------------------------------------------------------*
 
 This routine is the Container Manager's low-level value data writer.  It takes a value
 header, and size bytes in the buffer and writes it to the container via the output
 handler.  The amount written is returned.  If it is not equal to the passed size, the
 caller should report an error.
 
 The reason this routine is used rather than using the CMfwrite() handler call directly is
 that this routine checks to see if the container has been opened to reuse free space.  If
 it hasn't, we degenerate into a simple CMfwrite() call.  If it has, then we use the free
 list, built by cmAddToFreeList(), to write out the data segments to reuse the free space.
 
 In all cases the data written is recorded as value segments in the value list belonging
 to the specified value header. The new segments are appended on to the END of the segment
 list.  It is up to the caller to guarantee this is where the segments are to go.  The
 continued flags are appropriately set.
 
 Note, as just mentioned, use this routine ONLY for appending data segments to a value.
 Also, use this routine ONLY if continued segments are permitted for the data.  This means
 you cannot call this routine to write global names.  They are always written as single
 segments.
 
 Even with these restrictions, for the main case, i.e., CMWriteValueData(), this is not a
 problem.  CMWriteValueData() is the primary caller.  It knows what it's doing with the
 data (lets hope so).  So it knows when to call us here.
 
 The net effect is to reuse free space whenever we can if the container was opened for
 updating, and to do straight CMfwrite() otherwise.
*/

CM_ULONG cmWriteData(TOCValueHdrPtr theValueHdr, CM_UCHAR *buffer,
										 CM_ULONG size)
{
	ContainerPtr  container = theValueHdr->container->updatingContainer;
	TOCValuePtr		prevValue;
	CM_ULONG 			chunkSize, offset, amountWritten = 0;
	TOCValueBytes valueBytes;
	Boolean				appendToPrev;

	/* Write out all the data (size bytes of it).  To save a little code space we check 	*/
	/* for updating in the loop.  If we are not updating we will attempt to do a standard	*/
	/* CMfwrite() of all the data as a single value segment.  That is also what happens		*/
	/* when we run out of free space.  Then we try to write out all the remaining data		*/
	/* as a single segment.  The code is the same, so that's why the update check is in 	*/
	/* the loop.  If we are updating, and we do have free list entries, we use them to		*/
	/* see where to write and how much.  This will reuse the free list space.							*/
	
	prevValue = (TOCValuePtr)cmGetListTail(&theValueHdr->valueList); /* last value seg		*/
	
	while (size > 0) {																	/* loop till no more data					*/
		if ((container->useFlags & kCMReuseFreeSpace)==0)	/* if not reusing free space...		*/
			chunkSize = 0;																	/* ...this will cause std write		*/
		else																							/* if updating,get some free space*/
			offset = cmGetFreeListEntry(container, size, false, &chunkSize);
		
		if (chunkSize == 0) {															/* if no free space to reuse...		*/
			offset = CMgetContainerSize(container);
			CMfseek(container, 0, kCMSeekEnd);							/* position to current eof				*/
			if (CMfwrite(container, buffer, sizeof(CM_UCHAR), size) == size) { 			/* write	*/
				amountWritten += size;												/* count total amount written			*/
				container->physicalEOF = offset + size;				/* update next free container byte*/
				SetLogicalEOF(container->physicalEOF);				/* logical EOF == physical EOF		*/
				(void)cmSetValueBytes(container, &valueBytes, Value_NotImm, offset, size);
				cmAppendValue(theValueHdr, &valueBytes, 0);		/* append new value segment				*/
#if CMKEEP_CONTINUE_FLAG
				if (prevValue != NULL) {											/* if this is not 1st segment...	*/
					prevValue->flags |= kCMContinued;						/* ...flag last seg as cont'd			*/
					theValueHdr->valueFlags |= ValueContinued;	/* ...also echo flag in the hdr		*/
				}
#endif
			}
			return (amountWritten);													/* return amount we wrote					*/
		} /* chunkSize == 0 */
		
		/* If we get here then we are going to reuse a free space segment...								*/
		
		CMfseek(container, offset, kCMSeekSet);						/* overwrite the free space chunk	*/
		if (CMfwrite(container, buffer, sizeof(CM_UCHAR), chunkSize) != chunkSize) 
			return (amountWritten);
		
		/* if the free space is right after a previous free space segment, just extend that */

		appendToPrev = true;
		if (prevValue != NULL) {													/* if this is not 1st segment...	*/
			if (((prevValue->flags & kCMImmediate) == 0) &&
					((prevValue->value.notImm.value+prevValue->value.notImm.valueLen) == offset)) {
				prevValue->value.notImm.valueLen += chunkSize;	/* just add to previous value */
				theValueHdr->size += chunkSize;								
				appendToPrev = false;
#if CMKEEP_CONTINUE_FLAG
			} else {																				/* it is discontinous							*/
				prevValue->flags |= kCMContinued;							/* ...flag last seg as cont'd			*/
				theValueHdr->valueFlags |= ValueContinued;		/* ...also echo flag in the hdr		*/
#endif
			};
		}
		
		if (appendToPrev) {
			(void)cmSetValueBytes(container, &valueBytes, Value_NotImm, offset, chunkSize);
			prevValue = cmAppendValue(theValueHdr, &valueBytes, 0);	/* append new value segment	*/
			if (prevValue == NULL) return (amountWritten);
		}
		
		offset += chunkSize;															/* set logical EOF								*/
		SetLogicalEOF(offset);
		
		buffer 				+= chunkSize;												/* point to next chunk to write		*/
		amountWritten += chunkSize;												/* count total amount written			*/
		size 					-= chunkSize;												/* reduce amount yet to be written*/
	} /* while */																				/* loop through all the data			*/
	
	return (amountWritten);															/* return amount we wrote					*/
}


/*----------------------------------------------------------------*
 | cmDeleteFreeSpace - delete free space beyond a specified point |
 *----------------------------------------------------------------*
 
 This routine is called to remove all free list entries that have their space beyond the
 specified offset, beyondHere.  All entries with starting offsets greater than or equal
 to beyondHere are removed.  If one spans beyondHere it will be reduced appropriately.
 
 These entries are removed so so that we may overwrite from beyondHere with a new TOC.
 Since we are reusing that space for the TOC we obviously can't keep free list entries for
 it.
*/

void cmDeleteFreeSpace(ContainerPtr container, CM_ULONG beyondHere)
{
	TOCValuePtr		theValue, nextValue;
	CM_ULONG 			offset, size, newLen;
	TOCValuePtr		spaceDeletedValue = container->spaceDeletedValue;

	if (container->freeSpaceValueHdr == NULL) return;				/* exit if no free list				*/
	
	theValue = (TOCValuePtr)cmGetListHead(&container->freeSpaceValueHdr->valueList);
	
	while (theValue) {																			/* ...scan free list					*/
		nextValue = (TOCValuePtr)cmGetNextListCell(theValue);	/* get next now for deletes		*/
		offset    = theValue->value.notImm.value;							/* offset of a free chunk			*/
		size    = theValue->value.notImm.valueLen;						/* size of a free chunk				*/
		
		if (offset >= beyondHere) {														/* if chunk entirely beyond		*/
			spaceDeletedValue->value.imm.ulongValue -= size;
			deleteFreeListEntry(theValue);											/* ...delete it								*/
		}
		else if (offset + size > beyondHere) { 								/* if partial...							*/
			newLen = beyondHere - offset;												/* ...cut size down						*/
			size -= newLen;																			/* actual size deleted				*/
			spaceDeletedValue->value.imm.ulongValue -= size;		/* decr space deleted					*/
			#if TOC1_SUPPORT
			if (container->majorVersion == 1) {									/* and if format 1 TOC...			*/
				if (newLen <= TOCentrySize) 											/* ...and too small to keep		*/
					deleteFreeListEntry(theValue);									/* ...delete it too						*/
				else {																						/* ...if still acceptable			*/
					container->freeSpaceValueHdr->size -= size;
					theValue->value.notImm.valueLen = newLen;				/* ...set its new smaller size*/
				}
			} else {																						/* if >format 1 TOC						*/
				if (newLen <= MinTOCSize) 												/* ...and still too small			*/
					deleteFreeListEntry(theValue);									/* ...delete it too						*/
				else {																						/* ...if still acceptable			*/
					container->freeSpaceValueHdr->size -= size;
					theValue->value.notImm.valueLen = newLen;				/* ...set its new smaller size*/
				}
			}
			#else
			if (newLen <= MinTOCSize) 													/* ...but if too small to keep*/
				deleteFreeListEntry(theValue);										/* ...delete it too						*/
			else {																							/* ...if still acceptable			*/
				container->freeSpaceValueHdr->size -= size;
				theValue->value.notImm.valueLen = newLen;					/* ...set its new smaller size*/
			}
			#endif
		}
		
		theValue = nextValue;																	/* loop till no more entries	*/
	} /* while */
}

														  CM_END_CFUNCTIONS
