Subversion Repositories Filer-Free

Rev

Rev 18 | Blame | Compare with Previous | Last modification | View Log | RSS feed

// 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);
}