I'm going to try something different in implementing DFFS. Instead of
doing all of the coding, I'll describe parts of the problem and see
what members of this NG come up with for code. The DFFS design is
described at
http://www.geocities.com/mammonsfool/DFFS.pdf

-- Brad

Here is a snippet of the problem:

10 constant FreeSpaces
FreeSpaces 2* cells buffer: FreeSpace
\ Assume the array is initialized to 0.
\ Each element contains 2 cells: length and cluster

Insert ( length cluster -- )
\ Insert this item into the list such that lengths remain sorted from
largest to smallest. If the item is too small it may be discarded.

Delete ( idx -- )
\ Delete a list item and shrink the list.

Smallest ( len -- idx )
\ Find the item whose length is smallest but greater than or equal to
len.
\ The list is probably not big enough to merit a binary search.
\ If not found, throw an error.

Brad,

  You got me interested.  How about posting a sample of what the data
in the array looks like.

Frank


On Aug 21, 11:43 am, Brad Eckert <nospaambr...@tinyboot.com> wrote:
> I'm going to try something different in implementing DFFS. Instead of
> doing all of the coding, I'll describe parts of the problem and see
> what members of this NG come up with for code. The DFFS design is
> described athttp://www.geocities.com/mammonsfool/DFFS.pdf
>
> -- Brad
>
> Here is a snippet of the problem:
>
> 10 constant FreeSpaces
> FreeSpaces 2* cells buffer: FreeSpace
> \ Assume the array is initialized to 0.
> \ Each element contains 2 cells: length and cluster
>
> Insert ( length cluster -- )
> \ Insert this item into the list such that lengths remain sorted from
> largest to smallest. If the item is too small it may be discarded.
>
> Delete ( idx -- )
> \ Delete a list item and shrink the list.
>
> Smallest ( len -- idx )
> \ Find the item whose length is smallest but greater than or equal to
> len.
> \ The list is probably not big enough to merit a binary search.
> \ If not found, throw an error.

On Aug 23, 6:40 am, Frank <fjru...@yahoo.com> wrote:
> How about posting a sample of what the data
> in the array looks like.

FreeSpace is a list of empty-cluster runs. At startup, the FAT table
would be scanned to build up a list of these runs. The longest runs
make it into the list so it doesn't matter if the list is too small to
hold all found runs. List elements are doubles: length and
starting_cluster. Here is some sample contents of FreeSpace after:

125 7463 INSERT  \ 125 clusters found at cluster 7463
155 8278 INSERT  \ 155 clusters found at cluster 8278

Initial  1st insertion  2nd insertion
0 0      125 7463       155 8278
0 0      0 0            125 7463
0 0      0 0            0 0

SMALLEST should return the address of the best fit. For example,

130 SMALLEST returns FreeSpace
120 SMALLEST returns FreeSpace+2*CELL
300 SMALLEST throws an error

I think DELETE isn't needed. The list is built at startup and maybe
rebuilt occasionally if the system never resets. SMALLEST is used to
set up a cluster move, and after the move the length and starting
sector of that FreeSpace entry is updated. So, the freespace pool is
gradually used up. If it becomes too small, the table is re-built from
the FAT again so that recently freed space is counted. SMALLEST should
probably invoke FATSCAN ( -- ) before throwing an error due to
insufficient free space.

On Aug 23, 9:54 am, Brad Eckert <nospaambr...@tinyboot.com> wrote:
> On Aug 23, 6:40 am, Frank <fjru...@yahoo.com> wrote:
>
> > How about posting a sample of what the data
> > in the array looks like.
>
> FreeSpace is a list of empty-cluster runs. At startup, the FAT table
> would be scanned to build up a list of these runs. The longest runs
> make it into the list so it doesn't matter if the list is too small to
> hold all found runs. List elements are doubles: length and
> starting_cluster. Here is some sample contents of FreeSpace after:
>
> 125 7463 INSERT  \ 125 clusters found at cluster 7463
> 155 8278 INSERT  \ 155 clusters found at cluster 8278
>
> Initial  1st insertion  2nd insertion
> 0 0      125 7463       155 8278
> 0 0      0 0            125 7463
> 0 0      0 0            0 0
>
> SMALLEST should return the address of the best fit. For example,
>
> 130 SMALLEST returns FreeSpace
> 120 SMALLEST returns FreeSpace+2*CELL
> 300 SMALLEST throws an error
>
> I think DELETE isn't needed. The list is built at startup and maybe
> rebuilt occasionally if the system never resets. SMALLEST is used to
> set up a cluster move, and after the move the length and starting
> sector of that FreeSpace entry is updated. So, the freespace pool is
> gradually used up. If it becomes too small, the table is re-built from
> the FAT again so that recently freed space is counted. SMALLEST should
> probably invoke FATSCAN ( -- ) before throwing an error due to
> insufficient free space.

