COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### DFFS open source

• Email
• Follow

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

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.

 0

See related articles to this posting

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
>
>
> 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.

 0
Reply fjrusso (58) 8/23/2007 1:40:31 PM

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.

 0

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
;

 0
Reply expandafter (56) 8/23/2007 8:08:08 PM

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
;

 0
Reply expandafter (56) 8/24/2007 6:41:26 AM

On Aug 24, 1:41 am, expandaf...@yahoo.com wrote:
[...]
> > 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 + ;

: shift ( adr direction -- )
dup >r
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
;

 0
Reply expandafter (56) 8/24/2007 8:13:42 AM

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 ;

 0

6 Replies
32 Views

Similar Articles

12/13/2013 11:12:22 AM
[PageSpeed]

Similar Artilces:

[News] PacktPub Rewards Open Source Projects, Sun Opens Open Source Portal
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 PacktPub 2008 Awards - Most Promising Open Source Web CMS ,----[ Quote ] | Every great web CMS contest showcases winners in much anticipated categories, | frequently highlighting names everyone already knows. But what about the new | guy on the block? PacktPub.com is proud to announce the 2008 Most Promising | CMS winners. `---- http://www.cmswire.com/cms/web-cms/packtpub-2008-awards-most-promising-open-source-web-cms-003432.php OSUM portal from Sun ,----[ Quote ] | Yes, that acronym is pronounced “Awesome.” Cheesy acronyms aside, the Op...

Open Source Conference in Japan: Open Source Realize Forum 2005

[News] Open Source Advantage in Digital Signage, Open Source Fakers Join In
Open-Source Technology in Digital Signage ,----[ Quote ] | Open Source and Free software have transformed the software business. Instead | of spending hundreds of thousands of dollars and getting locked in, we have | been given freedom. Freedom to be our own equipment's boss; freedom to share; | and freedom to benefit from cooperation and hence from what thousands of | others have already done. | | Many Digital Signage providers use Open Source both in the products like | Media Players, and to run their operations cost-effectively. By doing so, | they can concentrate on our “re...

[News] Open Source for Books, Open Source Magazine, and Java on Linux (Digest)
Creating ebooks with open source tools http://software.newsforge.com/software/06/07/18/152227.shtml?tid=130&tid=132&tid=138 welcome to o3 magazine ,----[ Snippet ] | The focus of o3 is on the use of Free and Open Source (FOSS) software | in Enterprise Data Networking environments. `---- http://www.o3magazine.com/ Homepage of Java on Linux http://www.blackdown.org/ ...

[News] Insoshi Goes Open Source, Social Networking and Open Source Connected
Social Networking Goes Open Source With Insoshi ,----[ Quote ] | Insoshi is not the first company to release its social networking code. | Broadband Mechanics has always emphasized the openness of its | PeopleAggregator platform, and even Ning, the most publicized DIY social | networking company, will give you the underlying code if you request it. `---- http://www.techcrunch.com/2008/04/29/social-networking-goes-open-source-with-insoshi/ Social Networking and Open Source: Cut From the Same Cloth ,----[ Quote ] | However, social and open source are starting to actually blend -- where...

Open Source, Open World
<http://slashdot.org/> <quote> "This article takes a brief look at open source software in Brazil and how it's transforming tech use in South America: Bringing free software to Brazil, however, is not just a matter of copying North American practices. The idea of free software has also been substantially transformed through contact with Brazilian politics. In the United States, the open source software community has long had libertarian leanings, which have only strengthened over time. The core tenet of free software, after all, is giving the users freedom to do...

[News] Why Software Freedom is More Important Than Open Source, 100% "Open Source" PC Arrives
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Why open standards, open source, and free software are not the same thing. (And never will be) ,----[ Quote ] | Much like “Open Standard”, the term “Open | Source is pretty hollow and vapid. It has | been abused and watered down such to the | point that a company can release some | source code and only give you the ability | to look at it, and maybe not you. | Microsoft’s Shared Source program is an | example of this. Shared Source sounds | better than “Closed Source” or | “Proprietary”, and they can even have | their ho...

[News] Government Gives \$150,000 to Build Open Source Game Engine, John Carmack Committed to Open Source
Profs Building Open-Source Educational Gaming Engine ,----[ Quote ] | Washington State University Vancouver professor Scott Wallace and University | of Puget Sound computer science professor Andrew Nierman were recently | awarded a \$150,000 grant from the National Science Foundation to build a | gaming engine designed to make learning computer science more absorbing for | students. `---- http://campustechnology.com/articles/49650/ QuakeCon Wrapup [with John Carmack] ,----[ Quote ] | Q: I wanted to say thank you for open-sourcing the Quake 3 engine, it's made | a huge differenc...

Could Microsoft directly attack Linux and the Open Source community byusing its programmers to develop viruses and/or other malicious software to discredit the security of the Open Source projec
I think this could be seen in the very near future as the popularity Windows is starting to decline among the mainstream. And if M\$ actually threatened Asian nations against using Linux, then this subtle way of taking it down is VERY possible, IMO. What do you think?, and, if M\$ actually do this, how will the Open Source community react? Check this out, isn't it strange that it didn't affect Internet Explorer?: http://story.news.yahoo.com/news?tmpl=story&ncid=1817&e=3&u=/nf/20050209/tc_nf/30348&sid=96120760 Juggernaut@icepr.com wrote: > Check this out, isn't...

