Subversion Repositories Filer-Free

Compare Revisions

Ignore whitespace Rev 62 → Rev 63

/trunk/filer/pathname_table.cc
New file
0,0 → 1,228
// 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 <cstdio>
 
#include "oslib/os.h"
#include "oslib/osfscontrol.h"
 
#include "pathname_hash.h"
#include "pathname_table.h"
#include "filer_window.h"
 
// Rules for ensuring thread safety:
// - the UpCall handler may search the index at any time (therefore _size
// and the content of _index must be valid at all times).
// - the UpCall handler may assume that the link referred to by _tail is
// always null. It may change that link from null to non-null at any
// time, provided that it first moves _tail to a different null link.
 
/** Upcall handler entry point.
* The interface is as described in the PRM.
*/
extern "C" void upcall_entry();
 
pathname_table::pathname_table(int* pollword):
_size(0),
_capacity(0),
_index_data(0),
_index_nodes(0),
_tail(&_head),
_pollword(pollword)
{
// Initialise refresh queue.
_head.next=0;
 
// Initialise free list.
_free.next=0;
 
// Activate upcall handler.
xos_claim(UpCallV,(void*)upcall_entry,(byte*)this);
}
 
pathname_table::~pathname_table()
{
// Deactivate upcall handler.
xos_release(UpCallV,(void*)upcall_entry,(byte*)this);
 
// Deallocate nodes in index.
for (unsigned int i=0;i!=_size;++i)
{
delete _index_nodes[i];
}
 
// Deallocate nodes in free list.
while (_free.next)
{
node* n=_free.next;
_free.next=n->next;
delete n;
}
 
// Deallocate index.
delete[] _index_data;
delete[] _index_nodes;
}
 
void pathname_table::reserve(size_type capacity)
{
// Each allocation is processed separately in order to avoid
// a memory leak of one of them fails.
if (_capacity<capacity)
{
// Reallocate index data (without allowing the existing index
// to become invalid until it is no longer needed).
int* new_index_data=new int[capacity];
for (unsigned int i=0;i!=_size;++i)
{
new_index_data[i]=_index_data[i];
}
volatile int* old_index_data=_index_data;
_index_data=new_index_data;
delete[] old_index_data;
 
// Reallocate index node pointers (again, without allowing the
// existing node pointers to become invalid until they are no
// longer needed).
volatile node** new_index_nodes=new volatile node*[capacity];
for (unsigned int i=0;i!=_size;++i)
{
new_index_nodes[i]=_index_nodes[i];
}
volatile node** old_index_nodes=_index_nodes;
_index_nodes=new_index_nodes;
delete[] old_index_nodes;
 
// Create new nodes.
while (_capacity<capacity)
{
node* n=new node;
n->next=_free.next;
_free.next=n;
++_capacity;
}
}
}
 
pathname_table::node* pathname_table::insert(filer_window* w)
{
// Ensure there is sufficient capacity for one more node.
reserve(_size+1);
 
// Parse pathname into filing system, special field and tail.
char* pathtail=0;
char* fs_special=0;
fileswitch_fs_no fs_number=osfscontrol_set_temporary_fs(w->pathname(),
&pathtail,&fs_special);
 
// Calculate hash of pathname.
unsigned int hash=pathname_hash(pathtail,strlen(pathtail),
fs_number,fs_special);
 
// Find point at which to insert.
unsigned int f=pathname_find(this,hash);
 
// Select node from free list.
node* n=_free.next;
_free.next=n->next;
 
// Initialise node.
n->next=0;
n->refresh=0;
n->window=w;
n->index=f;
 
// Increment _size, after first ensuring that this will not cause
// the index to become unordered.
_index_data[_size]=0xffffffff;
_index_nodes[_size]=0;
++_size;
 
// Make space for new index entry.
for (unsigned int i=_size-1;i!=f;--i)
{
_index_data[i]=_index_data[i-1];
_index_nodes[i]=_index_nodes[i-1];
_index_nodes[i]->index=i;
_index_nodes[i-1]=0;
}
 
// Create new index entry.
_index_data[f]=hash;
_index_nodes[f]=n;
 
// Return pointer to node.
return n;
}
 
