1 files changed, 282 insertions, 0 deletions
diff --git a/src/slices.c b/src/slices.c
new file mode 100644
index 0000000..e8f1d49
--- /dev/null
+++ b/src/slices.c
@@ -0,0 +1,282 @@
+#include "slices.h"
+
+#include <string.h>
+#include <stdio.h> /* For perror() */
+
+#define MIN(a, b)  (((a) < (b)) ? (a) : (b))
+#define MAX(a, b)  (((a) > (b)) ? (a) : (b))
+
+slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t *next) {
+	slice_t *s;
+
+	s = malloc(1*sizeof(slice_t));
+	if (s!=NULL) {
+		s->begin=begin;
+		s->end=end;
+		s->status=status;
+		s->next=next;
+	}	
+
+	return s;
+}
+
+void sliceDelete(slice_t *s) {
+	free(s);
+}
+
+// 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.
+	*/
+	pthread_mutex_lock(&(slices->writeOrConsistentReadMutex));
+
+	if ( splitAt < initialSlice->begin || splitAt > initialSlice->end ) {
+		pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+		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 ) {
+			pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+			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 ) {
+			pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+			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
+	}
+
+	pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+	return 1 + (splitBeforeSingularity?1:0) + (splitAfterSingularity?1:0);
+}
+
+void sliceDumpUpdate(char *dump, slice_t *s, address_t blockSize, unsigned int charCount, address_t begin, address_t end) {
+	address_t sb,se,i;
+	char ci;
+
+	// If "s" slice is (partially) contained/visible in the [begin,end] display interval
+	if ( !(s->end < begin) && !(s->begin > end) ) {
+		// Draw the slice on the right number of characters
+		// Mathematically correct, but crashes because address_t is UNSIGNED
+		// sb=MAX(0, (s->begin - begin) / *blockSize);
+		sb=(s->begin < begin)?0:(s->begin - begin) / blockSize;
+		se=MIN((s->end - begin) / blockSize, charCount-1);
+
+		/* Debug "assertion"
+		if (sb >= charCount || se >= charCount) {
+			printf("BUG : sb==%lli, se=%lli, charCount==%i\n", sb, se, charCount);
+			printf("BUG : MAX(0, (%lli - %lli) / %lli)", s->begin, begin, blockSize);
+			exit(42);
+		}*/
+		
+		// Choose from the sent slice status the right char to draw
+		switch (s->status) {
+			case S_UNKNOWN:		ci='_'; break;
+			case S_UNREADABLE:	ci='!'; break;
+			case S_RECOVERED:	ci='.'; break;
+			default:		ci='~'; break;
+		}
+
+		// Draw on the right number of characters, paying attention with information collision
+		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]='#';
+			}
+		}
+	}
+}
+
+slices_t *slicesNewEmpty() {
+	int res;
+	slices_t *ss = malloc(1*sizeof(slices_t));
+
+	if (ss==NULL) {
+		return NULL;
+	}
+
+	memset(ss, 0, sizeof(slices_t));
+	res=pthread_mutex_init(&(ss->writeOrConsistentReadMutex), NULL);
+	if (res!=0) {
+		free(ss);
+		return NULL;
+	}
+
+	return ss;
+}
+
+slices_t *slicesNewSingleton(address_t begin, address_t end, sliceStatus_t status) {
+	slice_t *s=NULL;
+	slices_t *ss = slicesNewEmpty();
+	if (ss==NULL) {
+		return NULL;
+	}
+	s=sliceNew(begin,end,status,NULL);
+	if (s==NULL) {
+		free(ss);
+		return NULL;
+	}
+	slicesAppend(ss,s);
+
+	return ss;
+}
+
+void slicesDelete(slices_t *ss) {
+	slice_t *curr, *toFree;
+
+	curr=ss->first;
+	while (curr!=NULL) {
+		toFree=curr;
+		curr=curr->next;
+		sliceDelete(toFree);
+	}
+	free(ss);
+}
+
+void slicesAppend(slices_t *slices, slice_t *slice) {
+	pthread_mutex_lock(&(slices->writeOrConsistentReadMutex));
+
+	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)++;
+
+	pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+}
+
+slice_t *slicesFindLargest(slices_t *slices, sliceStatus_t status) {
+	slice_t *curr, *sMax = NULL;
+	address_t i, iMax = 0;
+	
+	pthread_mutex_lock(&(slices->writeOrConsistentReadMutex));
+
+	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;
+	}
+
+	pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+	return sMax;
+}
+
+slice_t *slicesFindLargestFast(slices_t *slices, address_t *foundMax, sliceStatus_t status, address_t knownMax, slice_t *firstToTry) {
+	slice_t *curr, *sMax = NULL;
+	address_t i, iMax = 0;
+	
+//FIXME : pthread_lock à faire avant l'appel là :-s (car argument firstToTry peut pointer vers n'importe quoi si autre thread modifie
+	curr = firstToTry;
+	while (curr != NULL) {
+		i=curr->end - curr->begin + 1;
+		if ( curr->status == status ) {
+			if ( knownMax == i ) { *foundMax=i; return curr; }
+			if ( i > iMax ) {
+				iMax = i;
+				sMax = curr;
+			}
+		}
+		curr=curr->next;
+	}
+	curr = slices->first;
+	while (curr != firstToTry) {
+		i=curr->end - curr->begin + 1;
+		if ( curr->status == status && i > iMax ) {
+			iMax = i;
+			sMax = curr;
+		}
+		curr=curr->next;
+	}
+	*foundMax=iMax;
+	return sMax;
+}
+
+char *slicesDump(slices_t *slices, address_t *blockSize, unsigned int charCount, address_t begin, address_t end) {
+	int res;
+	slice_t *curr;
+	char *dump;
+
+	res=pthread_mutex_lock(&(slices->writeOrConsistentReadMutex));
+	if (res!=0) {
+		//FIXME Trashy code
+		perror("slicesDump, pb lock mutex");
+		exit(42);
+	}
+
+	// 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;
+
+	//For each slice write in dump ASCII representation
+	curr = slices->first;
+	while (curr != NULL) {
+		sliceDumpUpdate(dump, curr, *blockSize, charCount, begin, end);
+		curr=curr->next;
+	}
+
+	pthread_mutex_unlock(&(slices->writeOrConsistentReadMutex));
+	return dump;
+}
+