In ANS Forth.

10 constant FreeSpaces

2 cells constant element-size
FreeSpaces element-size * constant FreeSpace-size
create FreeSpace  FreeSpace-size allot
: FreeSpace[] ( n -- adr) element-size * FreeSpace + ;

\ Assumes FreeSpace is sorted from largest to smallest.
\ Returns 0 if insufficient free space.
: smallest  ( needed -- where )
  0 swap     ( where needed )
  FreeSpace
  dup FreeSpace-size + swap
  do     ( where needed )
    dup  i @  >
    if   leave   then
    nip  i  swap

    element-size
  +loop
  drop
;

: test
  FreeSpaces 0 do
    FreeSpaces 1-  i -  100 *  i FreeSpace[]  !
  loop

  cr
  FreeSpaces 0 do
    i FreeSpace[] @ . cr
  loop

  cr
  988 709 133 40 1
  5 0 do
    dup .
    smallest
    dup if  @  then  .  cr
  loop
;

On Aug 23, 3:08 pm, expandaf...@yahoo.com wrote:
> On Aug 23, 9:54 am, Brad Eckert <nospaambr...@tinyboot.com> wrote:
>
> > On Aug 23, 6:40 am, Frank <fjru...@yahoo.com> wrote:
>
> > > How about posting a sample of what the data
> > > in the array looks like.
>
> > FreeSpace is a list of empty-cluster runs. At startup, the FAT table
> > would be scanned to build up a list of these runs. The longest runs
> > make it into the list so it doesn't matter if the list is too small to
> > hold all found runs. List elements are doubles: length and
> > starting_cluster. Here is some sample contents of FreeSpace after:
>
> > 125 7463 INSERT  \ 125 clusters found at cluster 7463
> > 155 8278 INSERT  \ 155 clusters found at cluster 8278
>
> > Initial  1st insertion  2nd insertion
> > 0 0      125 7463       155 8278
> > 0 0      0 0            125 7463
> > 0 0      0 0            0 0
>
> > SMALLEST should return the address of the best fit. For example,
>
> > 130 SMALLEST returns FreeSpace
> > 120 SMALLEST returns FreeSpace+2*CELL
> > 300 SMALLEST throws an error
>
> > I think DELETE isn't needed. The list is built at startup and maybe
> > rebuilt occasionally if the system never resets. SMALLEST is used to
> > set up a cluster move, and after the move the length and starting
> > sector of that FreeSpace entry is updated. So, the freespace pool is
> > gradually used up. If it becomes too small, the table is re-built from
> > the FAT again so that recently freed space is counted. SMALLEST should
> > probably invoke FATSCAN ( -- ) before throwing an error due to
> > insufficient free space.
>
> In ANS Forth.
[...]

Replaced ">" with "u>" and cleaned up a bit.

10 constant FreeSpaces

2 cells constant element-size
FreeSpaces element-size * constant FreeSpace-size
create FreeSpace  FreeSpace-size allot
: FreeSpace[] ( n -- adr)  element-size * FreeSpace + ;

\ Assumes FreeSpace is sorted from largest to smallest.
\ Returns 0 if insufficient free space.
\ Question: what should happen if a 0 is passed to
\ this function?
: smallest  ( needed -- where )
  0 swap     ( where needed )
  FreeSpaces FreeSpace[]
  FreeSpace
  do     ( where needed )
    dup  i @  u>
    if   leave   then
    nip  i  swap

    element-size
  +loop
  drop