void pathname_table::erase(node* n)
{
// Get location of node in index.
unsigned int f=n->index;
 
// Delete from index.
// Each entry is modified as follows:
// - first the link to the current node is broken
// - next the hash is replaced with the new value
// - finally the link to the new node is established
// An index entry may therefore point to no node, or to the correct
// node for the hash, but never to an incorrect node.
_index_nodes[f]=0;
for (unsigned int i=f+1;i!=_size;++i)
{
_index_data[i-1]=_index_data[i];
_index_nodes[i-1]=_index_nodes[i];
_index_nodes[i-1]->index=i-1;
_index_nodes[i]=0;
}
 
// Remove last entry from index.
// The last entry is now an inactive duplicate of the penultimate
// entry, and can be removed by decrementing the size.
--_size;
 
// Return node to free list.
n->next=_free.next;
_free.next=n;
}
 
void pathname_table::refresh()
{
if (_head.next)
{
// A chain has been started, so the UpCall handler will not now
// alter _head until _tail is reset.
 
// Make a pointer to the first node in the chain.
node* p=_head.next;
 
// Reset _head and _tail. The UpCall handler will not now make
// any changes to the chain about to be processed.
_head.next=0;
_tail=&_head;
 
while (p)
{
// Keep a pointer to the current node, because the chain
// pointer is about to move.
node* n=p;
 
// Move the chain pointer forward now, because the link is
// about to be cleared.
p=n->next;
 
// Clear the forward link and the refresh pending flag
// (in that order). This is done before the filer window
// is refreshed so that if there is further disc activity
// it is refreshed again.
n->next=0;
n->refresh=0;
 
// Refresh the filer window to which the node refers.
n->window->refresh();
}
}
}
/trunk/filer/pathname_find.s
New file
0,0 → 1,84
; 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).
 
GET _pathname_table.s
 
AREA |C$$Code|,CODE,READONLY,REL
 
; Find pathname in table.
;
; On entry:
; R0=pathname table
; R1=hash
; On exit:
; R0=lower bound
; R1=upper bound
; R2-R3,R12 corrupted.
 
EXPORT |pathname_find|
|pathname_find|
STMFD R13!,{R4-R6,R14} ; Preserve registers
MOV R12,R0 ; R12=pathname table
MOV R0,R1 ; R1=hash
 
