Εργασία ΥΣΒΔ άσκηση 1 και 2 Από Φράγκο Κωνσταντίνο sdi2000207 και Τουρνη Ιωαννη sdi2000192 Για την δημιουργία του εκτελέσιμου το οποίο δείχνει τις δυνατότητες της βιβλιοθήκης BF, τρέξτε την εντολή: make bf; Για να τρέξετε το εκτελέσιμο: ./build/bf_main Αντίστοιχα και για τα άλλα εκτελέσιμα. make ht; make hp; Για την δημιουργία των εκτελέσιμων hp , ht , sht αρχείων τρέχουμε την εντολή make hp, make ht, make sht αντίστοιχα, σιγουρευόμενοι πως δεν υπάρχουν ήδη τα αρχεία data.db, index.db. Για την διαγραφή των αρχείων αυτών τρέχουμε την εντολή make clean Για την εκτέλεση των εκτελέσιμων αρχείων hp, ht, sht τρέχουμε αντίστοιχα την εντολές /build/hp_main /build/ht_main /build/sht_main Το αρχείο hp_file υλοποιεί τις συναρτήσεις που υπάρχουν στην hp_file.h. Για την υλοποίση αυτή χρησιμοποιούμε την δομή hp_info που αποθηκεύουμε στο πρώτο μπλοκ του αρχείου, ενώ και την δομή hp_block_info που αποθηκεύεται στο τέλος κάθε μπλοκ εγγραφών. Για την υλοποίση, ουσιαστικά προσθέτουμε μία εγγραφή μετά την τελευταία που προσθέσαμε. Αν χοράει στο ίδιο μπλοκ την προσθέτουμε εκεί, αλλιώς δημιουργούμε ένα καινούριο και την προσθέτουμε εκεί. Η αναζήτηση γίνεται σειριακά σε όλο το αρχείο των μπλοκς, από το πρώτο μέχρι το τελευταίο μπλοκ. Το αρχείο ht_file υλοποιεί τις συναρτήσεις που υπάρχουν στην hp_file.h. Χρησιμοποιούμε τις αντίστοιχες δομές που χρησιμοποιήσαμε και στο hp_file απλά με διαφορετικά περιεχόμενα. Στην ht_info έχουμε έναν πίνακα μεγέθους num_of_buckets, με την τιμή κάθε bucket ουσιαστικά να είναι το πρώτο μπλοκ που δείχνει. Και άλλον ένα ίδιο πίνακα με την διαφορά ότι αυτή τη φορά δείχνει στο τελευταίο μπλοκ που έγινε εισαγωγή. Αν ένα μπλοκ γεμίσει, τότε δημιουργούμε ένα καινούριο μπλοκ υπερχείλισης, με το προηγούμενο μπλοκ να έχει ένα αναγνωριστικό, για το καινούριο. Έτσι μπορούμε τα μπλοκς του bucket, να τα διατρέξουμε γραμμικά σαν λίστα. Για την εισαγωγή, χασάρουμε τον id με χρήση mod num_of_buckets, και τοποθετούμε την καινούρια εγγραφή στο τέλος της λίστας των μπλοκ του bucket. Η αναζήτηση, αυτή τη φορά δε θα χρειαστεί να γίνει σε όλες τις εγγραφές, παρά μόνο σε αυτές που το hash_value, είναι ίδιο με το hash_value που αναζητούμε. Το αρχείο sht_file υλοποιεί τις συναρτήσεις που υπάρχουν στην shp_file.h.Χρησιμοποιούμε τις αντίστοιχες δομές που χρησιμοποιήσαμε και στο hp_file απλά με διαφορετικά περιεχόμενα και μία καινούρια δομή tuple, ουσιαστικά ένα ζευγάρι από όνομα και αναγνωριστικό μπλοκ. Ουσιαστικά, για κάθε ινσερτ σε ht_file που γίνεται, στο ευρετίριο γίνεται insert το όνομα της εγγραφής που έγινε ινσερτ αλλά και το αναγνωριστικό μπλοκ στο αρχείο ht. Το insert, γίνεται με ίδιο τρόπο όπως στο ht, απλά χασάροντας το όνομα αυτή τη φορά. Η αναζήτηση γίνεται όπως το ht με βάση το name, και μετά για ότι εγγραφή βρίσκουμε με αυτό το name, ψάχνουμε στο αρχείο ht απεθυείας, στο μπλοκ που είναι αποθηκευμένη. Έχουμε και δύο συναρτήσεις έκδοσης στατιστικών για το αρχείο, μία για κάθε τύπο αρχείου κατακερματισμού (ht,sht), από τις οποίες αντλούμε τα στατιστικά τα οποία ζητάει η εκφώνηση, καθώς και το πλήθος εγγραφών του αρχείου.