Fonctions des slices terminées, module recovery qui contient l'algo de récupération terminé aussi.

Main minimaliste pour lancer des tests à droite à gauche.
Mises au points à coup de valgrind et ddd, ça a l'air presque bien, il reste peut être un bug ou deux dans des cas à la con.

La fonction slicesFindLargest est coûteuse. On peut imaginer une version qui prends en argument :
- le max potentiellement trouvable (permet d'éliminer plein de parcours dans la majorité des cas vue l'utilisation qui est faite des slices dans le recovery. La fonction retournerai le premier slice qui correspond à cette valeur de maximum.
- un pointeur vers le slice à partir duquel commencer la recherche, qui serait le pointeur du slice trouvé la précédente fois. Permet dans le cas général de trouver vite. Il faut quand même reprendre la liste au début jusqu'à ce pointeur si on arrive à la fin de la liste sans avoir trouvé.



git-svn-id: file:///var/svn/2011-ddhardrescue/trunk@3 d3078510-dda0-49f1-841c-895ef4b7ec81

1 files changed, 118 insertions, 10 deletions

diff --git a/src/slices.c b/src/slices.c
index edae571..8e9aee6 100755
--- a/src/slices.c
+++ b/src/slices.c
@@ -1,8 +1,12 @@
 #include <string.h>
 #include "slices.h"
 
+int min(int a, int b) { return (a<b)?a:b; }
+
 slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t *next) {
-	slice_t *s = malloc(1*sizeof(slice_t));
+	slice_t *s;
+
+	s = malloc(1*sizeof(slice_t));
 	if (s!=NULL) {
 		s->begin=begin;
 		s->end=end;
@@ -13,8 +17,62 @@ slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t
 	return s;
 }
 
-int sliceSplit(slice_t *slice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter) {
-	return 1;
+// Return the numbers of slices after split (3 in the general case, 2 or 1 in particular cases. -1 is memory error)
+int sliceSplit(slices_t *slices, slice_t *initialSlice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter) {
+	slice_t *secondSlice, *thirdSlice, *rightSlice;
+	int splitAfterSingularity, splitBeforeSingularity;
+
+	/* Basically, we want to split the slice in 3 :
+	[a;b] shoud be transformed in : [a;splitAt-1], [splitAt;splitAt], [splitAt+1;b]
+	There is exceptions and singularities :
+	* If splitAt is not within [a;b], bail out, no coherent solution
+	* If splitAt==a, the first slice should not exists
+	* If splitAt==b, the last slice shoud not exists
+	* If a==b (and so, ==splitAt), there is nothing to split, just change status
+	But, if statusBefore==statusAt, we don't want an interval [splitAt;splitAt], we want just split in 2.
+	This unwanted interval should be kept merged with the first interval.
+
+	For pratical reasons with pointer mess-up, the first action is to split between the second and the last slice
+	and then between he first and second if needed.
+	*/
+
+	if ( splitAt < initialSlice->begin || splitAt > initialSlice->end ) return 2;
+	
+	// Test before act because we'll change values of the initialSlice because
+	//  it would become the firstSlice or even the second one if the first is zero-lenght
+	splitAfterSingularity=(splitAt != initialSlice->end);
+	splitBeforeSingularity=(splitAt != initialSlice->begin) && (statusBefore != statusAt);
+
+	if ( splitAfterSingularity ) {
+		thirdSlice = sliceNew(splitAt+1, initialSlice->end, statusAfter, initialSlice->next);
+		if ( thirdSlice == NULL ) return -1;
+
+		initialSlice->end = splitAt;
+		// No status change because we'll split again in 2 parts or not
+		initialSlice->next = thirdSlice;
+		if ( initialSlice == slices->last ) slices->last = thirdSlice;
+		(slices->count)++;
+
+		rightSlice=thirdSlice;
+	} else {
+		rightSlice=initialSlice->next;
+	}
+
+	if ( splitBeforeSingularity ) {
+		secondSlice = sliceNew(splitAt, splitAt, statusAt, rightSlice);
+		if ( secondSlice == NULL ) return -1;
+		
+		initialSlice->end = splitAt-1;
+		initialSlice->status=statusBefore;
+		initialSlice->next = secondSlice;
+		if ( initialSlice == slices->last ) slices->last = secondSlice;
+		(slices->count)++;
+	} else {
+		initialSlice->status=statusAt; // Two cases : a==splitAt or statusAt==statusBefore
+	}
+
+	
+	return 1 + (splitBeforeSingularity?1:0) + (splitAfterSingularity?1:0);
 }
 
 slices_t *slicesNew() {
@@ -29,25 +87,75 @@ slices_t *slicesNew() {
 }
 
 void slicesAppend(slices_t *slices, slice_t *slice) {
-
+	slice->next=NULL; //XXX Could be generalized
+	if (slices->first==NULL || slices->last==NULL) {
+		slices->first = slice;
+	} else {
+		slices->last->next=slice;
+	}
+	slices->last=slice;
+	(slices->count)++;
 }
 
 slice_t *slicesFindLargest(slices_t *slices, sliceStatus_t status) {
-	return NULL;
+	slice_t *curr, *sMax = NULL;
+	address_t i, iMax = 0;
+	
+	curr = slices->first;
+	while (curr != NULL) {
+		i=curr->end - curr->begin + 1;
+		if ( curr->status == status && i > iMax ) {
+			iMax = i;
+			sMax = curr;
+		}
+		curr=curr->next;
+	}
+	return sMax;
 }
 
-char *slicesDump(slices_t *slices, int charCount, address_t begin, address_t end) {
+char *slicesDump(slices_t *slices, address_t *blockSize, unsigned int charCount, address_t begin, address_t end) {
 	slice_t *curr = slices->first;
-	address_t sb,se, blockSize=(end-begin)/(charCount+1);
-	char *dump=malloc(1*charCount+1);
+	unsigned int sb,se,i;
+	char *dump, ci;
+
+	// If blockSize is 0, try to autodetect to display entire slice chain
+	if (*blockSize == 0) {
+		*blockSize=(end-begin+1)/(charCount+1);
+		// If we have a too big zoom factor, draw it at 1:1 scale
+		if (*blockSize==0) *blockSize=1;
+	}
+
+	dump = malloc(charCount+1);
+	if (dump==NULL) { return NULL; }
 	memset(dump, ' ', charCount);
+	dump[charCount]=0;
 
 	while (curr != NULL) {
-		sb=curr->begin;
-		// TODO : boucle pour dessiner les caractères correspondant selon le type de zone. Attention aux cas ou 1 caractère contient la frontière de plusieurs zones (ne pas toujours écraser avec la dernière valeur)
+		sb=curr->begin / *blockSize; //FIXME : gérer le max également !
+		se=min(curr->end / *blockSize,charCount-1);
+
+		switch (curr->status) {
+			case S_UNKNOWN:		ci='_'; break;
+			case S_UNREADABLE:	ci='!'; break;
+			case S_RECOVERED:	ci='.'; break;
+			default:		ci='~'; break;
+		}
+
+		for (i=sb;i<=se;i++) {
+			if (dump[i] == ' ' ) {
+				// This is a new information
+				dump[i]=ci;
+			} else if ( dump[i] == ci || dump[i] == '!' ) {
+				// Already the right information or error, don't modify
+			} else {
+				// Multiple information on the same character
+				dump[i]='#';
+			}
+		}
 
 		curr=curr->next;
 	}
 
 	return dump;
 }
+