LDR R1,[R12,#table_index] ; R1=start of range
LDR R2,[R12,#table_size] ; R2=size of table
ADD R2,R1,R2,LSL#2 ; R2=end of range
 
TEQ R1,R2 ;
BEQ |pathname_find_3| ; Jump if range empty
 
|pathname_find_0|
ADD R3,R1,R2 ;
MOV R3,R3,LSR#1 ;
BIC R3,R3,#3 ; R3=middle of range (R1<=R3<R2)
LDR R6,[R3] ; R6=value at middle of range
CMP R0,R6 ;
ADDHI R1,R3,#4 ; If target higher then move start of range
MOVLO R2,R3 ; If target lower then move end of range
TEQNE R1,R2 ;
BNE |pathname_find_0| ; Repeat until found or range is empty
 
TEQ R1,R2 ;
BEQ |pathname_find_3| ; Jump if range empty
 
MOV R4,R3 ; R4=top of range for lower bound
ADD R5,R3,#4 ; R5=bottom of range for upper bound
 
TEQ R1,R4 ;
BEQ |pathname_find_2| ; Jump if lower bound range empty
|pathname_find_1|
ADD R3,R1,R4 ;
MOV R3,R3,LSR#1 ;
BIC R3,R3,#3 ; R3=middle of range (R1<=R3<R4)
LDR R6,[R3] ; R6=value at middle of range
CMP R0,R6 ;
MOVEQ R4,R3 ; If target matches then move end of range
ADDNE R1,R3,#4 ; otherwise move start of range
TEQ R1,R4 ;
BNE |pathname_find_1| ; Repeat until range is empty
 
TEQ R5,R2 ;
BEQ |pathname_find_3| ; Jump if upper bound range empty
|pathname_find_2|
ADD R3,R5,R2 ;
MOV R3,R3,LSR#1 ;
BIC R3,R3,#3 ; R3=middle of range (R5<=R3<R2)
LDR R6,[R3] ; R6=value at middle of range
CMP R0,R6 ;
ADDEQ R5,R3,#4 ; If target matches then move start of range
MOVNE R2,R3 ; otherwise move end of range
TEQ R5,R2 ;
BNE |pathname_find_2| ; Repeat until range is empty
 
|pathname_find_3|
LDR R0,[R12,#table_index] ; R0=start of index
SUB R1,R1,R0 ; R1=offset for lower bound
SUB R2,R2,R0 ; R2=offset for upper bound
MOV R0,R1,LSR#2 ; R0=lower bound
MOV R1,R2,LSR#2 ; R1=upper bound
LDMFD R13!,{R4-R6,PC} ; Return
 
END
/trunk/filer/upcall_refresh.s
New file
0,0 → 1,79
; 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).
 
GET _pathname_table.s
 
AREA |C$$Code|,CODE,READONLY,REL
 
IMPORT |pathname_hash|
IMPORT |pathname_find|
 
; Find filer window associated with given pathname and filing system
; number, add to list of windows awaiting update.
;
; The given pathname is that of an object within the directory,
; therefore its leafname is removed before searching.
;
; On entry:
; R0=pathname (null terminated)
; R1=filing system number
; R2=filing system special field (null terminated) (or 0 if none)
; R12=pathname table
; On exit:
; R0-R3 corrupted (but R12 preserved)
 
EXPORT |upcall_refresh|
|upcall_refresh|
STMFD R13!,{R4,R12,R14} ; Preserve registers
 
MOV R4,R12 ; R4=pathname table
MOV R3,R2 ; R3=fs special field (or 0)
MOV R2,R1 ; R2=fs number
 
; Remove final component of pathname.
MOV R12,R0 ; R12=pointer into pathname
MOV R1,#0 ; R1=pointer to last path separator
; (initially zero)
|upcall_refresh_0|
LDRB R14,[R12],#1 ; R14=char from pathname
TEQ R14,#'.' ;
SUBEQ R1,R12,#1 ; Update R1 if path separator found
TEQ R14,#0 ;
BNE |upcall_refresh_0| ; Repeat until end of pathname
 
TEQ R1,#0 ;
SUBNE R1,R1,R0 ; R1=length of directory pathname
BL |pathname_hash| ; R0=hash
 
MOV R1,R0 ; R1=hash
MOV R0,R4 ; R0=pathname table
BL |pathname_find| ; R0=lower bound, R1=upper bound
 
TEQ R0,R1 ;
BEQ |upcall_refresh_3| ; Skip loop if range empty
LDR R12,[R4,#table_nodes] ; R12=nodes array
|upcall_refresh_1|
LDR R2,[R12,R0,LSL#2] ; R2=pointer to node
LDR R3,[R2,#node_refresh] ; R3=1 if refresh pending, otherwise 0
TEQ R3,#0 ;
BNE |upcall_refresh_2| ; Jump if refresh already pending
 
LDR R3,[R4,#table_tail] ; R3=pointer to tail node
STR R2,[R4,#table_tail] ; Make node at R2 the tail node
STR R2,[R3,#node_next] ; Link node at R2 into the chain
MOV R3,#1 ;
STR R3,[R2,#node_refresh] ; Mark node at R2 as refresh pending
LDR R2,[R4,#table_pollword] ;
STR R3,[R2] ; Set pollword
 
|upcall_refresh_2|
ADD R0,R0,#1 ; Increment pointer into index
TEQ R0,R1 ;
BNE |upcall_refresh_1| ; Repeat until upper bound reached
 
|upcall_refresh_3|
LDMFD R13!,{R4,R12,PC} ; Restore registers and return
 
END
/trunk/filer/upcall_entry.s
New file
0,0 → 1,111
; 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).
 
GET _pathname_table.s
 
AREA |C$$Code|,CODE,READONLY,REL
 
IMPORT |upcall_refresh|
 
X EQU &20000
OS_Args EQU &09
 
; Upcall entry point.
;
; On entry:
; R0=upcall code (3=filesystem modification)
; R1-R7 depend on reason code
; R8=filing system information word
; R9=reason code
; R12=pathname table
; On exit:
; All registers must be preserved
;
; Note that there does not appear to be any reason to respond to
; reason code 258 (opening for update).
 
EXPORT |upcall_entry|
|upcall_entry|
TEQ R0,#3 ; If upcall code!=3
MOVNE PC,R14 ; then return immediately
 
CMP R9,#9 ;
BLO |upcall_pathname_0| ; Reason codes 0-8: R1=pathname
SUB R9,R9,#&100 ;
TEQ R9,#1 ;
BEQ |upcall_pathname_100| ; Reason code &101: R1=pathname
TEQ R9,#3 ;
BEQ |upcall_filehandle_100| ; Reason code &103: R1=filehandle
SUB R9,R9,#&100 ;
TEQ R9,#0 ;
BEQ |upcall_filehandle_200| ; Reason code &200: R1=filehandle
TEQ R9,#8 ;
BEQ |upcall_pathnames_200| ; Reason code &208: R1,R2=pathnames
TEQ R9,#9 ;
BEQ |upcall_pathname_200| ; Reason code &209: R1=pathname
ADD R9,R9,#&200 ;
MOV PC,R14 ; Return if reason not recognised
 
|upcall_pathname_200|
ADD R9,R9,#&100 ; Restore R9 to original-&100
|upcall_pathname_100|
ADD R9,R9,#&100 ; Restore R9 to original value
|upcall_pathname_0|
STMFD R13!,{R0-R3,R14} ; Preserve registers
MOV R0,R1 ; R0=pathname (no FS prefix)
AND R1,R8,#&FF ; R1=filing system number
MOV R2,R6 ; R2=fs special field
BL |upcall_refresh| ; Process pathname
LDMFD R13!,{R0-R3,PC} ; Restore registers and return
 
|upcall_pathnames_200|
ADD R9,R9,#&200 ; Restore R9 to original value
STMFD R13!,{R0-R3,R14} ; Preserve registers
MOV R0,R1 ; R0=first pathname
AND R1,R8,#&FF ; R1=filing system number
MOV R2,R6 ; R2=first special field
BL |upcall_refresh| ; Process first pathname
LDR R0,[R13,#8] ; R0=second pathname
AND R1,R8,#&FF ; R1=filing system number
MOV R2,R7 ; R2=second special field
BL |upcall_refresh| ; Process second pathname
LDMFD R13!,{R0-R3,PC} ; Restore registers and return
 
|upcall_filehandle_200|
ADD R9,R9,#&100 ; Restore R9 to original-&100
|upcall_filehandle_100|
ADD R9,R9,#&100 ; Restore R9 to original value
STMFD R13!,{R0-R3,R5,R14} ; Preserve registers
MOV R0,#7 ; R0=reason code 7 (to OS_Args)
ADD R2,R12,#table_buffer ; R2=buffer for pathname
MOV R5,#&100 ; R3=length of pathname buffer
SWI X+OS_Args ; Get pathname for given file handle
LDMVSFD R13!,{R0-R3,R5,PC} ; Return if error
 
MOV R0,R2 ; R0=pathname
MOV R2,#0 ; R2=special field (default none)
 
|upcall_entry_0|
LDRB R14,[R0],#1 ; R14=char from pathname
TEQ R14,#'#' ;
TEQEQ R2,#0 ;
MOVEQ R2,R0 ; First hash is start of special field
TEQ R14,#':' ;
TEQNE R14,#0 ;
BNE |upcall_entry_0| ; Repeat until colon or end
 
TEQ R14,#':' ; If colon found then replace with
MOVEQ R14,#0 ; null (to terminate special field)
STREQB R14,[R0],#1 ; and step forward
 
; (A colon should never not be found, so there is no need to take
; any particular action except to ensure that the code is reasonably
; well-behaved.)
 
AND R1,R8,#&FF ; R1=filing system number
BL |upcall_refresh| ; Process pathname
LDMFD R13!,{R0-R3,R5,PC} ; Restore registers and return
 
END
/trunk/filer/main.cc
15,13 → 15,17
 
filer_application* app=0;
 
int pollword=0;
 
pathname_table pathnames(&pollword);
 
extern "C"
int main(int argc, char *argv[])
{
if (!app)
{
app=new filer_application;
app->run(0);
app->run(&pollword);
delete app;
app=0;
}
/trunk/filer/filer_window.h
7,6 → 7,7
#define FILER_FILER_WINDOW
 
#include "directory.h"
#include "pathname_table.h"
#include "auto_pos.h"
#include "window.h"
#include "filer_options.h"
48,6 → 49,11
/** The position at which a filer window for a subdirectory will be
* opened. */
auto_pos _auto_pos;
 
/** The node within the pathname table that corresponds to this filer
* window (and which is needed to deregister the pathname when this
* window is destroyed). */
pathname_table::node* _pathname_node;
public:
/** Construct filer window.
* @param app the application to which this filer window belongs
/trunk/filer/filer_application.h
11,6 → 11,7
#include "application.h"
#include "auto_pos.h"
#include "directory.h"
#include "pathname_table.h"
 
class filer_window;
 
43,6 → 44,7
filer_application();
 
virtual void handle_key_pressed(wimp_key& block);
virtual void handle_pollword_non_zero(int* pollword);
virtual void handle_user_message(wimp_event_no event,
wimp_message& message);
virtual void deregister_window(window& w);
65,6 → 67,17
 
/** Cancel rename operation if one is in progress. */
void cancel_rename();
 
/** Register pathname of filer window.
* @param w the window
* @return a pointer to the pathname table node
*/
pathname_table::node* register_pathname(filer_window& w);
 
/** Deregister pathname of filer window.
* @param n a pointer to the pathname table node
*/
void deregister_pathname(pathname_table::node* n);
};
 
#endif
/trunk/filer/filer_window.cc
111,10 → 111,20
open.yscroll=wstate.yscroll;
open.next=wimp_TOP;
open_window(open);
 
// Register this window in the pathnames table.
if (app) _pathname_node=app->register_pathname(*this);
}
 
filer_window::~filer_window()
{
// Deregister this window from the pathnames table.
if (filer_application* app=
dynamic_cast<filer_application*>(parent_application()))
{
app->deregister_pathname(_pathname_node);
}
 
// Delete pathname buffer.
delete[] _pathname;
}
/trunk/filer/_pathname_table.s
New file
0,0 → 1,21
; 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).
 
; The following offsets must match the layout of a pathname_table.
table_size EQU 0
table_capacity EQU 4
table_index EQU 8
table_nodes EQU 12
table_tail EQU 16
table_pollword EQU 20
table_buffer EQU 24
 
; The following offsets must match the layout of a pathname_table::node.
node_next EQU 0
node_refresh EQU 4
node_window EQU 8
node_index EQU 12
 
END
/trunk/filer/filer_application.cc
49,6 → 49,12
if (!handled) application::handle_key_pressed(block);
}
 
void filer_application::handle_pollword_non_zero(int* pollword)
{
*pollword=0;
pathnames.refresh();
}
 
void filer_application::handle_user_message(wimp_event_no event,
wimp_message& message)
{
136,3 → 142,13
_rename_index=directory::npos;
}
}
 
pathname_table::node* filer_application::register_pathname(filer_window& w)
{
return pathnames.insert(&w);
}
 
void filer_application::deregister_pathname(pathname_table::node* n)
{
pathnames.erase(n);
}
/trunk/filer/pathname_table.h
New file
0,0 → 1,138
// 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).
 
#ifndef FILER_PATHNAME_TABLE
#define FILER_PATHNAME_TABLE
 
class filer_window;
 
/** A table for mapping pathnames to filer windows.
* For speed, pathnames are hashed before they are indexed.
* @note At present there is no mechanism for preventing hash collisions:
* all matching filer windows are refreshed. This is considered acceptable.
* @warning The layout of this class must match the offsets given
* in the file "_pathname_table.s".
*/
class pathname_table
{
public:
/** A type to represent a number of index entries. */
typedef unsigned int size_type;
 
/** A class to represent an entry in the table.
* @warning The layout of this structure must match the offsets given
* in the file "_pathname_table.s".
*/
struct node
{
/** The next node in the refresh queue.
* If this is the last node in the queue, or if this is not a
* member of a queue, then the value of this field is undefined
*/
node* next;
 
/** The refresh pending flag.
* True if a refresh is pending for this node (and therefore,
* it has been added to the refresh queue), otherwise false.
*/
int refresh;
 
/** The filer window associated with this node. */
filer_window* window;
 
/** The index entry occupied by this node.
* This may change when other nodes are added or removed from
* the index.
*/
int index;
};
private:
/** The number of nodes in the pathname table. */
volatile size_type _size;
 
/** The capacity of the index. */
size_type _capacity;
 
/** The index (pathname hash array).
* This is a ordered array of pathname hashes. It must remain ordered
* (for all indices less than _size) at all times.
*/
volatile int* _index_data;
 
/** The index (node table). */
volatile node** _index_nodes;
 
/** The tail of the refresh queue. */
volatile node* _tail;
 
/** The pollword to be set if there are windows in need of a refresh. */
int* _pollword;
 
/** A buffer for use by the upcall handler.
* When the upcall handler is notified on an operation on a filehandle
* it converts that filehandle into a pathname. For this is needs a
* buffer to hold the pathname. Allocating from the RMA from within
* the handler would be highly undesirable, therefore a suitable buffer
* is permanently allocated.
*/
char _pathname_buffer[256];
 
/** The head of the refresh queue.
* Although this member is not referenced directly by the upcall
* handler, it can be altered by the handler indirectly through _tail
* (which may point to _head). For this reason it is marked as
* volatile.
*/
volatile node _head;
 
/** The head of the free list. */
node _free;
public:
/** Construct pathname table.
* @param pollword the pollword to be set if there are windows
* in need of a refresh
*/
pathname_table(int* pollword);
 
/** Destroy pathname table. */
~pathname_table();
 
/** Reserve capacity for index to reach given size.
* @param capacity the required capacity of the index
*/
void reserve(size_type capacity);
 
/** Insert filer window into table.
* No action is taken if the filer window is already present.
* @param w the filer window to be inserted
*/
node* insert(filer_window* w);
 
/** Remove filer window from table.
* No action is taken if the filer window is not found.
* @param w the filer window to be removed
*/
void erase(node* n);
 
/** Find filer window given pathname.
* @param pathname the pathname for which to search
* @return the corresponding filer window, or 0 if not found
*/
filer_window* find(const char* pathname);
 
/** Refresh all filer windows for which a refresh is necessary. */
void refresh();
};
 
/** Find pathname in table.
* @param table the pathname table
* @param hash the hash of the pathname to be found
* @param the index into the table of the first match, or table->_size
* if not found
*/
extern "C"
unsigned int pathname_find(pathname_table* table,unsigned int hash);
 
#endif
/trunk/filer/main.h
7,6 → 7,7
#define FILER_MAIN
 
#include "filer_options.h"
#include "pathname_table.h"
 
class filer_application;
 
17,4 → 18,17
* or 0 if the filer is not running. */
extern filer_application* app;
 
/** The pollword used to notify the filer that there is a window to
* be refreshed.
* This variable must be located in global memory so that it is
* accessible to the upcall handle (not in the application slot).
*/
extern int pollword;
 
/** A table of pathnames with open filer windows.
* This variable must be located in global memory so that it is
* accessible to the upcall handle (not in the application slot).
*/
extern pathname_table pathnames;
 
#endif