ProvaPratica 2013.09.13
Jump to navigation
Jump to search
Esercizio 1 e 2
Soluzione di Edu San
/***********************************************************************
* Prova Pratica di Laboratorio di Sistemi Operativi *
* 13 settembre 2013 *
* Esercizio 1+2 *
* *
* URL: http://www.cs.unibo.it/~renzo/so/pratiche/2013.09.13.pdf *
* Autore: Eduardo Santarelli *
************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <dirent.h>
#include <unistd.h>
/* An entry in the hash table. */
typedef struct fileEntry{
const char *filename;
struct fileEntry *next;
} fileEntry;
/* Global variables */
fileEntry **table = NULL;
int table_size;
/* Hash function. Calculates XOR of 8-bytes blocks *
* (actually, sizeof(long int)) read from the input file */
unsigned int hash(const char *fname){
FILE *f;
unsigned long int hash_val = 0;
unsigned long int tmp = 0;
f = fopen(fname, "r");
fread(&hash_val, sizeof(unsigned long int), 1, f);
while((fread(&tmp, sizeof(unsigned long int), 1, f) == 1))
hash_val = hash_val^tmp;
fclose(f);
return hash_val;
}
/* Creates a table of struct fileEntry elements, based on the hash values of the files *
* detected by scandir. If a collision is detected, the new entry is pointed by the *
* 'next' field of the current last element*/
void populate_table(struct dirent *dir_list[], int n){
int i;
table_size = 2*n;
table = (fileEntry**)calloc(table_size, sizeof(fileEntry));
if(!table) abort();
for(i=0; i<n; i++){
unsigned int index;
fileEntry *entry = NULL;
entry = (fileEntry*)malloc(sizeof(fileEntry));
if(!entry) abort();
index = hash(dir_list[i]->d_name)%table_size;
if(table[index] == NULL){
entry->filename = dir_list[i]->d_name;
entry->next = NULL;
table[index] = entry;
}
else{
entry->filename = dir_list[i]->d_name;
entry->next = table[index];
table[index] = entry;
}
}
}
/* Compares two files */
int fcompare(const char *f1, const char *f2){
FILE *f, *g;
int file1, file2;
f = fopen(f1, "r");
g = fopen(f2, "r");
while(fread(&file1, sizeof(int), 1, f) && fread(&file2, sizeof(int), 1, g)){
if(file1!=file2){
fclose(f);
fclose(g);
return 0;
}
}
fclose(f);
fclose(g);
return 1;
}
/* This function scans the file table. If an entry contains more than one file, *
* it compares all them. If a duplicate is found, the first file is removed, *
* and a hard link is created with the deleted file's name, pointing to the *
* second, identical, file. */
void deduplicate(){
int i;
for(i=0; i<table_size; i++){
while(table[i] != NULL && table[i]->next != NULL){
fileEntry *file1, *file2;
file1 = table[i];
file2 = table[i]->next;
while(file2 != NULL){
if(fcompare(file1->filename, file2->filename)){
unlink(file1->filename);
link(file2->filename, file1->filename);
printf("%s -> %s\n", file1->filename, file2->filename);
break;
}
file2 = file2->next;
}
table[i] = table[i]->next;
}
}
}
/*selector function for scandir() */
int exclude(const struct dirent *dir){
if(dir->d_type != DT_REG)
return 0;
else
return 1;
}
int main(int argc, char *argv[]){
struct dirent **entries = NULL;
int num_files;
num_files = scandir(".", &entries, exclude, alphasort);
populate_table(entries, num_files);
deduplicate();
return EXIT_SUCCESS;
}
Soluzione di Maldus (ora con tabella hash!)
#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <fcntl.h>
#include <stdlib.h>
#define SIZE 1024
char BUFF1[SIZE] ; /*buffer usati per leggere i file*/
char BUFF2[SIZE] ;
struct list{ /*struttura che uso per implementare la lista di file che hanno uguale somma crittografica*/
struct dirent* ent ;
struct list *next ;
struct list *prev ;
};
inline void del(struct list* p){ /*rimuove p dalla lista in cui si trova*/
(p->next)->prev = p->prev ;
(p->prev)->next = p->next ;
free(p) ;
}
int critsum( int f ){ /*somma crittografica per la tabella hash*/
int i , n ;
int x = 0 ;
while(( n = read( f , BUFF1 , SIZE ) )> 0 ){
for( i = 0 ; i < n ; i++ ){
x += ((int) BUFF1[i])*((i%8)+1) ; /*aggiungo ogni volta il valore numerico corrispondente al byte letto moltiplicato per un numero da 1 a 8*/
}
}
if( x < 0) return -x ;/*restituisco sempre un valore positivo, perchè possa essere usato come indice di un vettore*/
else return x ;
}
int buffcmp( char* buf1 , char* buf2 , int s1 , int s2 ){/*funzione che compara due buffer*/
int i ;
if( s1 != s2 ) return 1 ; /*se hanno lunghezza diversa sono diversi*/
for( i = 0 ; i < s1 ; i++ ){
if( buf1[i] != buf2[i] ) return 1 ;
}
return 0 ;
}
int filecmp( int f1 , int f2 ){ /*funzione ausiliaria che confronta due file. Si comporta come strcmp*/
int n1 , n2 ;
while(( n1 = read( f1 , BUFF1 , SIZE ) )> 0 ){ /*ho provato a inserire entrambe le read nel controllo del while con un &&; mi creava dei problemi, come se la seconda read venisse eseguita nel giro seguente del ciclo*/
n2 = read( f2 , BUFF2 , SIZE ) ;
if( buffcmp( BUFF1 , BUFF2 , n1 , n2 ) != 0 ) return 1 ; /*ritorna 1 se i due file sono diversi*/
}
return 0 ; /*ritorna 0 se sono uguali*/
}
void del_clones( struct list* p ){ /*cerca nella lista il cui primo elemento è p tutti i file con lo stesso contenuto*/
struct list *aux1 , *aux2 , *tmp;
int fd1, fd2 ;
struct stat s1 , s2 ;
aux1 = p ;
aux2 = aux1->next ;
while( aux1->next != p ){
printf( "%s:\n" , (aux1->ent)->d_name ) ;
if( stat( (aux1->ent)->d_name , &s1 ) != 0 ){
perror("stat") ;
exit(1) ;
}
if ( (fd1 = open((aux1->ent)->d_name, O_RDONLY ) ) == -1){ /*apro la entry*/
perror("open") ;
exit(1) ;
}
while( (aux2->next) != p && (aux2 != p) ){
tmp = aux2->next ;
if( stat( (aux2->ent)->d_name , &s2 ) != 0 ){
perror("stat") ;
exit(1) ;
}
if ( (fd2 = open((aux2->ent)->d_name, O_RDONLY ) ) == -1){ /*apro la entry*/
perror("open") ;
exit(1) ;
}
printf("\t%s" , (aux2->ent)->d_name) ;
if( s1.st_ino != s2.st_ino){
if( filecmp( fd1 , fd2 ) == 0 ){ /*controllo se i due file hanno lo stesso contenuto*/
printf("<-uguale\t") ;
unlink((aux2->ent)->d_name) ; /*rimuovo il file uguale*/
if( link( (aux1->ent)->d_name , (aux2->ent)->d_name) == -1 ){ /*creo un link fisico*/
perror("link") ;
exit(1) ;
}
del(aux2) ;
}
}
else del(aux2) ; /*se hanno lo stesso i-node toglili dalla lista*/
aux2 = tmp; /*tmp = aux2->next. Lo salvo in precedenza nel caso in cui aux2 sia stato cancellato*/
close(fd2) ;
}
printf("\n") ;
close(fd1) ;
aux1 = aux1->next ;
}
}
int main( int argc, char* argv[]){
struct stat s1 , s2; /*struttura di informazioni su un file*/
DIR *dir ; /*puntatore a directory*/
struct dirent *entry ; /*struttura di informazioni sulle entry di una directory*/
int fd1; /*descrittore di file*/
char *name ;
int n = 0 ; /*contatore di file all'interno della directory*/
int cs , i ; /*cs è somma crittografica del file*/
struct list *hash ;
struct list *tmp ;
if( stat( argv[1] , &s1 ) != 0 ){
perror("stat") ;
return 1 ;
}
if( !S_ISDIR(s1.st_mode) ){
printf( "argument is not a valid directory\n" ) ;
return 0 ;
}
if( (dir = opendir( argv[1] )) == NULL ){
perror("opendir") ;
return 1 ;
}
if( chdir( argv[1] ) == -1 ){ /*sposto la directory corrente in quella di esecuzione per poter aprire i file*/
perror("chdir") ;
return 1 ;
}
while( (entry = readdir(dir) ) != NULL){ /*conto i file contenuti nella directory*/
stat( entry->d_name , &s1 ) ;
if( S_ISREG(s1.st_mode) ) n++ ; /*se si tratta di un file normale contalo*/
}
printf("La directory contiene %i file\n" , n ) ;
n = 2*n ; /*da questo momento n è il numero di indici nella mia hashtable*/
hash = (struct list*) malloc( sizeof(struct list)*n) ; /*alloco una hash table con n = 2n indici*/
rewinddir(dir) ;
for( i = 0 ; i < n ; i++ ){ /*inizializzo le liste*/
hash[i].next = &hash[i] ;
hash[i].prev = &hash[i] ;
hash[i].ent = NULL ;
}
while( (entry = readdir(dir) ) != NULL){ /*con questo ciclo riempo la hashtable*/
stat( entry->d_name , &s1 ) ;
if( S_ISREG(s1.st_mode) ){ /*se si tratta di un file normale consideralo*/
if ( (fd1 = open(entry->d_name, O_RDONLY ) ) == -1){ /*apro la entry*/
perror("open") ;
exit(1) ;
}
cs = critsum( fd1 ) ;
tmp = (struct list*) malloc( sizeof(struct list) ) ;
tmp->ent = entry ;
(hash[cs%n].next)->prev = tmp ; /*inserisco il file in testa alla lista di indice cs%n*/
tmp->prev = &hash[cs%n] ;
tmp->next = hash[cs%n].next ;
hash[cs%n].next = tmp ;
close(fd1) ;
}
}
for( i = 0 ; i < n ; i++ ){ /*con questo ciclo cancello effettivamente i file uguali*/
printf("%i: " , i ) ;
if( hash[i].next != &hash[i] ){
del_clones( hash[i].next ) ;
}
else printf("\n") ;
}
return 0 ;
}
Esercizio 3
Soluzione di Edu San
#!/usr/bin/env python3
# Prova Pratica di Laboratorio di Sistemi Operativi
# 13 settembre 2013
# Esercizio 3
#
# URL: http://www.cs.unibo.it/~renzo/so/pratiche/2013.09.13.pdf *
# Autore: Eduardo Santarelli
class LineCounter:
def __init__(self, fileList):
# A list containing the char-per-line
# count for the specified files.
# Value for line 1 is in result[0] and so on.
self.result = []
self.files = fileList # List of files to elaborate.
self.getLinesCount()
# Count the chars for each lines of specified file,
# add the result to the relevant field in self.result,
# if already present, append the value to the
# end of the list if not.
def countLines(self, file):
i = 0
fd = open(file)
for line in fd:
lineLength = len(line)
# If an entry for the current line does
# not exist, append the value to the end of the list
try:
self.result[i] += lineLength
except IndexError:
self.result.append(lineLength)
i = i+1
fd.close()
# Call self.countLines() for each file in self.files
# in order to build the self.result list
def getLinesCount(self):
for entry in self.files:
self.countLines(entry)
# Print the items in self.result, each preceded by the
# corresponding line number.
def printLines(self):
i = 1
for value in self.result:
print("{:d}: {:d}".format(i, value))
i = i+1
import os
lc = LineCounter(os.listdir(os.getcwd()))
lc.printLines()
Soluzione di Pirata
#Esercizio 3: Script bash o Python: (10 punti):
#Sia data una directory che contiene file di testo.
#Scopo dell'esercizio e' di contare i caratteri delle corrispondenti righe di testo di tutti i file della directory, si vuole cioe' sapere
#il numero totale di caratteri presenti nelle prime righe di tutti i file, nelle seconde linee, ecc.
#$ ccpl mydir
#1 234
#2 21
#3 333
# .....
#l'ouput significa che se contiamo tutti i caratteri contenuti nella prima riga di tutti i file in mydir otteniamo 234 (mydir/file1
#puo' avere 40 caratteri nella prima riga, mydir/file2 ne puo' avere 20, ecc... procedendo per tutti i file di mydir la somma fa 234)
#! bin/bash
nline=1
touch fileresult
paste $1/* > fileresult #merges every file's line from the directory passed to the file fileresult
while read line; do
count=$(echo $line | wc -m) #counts the number of char in each line of fileresult
echo $nline $count
nline=$(($nline + 1))
done < fileresult
rm fileresult
Soluzione di Maldus
#! /bin/bash
count=1 #conta il numero di riga che sto considerando
bool=1 #resta 1 finchè ci sono righe da contare in qualche file
if [[ -n $1 ]]; then
cd $1
else
exit 1
fi
file=`ls`
while [[ $bool -eq 1 ]]; do
tot=0
bool=0
for word in $file; do
if [[ (-r $word) && (-s $word) && ( -f $word) && (! $word = *~ ) ]]; then
x=`awk 'NR==c' c=$count $word | wc -m` #considero solo la riga contata da count
if [[ $x -ne 0 ]]; then #se la riga non è vuota
tot=`expr $tot + $x - 1` #con -1 tolgo il carattere \n che era stato contato da awk
bool=1 #bool=1 finchè c'è qualche riga da contare
fi
fi
done
if [[ $bool -eq 1 ]]; then
echo "$count: $tot"
fi
count=`expr $count + 1`
done
Soluzione di Davide Quadrelli
#!/bin/bash
if [[ -n $1 ]]; then
cd $1
files=`ls -p | grep -v /` #elenco file
else
echo"Inserire cartella come parametro"
exit
fi
array=()
#per ogni file nella cartella
for file in $files; do
i=0
while read line; do
#conto la lunghezza di ogni riga e la aggiungo nella corrispondente cella dell'array
len=`expr length "${line}"`
array[$i]=`expr ${array[$i]} + $len`
((i++))
done < $file
done
#a questo punto l'i-esima cella contiene la somma delle lunghezze della i-esima riga di ogni file
i=1
for n in ${array[@]}; do
echo "$i $n"
((i++))
done