Assignment 3: ADTs: Πίνακας Συμβόλων (Symbol Table)
Ο σκοπός αυτής της άσκησης είναι να σας βοηθήσει να κάνετε επανάληψη/μάθετε (1) τη χρήση arrays και pointers στη γλώσσα προγραμματισμού C, (2) πως να δημιουργείτε modules χωρίς state στη C, και (3) τη χρήσης των εργαλείων προγραμματισμού GNU/UNIX, ειδικά gcc, shell, και editing (emacs).
Ένας symbol table είναι μια συλλογή από ζεύγη δεσμεύσεων (bindings). Ένα ζεύγος δέσμευσης αποτελείται από ένα κλειδί (key) και μία τιμή (value). Το κλειδί είναι ένα string που χαρακτηρίζει με μοναδικό τρόπο το αντίστοιχο ζεύγος δέσμευσης (binding). Η τιμή είναι δεδομένα που κατά κάποιο τρόπο αντιστοιχούν στο συγκεκριμένο κλειδί. Ο symbol table επιτρέπει στον χρήστη να εισάγει (put) ένα νέα bindings, να διαβάσει (get) τις τιμές των bindings με βάση τα κλειδιά, και να σβήσει (remove) bindings με βάση τα κλειδιά. Οι symbol tables χρησιμοποιούνται συχνά σε συστήματα προγραμματισμού, όπως compilers, assemblers, και λειτουργικά συστήματα.
Υπάρχουν διάφοροι τρόποι να υλοποιηθεί ένας symbol table. Ένας απλός τρόπος είναι να αποθηκεύσουμε τα bindings σε μία διασυνδεδεμένη λίστα (linked list). Διασυνδεδεμένες λίστες περιγράφονται σε διάφορες αναφορές, π.χ. στο Section 17.5 του C Programming: A Modern Approach (King). Μια πιο αποτελεσματική υλοποίηση ενός symbol table, μπορεί να χρησιμοποιήσει έναν hash table. Οι hash tables περιγράφονται επίσης σε πολλές αναφορές, όπως στο Section 2.9 του The Practice of Programming.
Η άσκηση σας ζητάει να δημιουργήσετε έναν abstract data type (ADT) που ονομάζεται SymTable. Κάθε αντίγραφο (instance) του SymTable ADT θα είναι έναs symbol table. Πρέπει να σχεδιάσετε τον SymTable ADT ώστε να είναι «γενικός», δηλαδή οι τιμές (values) να είναι void pointers, και επομένως να μπορούν να δείξουν σε δεδομένα οποιουδήποτε τύπου.
Θα δημιουργήσετε δύο υλοποιήσεις του SymTable ADT: μία υλοποίηση που χρησιμοποιεί μια διασυνδεδεμένη λίστα και μια που χρησιμοποιεί ένα hash table.
Ο SymTable ADT που θα δημιουργήσετε θα σας χρησιμεύσει και αργότερα.
SymTable_T SymTable_new(void);
void SymTable_free(SymTable_T oSymTable);
unsigned int SymTable_getLength(SymTable_T oSymTable);
int SymTable_put(SymTable_T oSymTable, const char *pcKey, const void *pvValue);
int SymTable_remove(SymTable_T oSymTable, const char *pcKey);
int SymTable_contains(SymTable_T oSymTable, const char *pcKey);
void *SymTable_get(SymTable_T oSymTable, const char *pcKey);
void SymTable_map(SymTable_T oSymTable, void (*pfApply)(const char *pcKey, void *pvValue, void *pvExtra),const void *pvExtra);
Η υλοποίηση του SymTable με διασυνδεδεμένη λίστα (linked list) πρέπει:
Η υλοποίηση του SymTable με hash table πρέπει:
#define HASH_MULTIPLIER 65599
...
/* Return a hash code for pcKey. */
static unsigned int SymTable_hash(const char *pcKey)
{
size_t ui;
unsigned int uiHash = 0U;
for (ui = 0U; pcKey[ui] != '\0'; ui++)
uiHash = uiHash * HASH_MULTIPLIER + pcKey[ui];
return uiHash;
}
Φυσικά μπορείτε να χρησιμοποιήσετε και άλλες εναλλακτικές συναρτήσεις.
Ο SymTable μπορεί να κάνει expand. Δηλαδή, για λόγους αποτελεσματικότητας, η υλοποίησή σας μπορεί να αυξάνει τον αριθμό των buckets (και, αναγκαστικά να επανατοποθετεί όλα τα bindings) όποτε ο αριθμός των bindings γίνεται πολύ μεγάλος. Μπορείτε να χρησιμοποιείτε τα εξής μεγέθη για τον αριθμό των buckets σε κάθε βήμα: 509, 1021, 2053, 4093, 8191, 16381, 32771, και 65521. Όταν η συνάρτηση SymTable_put ανιχνεύει ότι με το νέο binding ξεπερνιούνται τα 509 bindings, τότε πρέπει να αυξάνει τον αριθμό των buckets σε 1021. Όταν η συνάρτηση ανιχνεύει ότι με το νέο binding ξεπερνιούνται τα 1021 bindings, τότε θα αυξάνει τον αριθμό των buckets σε 2053, κ.ο.κ. Όταν ο SymTable_put ανιχνεύει ότι με το νέο binding ξεπερνιούνται τα 65521 bindings, τότε δεν θα αυξάνει τον αριθμό των buckets. Οπότε το 65521 είναι ο μέγιστος αριθμός buckets που μπορεί να περιέχει ο SymTable. Θα έχετε καλύτερο βαθμό αν παραδώσετε μια έκδοση του hash table που δεν υποστηρίζει επέκταση αλλά δουλεύει σωστά, από το να παραδώσετε μια έκδοση του hash table που υποστηρίζει επέκταση αλλά δεν δουλεύει σωστά. Αν προσπαθήσετε να υλοποιήσετε την επέκταση και δεν την τελειώσετε, τότε αφαιρέστε τον κώδικα σας για την επέκταση και περιγράψτε στο readme αρχείο την προσπάθειά σας.
Δημιουργήστε ένα test πρόγραμμα testsymtab (testsymtab.c) που θα εκτελεί διάφορες πράξεις σε έναν ή περισσότερους symbol tables. Προσπαθήστε να καλύψετε όσο το δυνατόν περισσότερες περιπτώσεις στις δοκιμές σας.
Συμπληρώστε το Makefile που υπάρχει στο repo το οποίο θα πρέπει να περιέχει τουλάχιστον τα εξής targets:
make clean: πρέπει να σβήνει όλα τα αρχεία που παράγονται κατά την μετάφραση του προγράμματος και να αφήνει μόνο τα header και source αρχεία του προγράμματος σας.
make list: πρέπει να κάνει build το executable testsymtab χρησιμοποιώντας την υλοποίηση του SymTable με την χρήση της linked list.
make hash: πρέπει να κάνει build το executable testsymtab χρησιμοποιώντας την υλοποίηση του SymTable με την χρήση του hash table.
Κάντε fork το repository assignment3 από την ομάδα του μαθήματος στο csd gitlab. Στη συνέχεια αλλάξτε τα permissions σε private όπως αναγράφει στα εδώ. Προσθέστε ως members στο repo σας τους TAs του μαθήματος.
Γράψτε το πρόγραμμα σας στα συστήματα x86 του CSD χρησιμοποιώντας τα εργαλεία gcc, vim, emacs, gdb. Επεξεργαστείτε τα αρχεία (symtable.h, symtablelist.c, symtablehash.c, testsymtab.c, Makefile) που βρίσκονται κάτω από το φάκελο src συμπληρώνοντας τον κώδικά σας μέσα. Περιορίστε το μέγεθος των γραμμών (πλάτος) στο αρχείο σας σε 78 ή 80 χαρακτήρες. Αυτό σας επιτρέπει να τυπώνετε σε δύο στήλες σε χαρτί και να έχετε ταυτόχρονα ανοιχτά παράθυρα για editing και compilation και execution.
Για κάθε ζητούμενη function όπως περιγράφεται πιο πάνω που υλοποιείτε μπορεί και θα πρέπει να είναι ένα ξεχωριστό commit στο git repository σας.
Χρησιμοποιήστε τον gcc με τις command line παραμέτρους “-Wall, -ansi, -pedantic” για να κάνετε preprocess, compile, assemble, και link το πρόγραμμά σας.
Προσθέστε στο README.md text file :
H παράδοση της άσκησής σας θα γίνει μέσω git, σύμφωνα με τις οδηγίες που περιγράφονται εδώ. Συγκεκριμένα το repository σας στο gitlab θα πρέπει να είναι fork του repository assignment3 και θα πρέπει να προσθέσετε ως members τους TAs του μαθήματος. Σιγουρευτείτε ότι ο κώδικάς σας έχει γίνει σωστά commit και ότι φαίνονται στο online repository στo account σας στο csd-gitlab.
Προσοχή! Mην κάνετε commit object και executables αρχεία.
Επειδή η εξέταση θα γίνει στα μηχανήματα του Τμήματος θα πρέπει να κάνετε clone το repository στα μηχανήματα του Τμήματος και να κάνετε compile και run τις ασκήσεις σας σε αυτά τα συστήματα. Αυτή είναι η ίδια διαδικασία που θα ακολουθηθεί την ημέρα της εξέτασης.
Στην προθεσμία της παράδοσης ένα script θα τρέξει και θα κατεβάσει όλα τα repositories που έχουν γίνει fork. Αυτά είναι τα repositories που θα βαθμολογηθούν.
Η βαθμολογία θα βασιστεί και στην ορθότητα αλλά και στο σχεδιασμό, όπως αναφέρεται στη σελίδα Policies του μαθήματος. Η κατανόηση της άσκησης αλλά και η αναγνωσιμότητα ενός προγράμματος είναι σημαντικό μέρος του σχεδιασμού.
___________________________________________________________________________________________________________________________________
Last Modified: 12-Feb-2021 08:23