Revision 64 (by gdshaw@RISCPKG.ORG, 2007/05/21 05:44:33) Disabled exceptions and enabled optimisation to reduce code size.
// This file is part of the free Filer module for RISC OS.
// Copyright � 2007 Graham Shaw.
// Redistribution and modification are permitted under the terms of the
// GNU General Public License (version 2 or any later version).

#include <cstring>
#include <new>

#include "oslib/osfscontrol.h"

#include "sort_method.h"
#include "sort_by_name.h"
#include "directory.h"

/** The attribute bit used to indicate whether or not a file is selected.
 * See the note about storage of the selection flag in the declaration of
 * directory::value_type.
 */
static const int attr_selected=0x80000000;

directory::value_type::value_type():
	_info(0)
{}

directory::value_type::value_type(osgbpb_info* info):
	_info(info)
{
	_info->attr&=~attr_selected;
}

bool directory::value_type::selected() const
{
	return (_info->attr&attr_selected)!=0;
}

void directory::value_type::selected(bool state)
{
	if (state) _info->attr|=attr_selected;
	else _info->attr&=~attr_selected;
}

void directory::reserve(size_type capacity)
{
	// Do nothing unless the required capacity exceeds the current capacity.
	if (capacity>_capacity)
	{
		// Allocate new, larger array.
		value_type* new_values=new(std::nothrow) value_type[capacity];
		value_type* old_values=_values;

		// Copy values from old array to new array.
		for (size_type i=0;i!=_size;++i)
		{
			new_values[i]=old_values[i];
		}

		// Switch to new array.
		_values=new_values;
		_capacity=capacity;

		// Deallocate old array.
		delete[] old_values;
	}
}

directory::iterator directory::lower_bound(value_type info)
{
	// Initially, result could lie anywhere from 0 to _size inclusive.
	size_type first=0;
	size_type last=_size;

	// Repeat until result range has narrowed to one possibility.
	while (last!=first)
	{
		// Go to index in middle of range (rounding down: first<=mid<last).
		size_type mid=(first+last)/2;
		if (_sort->less(*info,*_values[mid]))
		{
			// If required index is lower than the index probed then
			// the insertion point can be no later than (but may be
			// equal to) the index probed.
			last=mid;
		}
		else
		{
			// Otherwise, the insertion point must be later than the
			// index probed.
			first=mid+1;
		}
	}

	// Return the result as an iterator.
	// (Note that first and last would be equally valid here.)
	return _values+first;
}

void directory::insert(value_type info,iterator pos)
{
	// Ensure that there is sufficient space for this insertion.
	// (The iterator is temporarily converted to an index during this
	// operation in order to survive a possible relocation of the data.)
	size_type index=pos-begin();
	if (_capacity==_size) reserve(_size+1);
	pos=begin()+index;

	// Make space for new entry.
	for (iterator i=end();i!=pos;--i)
	{
		*i=*(i-1);
	}
	++_size;

	// Insert new entry.
	_values[index]=info;
}

void directory::erase(iterator pos)
{
	// Move following entries into space vacated by deletion.
	for (iterator i=pos,i_end=end();i!=i_end;++i)
	{
		*i=*(i+1);
	}
	--_size;
}

directory::directory(sort_method& sort):
	_sort(&sort),
	_size(0),
	_capacity(0),
	_values(0)
{}

directory::~directory()
{
	for (size_type i=0;i!=_size;++i)
	{
		osgbpb_info* info=_values[i];
		delete[] (int*)info;
	}
	delete[] _values;
}

void directory::sort(sort_method& sort)
{
	// Change the sorting method.
	_sort=&sort;

	// Perform an insertion sort.
	for (unsigned int i=1;i<_size;++i)
	{
		value_type value=_values[i];
		unsigned int j=i;
		while (j&&_sort->less(*value,*_values[j-1]))
		{
			_values[j]=_values[j-1];
			--j;
		}
		_values[j]=value;
	}
}

void directory::load(const char* pathname,int* buffer,size_t buffer_size)
{
	// Record current sorting method then change to sort-by-name.
	// (The sorting method must not take account of anything but
	// the name during a reload, otherwise the existing selection
	// may not be correctly preserved.)
	sort_method* user_sort=_sort;
	static sort_by_name by_name;
	sort(by_name);

	// Mark all existing entries as deleted (but do not actually delete
	// them, so that they can still be found and their selection state
	// copied).
	for (size_type i=0,i_end=size();i!=i_end;++i)
	{
		_values[i]->obj_type=fileswitch_NOT_FOUND;
	}

	// Iterate through directory.
	int context=0;
	while (context!=-1)
	{
		// Read a buffer-full of directory entries.
		int count=0;
		if (xosgbpb_dir_entries_info(pathname,(osgbpb_info_list*)buffer,
			(buffer_size)/sizeof(osgbpb_info),context,buffer_size,0,
			&count,&context))
		{
			break;
		}

		// Reserve space for new entries now (as opposed to doing so
		// piecemeal) to reduce the number of reallocations.
		reserve(_size+count);

		// Process buffer.
		const int* p=buffer;
		for (int i=0;i!=count;++i)
		{
			// Calculate length of current entry (in words).
			osgbpb_info* info_src=(osgbpb_info*)p;
			size_t info_words=5+((strlen(info_src->name)+4)>>2);

			// Choose insertion point.
			iterator f=lower_bound(info_src);
			if (f!=end()&&!_sort->less(*info_src,**f)&&
				!_sort->less(**f,*info_src))
			{
				// If an entry with that leafname is already present
				// then re-use that entry.
				int selected=((*f)->attr&attr_selected);
				**f=*info_src;
				(*f)->attr&=~attr_selected;
				(*f)->attr|=selected;
			}
			else
			{
				// If the leafname is not already present then create
				// a new entry and insert it into the directory.
				value_type info(
					(osgbpb_info*)new(std::nothrow) int[info_words]);
				*info=*info_src;
				strcpy(info->name,info_src->name);
				insert(info,f);
			}

			// Move to next entry.
			p+=info_words;
		}
	}

	// Iterate through directory, removing any entries which have been
	// marked as deleted.  Some care is needed here because it is not
	// safe to simply proceed from index 0 to _size: the act of deleting
	// an entry changes the size of the array and the index must be
	// adjusted accordingly.
	size_t i=0;
	while (i!=_size)
	{
		if (_values[i]->obj_type==fileswitch_NOT_FOUND)
		{
			// Make a note of the entry to be deleted.
			osgbpb_info* info=_values[i];

			// Remove the entry from the directory.
			erase(_values+i);

			// Deallocate the entry.
			delete[] (int*)info;
		}
		else
		{
			// If nothing was deleted then increment the index.
			// (Conversely, and quite importantly, if something /was/
			// deleted then do /not/ increment the index.)
			++i;
		}
	}

	// Revert to the sorting method that had previously been chosen.
	sort(*user_sort);
}