From 0f2c685db3d3790ce9bdc9598df8dae7d6b67eae Mon Sep 17 00:00:00 2001 From: Ludovic Pouzenc Date: Sun, 9 Oct 2011 12:33:48 +0000 Subject: On range tout le code actuel du trunk dans une branche nommée "0.x" et on crée une branche 1.x qui contiendra une nouvelle mouture (re-conception, méta info de packaging...). MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit git-svn-id: file:///var/svn/2011-ddhardrescue/branches/0.x@29 d3078510-dda0-49f1-841c-895ef4b7ec81 --- src/slices.c | 282 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 282 insertions(+) create mode 100644 src/slices.c (limited to 'src/slices.c') 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 +#include /* 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; +} + -- cgit v1.2.3