NYC LOCAL: Thursday 19 May 2005 UNIGROUP: Maria Winslow, author of The Practical Manager's Guide to Open Source, on Getting Your Manager to Approve Open Source
<blockquote what="official UNIGROUP announcement"> Date: Mon, 16 May 2005 06:46:05 -0400 (EDT) From: Unigroup_of_NY <unilist@unigroup.org> Subject: UNIGROUP 19-MAY-2005 (Thu): Getting Your Manager to Approve Open Source Unigroup's May 2005 meeting is THIS Thursday... ================================================================ UNIGROUP OF NEW YORK - UNIX USERS GROUP - MAY 2005 ANNOUNCEMENTS ================================================================ ------------------------------------------------ 1. UNIGROUP'S MAY 2005 GENERAL...

open source
Hi Folk For the last few years I have been working on an application for small hotels, bed and breakfast, function places (e.g. restaurants) and the like. Slowly, the application is starting to work better and better. It has now been installed in a few great locations and it is doing very well. The application has been written with the following philosophy: 1. not so easy for novices, super fast and easy for regular users. Not for dummies but for smarties. For example, not so many icons and the like, but easy data-entry. 2. modular design (same concepts are used throughout) 3. very ...

Hi I have always feels that , the open source software more unstable. Especially when I use Linux, there are always many problems, and most of them are hard to solve. Such as eclipse for linux, I have tried it on some linux, like ubuntu, suse, I felt that , it's more unstable than windows edition. Do you have the same feeling? why is this could happen? On Tue, 6 Mar 2012 07:30:21 -0800 (PST), leilei <huxuelei630@gmail.com> wrote: >Hi I have always feels that , the open source software more unstable. >Especially when I use Linux, there are always many problems, and most &g...

Tru64 file system source code now open source
http://www.informationweek.com/news/software/open_source/showArticle.jhtml?articleID=208800252 John Smith wrote: > http://www.informationweek.com/news/software/open_source/showArticle.jhtml?articleID=208800252 > > > ## Tru64 is a 64-bit Unix operating system for the Alpha microprocessor architecture owned by HP. Tru64 was a product of Compaq, which was acquired by HP in 2002. ## No mention of Tru64 coming from Digital. No mention about Alpha having been murdered and Tru64 development having stopped in 2001. The last paragraph though is the best. Finally, a true reflection ...

can't use View, Source menu to open the source code.
Hi, I can't use View, Source menu to open the source code of a page. I am using WinXP and IE 6. Here is the link: http://news.wenxuecity.com/BBSView.php?SubID=news&MsgID=21414 Could you try it? If you can't use View, Source menu to open the source code, could you help me to figure out why? Thanks a lot. Jenny Jenny wrote: > Hi, > > I can't use View, Source menu to open the source code of a page. I am > using WinXP and IE 6. Here is the link: Works fine in Firefox and IE. The charset is gb2312, which may require extra language support but I'm n...

Closed Source Vs. Open Source Bug Dynamics / Applied to Linux History
http://arxiv.org/pdf/cond-mat/0306511 "We introduce a microscopic model of software bug dynamics....we apply our model to Linux History and determine qualitative lower bounds to quality of its programmers" "john bailo" <jabailo@earthlink.net> wrote in message news:989e2a80b02a19e9dd258597e7f6187f@news.teranews.com... > > > http://arxiv.org/pdf/cond-mat/0306511 > > "We introduce a microscopic model of software bug dynamics....we apply our > model to Linux History and determine qualitative lower bounds to quality > of its programmers"...

Open Cloud Roundup: Open Source Dominates Private, Hybrid Enterprise Clouds
https://www.linux.com/news/enterprise/cloud-computing/589506:open-cloud-roundup-top-stories-this-week ...

[News] Open Source and Open Standards Symbiotic; Implication of Microsoft Killing ISO
Open Source and Open Standards ,----[ Quote ] | The acceptance and success of open source development methodologies pose both | a challenge and an opportunity for standards organizations such as the JCP. | Some argue that standards are less necessary in an open-source world, or that | the collaborative efforts of open source communities can develop "de facto | standards" in a more agile manner than the more traditional standards bodies | whose processes are necessarily more cautious and time-consuming. I believe | that both open standards and open source are necessary; they ca...

[News] How Openness and Freedom ("Open Source") Improve Quality of Life
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Open source prosthetics ,----[ Quote ] | I found out about www.openprosthetics.org | in March, and immediately fell in love. | NPR described the creator, Jonathan | Kuniholm's mission, as an "open-source | collaboration that makes its innovations | available to anyone." `---- http://www.boingboing.net/2010/04/02/open-source-prosthet-1.html Open-source biotechnology ,----[ Quote ] | The free software community, along with the | commercial ecosystem which surrounds it, is | widely seen as having pointe...

[News] [OSS] US Air Force and I-Open Adopt and Praise the Open Source Approach
Air Force wants to reuse software components ,----[ Quote ] | The strategy, said Charles Riechers, the Air Force's principal | deputy assistant secretary for acquisition, is to "encourage the | use of open standards, open data interfaces and best-of-breed open | source software solutions." `---- http://www.gcn.com/online/vol1_no1/44278-1.html I-Open Selects Near-Time Web Platform to Accelerate Economic Development Communities Across the U.S. ,----[ Quote ] | The new models of economic development that I-Open is developing | and deploying initially are in Ohio, Kentucky and I...

[News] Government of France and Texas Lean Towards Free/Open Source/Open Data
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 FR: Chamber of Commerce selects open source for craftsmen ,----[ Quote ] | A DVD with a selection of free and open | source software applications tailored to | very small businesses (VSBs), was | published by the Chamber of Commerce for | Crafts and Trades of the French Somme | Department, earlier this year. | | "Our goal is to assist VSBs in their use | of office productivity tools and business | applications", writes Alain Bethfort, | president of the organisation, in his | introduction. `---- http://www...