So I've finished the SWIG/Lua combination for JkDefrag, and while going through everything, I had a couple more questions.
1) You are sorting the tree every 1000 insertions. A constant 1000 insertions is inefficient, and it should be related to the depth of the last insertion. i.e. A perfect tree of size n should have m levels. The last insertion was at m*2 levels, so you need to sort.
Also, when you start sorting by directories, you will get sequential inserts, effectively forming a linked list instead of a tree, so you may need to take that into account.
At the moment 180455 items takes 0.094 seconds to sort on my 1.09Ghz Athlon. So I suppose worrying about this stuff is pointless.
2) I hate WCHAR, but thats just because Lua doesn't support them with SWIG at the moment, so not really an issue.
Now, for the implementation.
I added a Next and Prev pointer to ItemStruct, and filled them with the next file in the directory (So contiguous directories are a matter of starting at the Item that Prev=NULL and filling till Next=NULL)
Then I added the following items to Lua
#define NO 0
#define YES 1
#define MAXULONG64 18446744073709551615
#define RUNNING 0
#define STOPPING 1
#define STOPPED 2
void print( WCHAR *str);
void ShowDebug(int Level, struct ItemStruct *Item, char *Message);
struct ItemStruct *TreeSmallest(struct ItemStruct *Top);
struct ItemStruct *TreeBiggest(struct ItemStruct *Top);
struct ItemStruct *TreePrev(struct ItemStruct *Here);
struct ItemStruct *TreeNext(struct ItemStruct *Here);
int FindGap( struct DefragDataStruct *Data, ULONG64 MinimumLcn,ULONG64 MaximumLcn,ULONG64 MinimumSize,int MustFit,int FindHighestGap,unsigned long long *OUTPUT,unsigned long long *OUTPUT);
int young(struct ItemStruct *Item, ULONG64 time);
struct DefragDataStruct *Data,
struct ItemStruct *Item,
ULONG64 NewLcn, /* Where to move to. */
ULONG64 Offset, /* Number of first cluster to be moved. */
ULONG64 Size, /* Number of clusters to be moved. */
int IsFragmented(struct ItemStruct *Item, ULONG64 Offset, ULONG64 Size);
ULONG64 GetItemLcn(struct ItemStruct *Item);
struct ItemStruct *FindItemAtLcn(struct DefragDataStruct *Data, ULONG64 Lcn);
void TreeSort(struct DefragDataStruct *Data);
void OptimizeFreeSpace(struct DefragDataStruct *Data);
void OptimizeMFTzone(struct DefragDataStruct *Data);
void OptimizeDirectories(struct DefragDataStruct *Data);
void Defragment(struct DefragDataStruct *Data);
void FastFillOptimize(struct DefragDataStruct *Data);
void OptimizeVolume(struct DefragDataStruct *Data, int Mode);
void OptimizeUp(struct DefragDataStruct *Data); /*Mode = 3 is full optimise */
I'll post up some example code for it soon. If you can think of anything else that is needed tell me.
This is some example code
p = data.ItemTree; --p is the Tree root
q=defrag.TreeSmallest(p); --q is first item
a,b,e = defrag.FindGap(data, 0, 0, q.Clusters, 0, 0); --a is return (0 = NO, 1 = YES), b is gap start, e is gap end
x = os.clock()
print(string.format("Elapsed time: %.9f\n", os.clock() - x));
Needs a script.lua
Call it as LuaDefrag C:
It runs analyze automatically (Cause it's faster in C), then passes Data to script and runs. All this from DefragOnePath. So if you call it with no arguments, it analyzes and runs script on each drive.[/url]
This example prints each directory and it's contents in order. (Contents in order, directories not)
p = data.ItemTree;
while q ~= nil do
if string.byte(q.Directory) == defrag.YES then
r = q.Next
while r ~= nil do
r = r.Next;
q = defrag.TreeNext(q);