;

: test
  FreeSpaces 0 do
    FreeSpaces 1-  i -  100 *  i FreeSpace[]  !
  loop
  cr
  ." cluster-runs in FreeSpace:"
  cr
  FreeSpaces 0 do
    i FreeSpace[] @ . cr
  loop
  cr
  -1 988 709 133 100 1
  6 0 do
    ." clusters needed: "
    dup 4 .r
    smallest
    ."   found: "
    dup if  @  then  4 .r  cr
  loop
;

On Aug 24, 1:41 am, expandaf...@yahoo.com wrote:
[...]
> > In ANS Forth.
>
> [...]
>
[...]

Added Insert and .FreeSpace.

10 constant FreeSpaces

2 cells constant element-size
FreeSpaces element-size * constant FreeSpace-size
create FreeSpace  FreeSpace-size allot
: FreeSpace[] ( n -- adr)  element-size * FreeSpace + ;

: shift ( adr direction -- )
  dup >r
  element-size *  over  + ( adr1 adr2)
  2dup max  FreeSpaces FreeSpace[]  swap -
  move
  r> 0 <
  if  \ Shifting left.
    0 0  FreeSpaces 1- FreeSpace[]  2!
  then
;

\ Insert this item into the list such that lengths
\ remain sorted from largest to smallest. If the
\ item is too small it may be discarded.
: Insert ( length cluster -- )
  0 rot
  FreeSpaces FreeSpace[]
  FreeSpace
  do     ( cluster where length)
    dup  i @  u>
    if   nip i swap  leave   then

    element-size
  +loop
  swap dup
  if   ( cluster length where)
    dup 1 shift
    2!
  else
    2drop drop
  then
;

\ Assumes FreeSpace is sorted from largest to smallest.
\ Returns 0 if insufficient free space.
\ Question: what should happen if a 0 is passed to
\ this function?
: smallest  ( needed -- where )
  0 swap     ( where needed )
  FreeSpaces FreeSpace[]
  FreeSpace
  do     ( where needed )
    dup  i @  u>
    if   leave   then
    nip  i  swap

    element-size
  +loop
  drop
;

: .FreeSpace
  cr
  FreeSpaces 0 do
    i FreeSpace[]  2@
    4 .r 6 .r cr
  loop
;

: test
  FreeSpaces 0 do
    0 0    i FreeSpace[]  2!
  loop
  72 4823 insert
  691 3289 insert
  100 2525 insert
  375 7800 insert
  822 5776 insert
  cr
  ." cluster-runs in FreeSpace:"
  cr
  .FreeSpace
  cr
  -1 988 709 133 100 1
  6 0 do
    ." clusters needed: "
    dup 4 .r
    smallest
    ."   found: "
    dup if  @  then  4 .r  cr
  loop
;

On Aug 24, 1:13 am, expandaf...@yahoo.com wrote:
> On Aug 24, 1:41 am, expandaf...@yahoo.com wrote:
> [...]> > In ANS Forth.

I was thinking of making Smallest throw an error if no entry of
sufficient size is found. But first it should rebuild the table by
clearing it and re-scanning the FAT to count runs of free clusters. I
call the word that does this BuildFree. BuildFree uses Insert.

The reason for using THROW is that many file words like WRITE-FILE,
OPEN-FILE, etc. use Smallest as well as several other operations that
can fail. One failure means the file word should terminate, and the
easiest way to handle this is via CATCH/THROW.

: BuildFree ( -- ) ;

20 constant DiskFullIOR

: _smallest ( len -- addr error )
\ Find the smallest usable free sector, error if none found.
   1- >r FreeSpaces begin dup while 1-          ( cnt | len )
     dup 2* cells FreeSpace +  dup @ r@ >       ( cnt a . | len )
     if nip r> drop 0 exit then drop
   repeat r> drop DiskFullIOR ;

: Smallest ( len -- addr )
\ Find the item whose length is smallest but >= len.
   dup _smallest if drop BuildFree _smallest throw else nip then ;