migf1 Δημοσ. 21 Νοεμβρίου 2011 Μέλος Δημοσ. 21 Νοεμβρίου 2011 "Αν το φτιάξεις και το δεχτούνε τότε θα σου πω" μου λέει !!!!!!!!! Παίζει να είναι κι embedded, γιατί με storage media encryptions ασχολούνται (αλλά δεν ξέρω αν το θέλει για τη δουλειά του ή για άλλο σκοπό). EDIT: Πάντως και η ενσωμάτωση ΟΛΩΝ των primitive data types θέλει κι αυτή το χρόνο της... > typedef enum HstDataTid { HST_T_NOID = 0, HST_T_CHAR, HST_T_SCHAR, /* signed char */ HST_T_UCHAR, /* unsigned char */ HST_T_HINT, /* short int */ HST_T_UHINT, /* unisgned short int */ HST_T_0xUHINT, /* hexadecimal unisgned short int */ HST_T_0UHINT, /* octal unisgned short int */ HST_T_INT, HST_T_UINT, /* unsigned int */ HST_T_0xUINT, /* hexadecimal unsigned int */ HST_T_0UINT, /* octal unsigned int */ HST_T_LINT, /* long int */ HST_T_ULINT, /* unsigned long int */ HST_T_0xULINT, /* hexadecimal unsigned long int */ HST_T_0ULINT, /* octal unsigned long int */ HST_T_FLOAT, HST_T_DOUBLE, HST_T_LDOUBLE, /* long double */ HST_T_STRING, HST_T_CUSTOM, /* must always be last (not a type, just their total count ) */ HST_MAX_TYPES } HstDataTid; typedef struct HstDataT { HstDataTid typid; union { long double valldouble; char valchar; signed char valschar; unsigned char valuchar; short int valhint; unsigned short int valuhint; int valint; unsigned int valuint; long int vallint; unsigned long int valulint; float valfloat; double valdouble; } basic; void *pcustom; void (*func_print_custom_data)(void *); } HstDataT; /* array with string decriptions of supported data types */ enum TypDescColumns { HST_TDESC_LABCOL = 0, HST_TDESC_SPECOL, /* must always be last (not a col, just their total count ) */ HST_MAX_TDESC_COLS }; char *g_hst_tdesc[ HST_MAX_TYPES ][ HST_MAX_TDESC_COLS ] = { /* LABelCOL SPEcifierCOL */ {"long double", "%lg"}, {"char", "%c"}, {"signed char", "%c"}, {"unsigned char", "%c"}, {"short int", "%hd"}, {"unsigned short", "%hu"}, {"hex unsigned short", "%hx"}, {"oct unsigned short", "%ho"}, {"signed int", "%d"}, {"unsigned int", "%u"}, {"hex unsigned", "%x"}, {"oct unsigned", "%o"}, {"long int", "%ld"}, {"unsigned long", "%lu"}, {"hex unsigned long", "%lx"}, {"oct unsigned long", "%lo"}, {"float", "%f"}, {"double", "%g"}, {"char *", "%s"}, {"void *", "%p"} }; Καταλαβαίνεις τώρα φίλε DirectX γιατί από την αρχή σκέφτηκα να μπουν και στην push() τα type-specifiers, σιγά μην θυμούνται όλα αυτά τα enum !!!! (τα οποία btw πάνε για bitflags, αλλά είναι 19 τα άτιμα ... κρίμα που δεν χωράνε όλα σε 2 bytes )
migf1 Δημοσ. 22 Νοεμβρίου 2011 Μέλος Δημοσ. 22 Νοεμβρίου 2011 Καταλαβαίνεις τώρα φίλε DirectX γιατί από την αρχή σκέφτηκα να μπουν και στην push() τα type-specifiers, σιγά μην θυμούνται όλα αυτά τα enum !!!! (τα οποία btw πάνε για bitflags, αλλά είναι 19 τα άτιμα ... κρίμα που δεν χωράνε όλα σε 2 bytes ) Τελικά μάλλον εξυπηρετούν καλύτερα ως enum, για indexing σε πίνακα που περιέχει τα type-specifiers. Φαίνεται να καταλήγω στο παρακάτω, σιγά-σιγά... > push_basic( &stack, "%?", byval ); // όπου %? οποιοσδήποτε type-specifier της C, πλην των "%s" και "%p" push_custom( &stack, "%s", byref, αχρείαστο_size, αχρείαστη_user_func_print); push_custom( &stack, "%p", byref, size, user_func_print); if ( peek_basic( stack, "%?", byref) ) // όπου %? οποιοσδήποτε type-specifier της C, πλην του "%p" /* do something with *byref : (byval *) αν περαστεί "%s", το αποθηκευμένο string της στοίβας αντιγράφεται στο byref που σημαίνει πως το byref πρέπει να είναι ένα ήδη allocated string */ else if ( peek_custom( stack, "%p", &byref ) ) /* do something with *byref : (byval **) δηλαδή byref του byref μπορεί να περαστεί "%s" αντί για "%p", οπότε το αποθηκευμένο string της στοίβας αντιγράφεται ως δείκτης στον *byref */ print( stack); /* τυπώνει αυτόματα ότι έχει η κορυφή της στοίβας (είτε primitive είτε custom) */ * όπου αχρείαστο_* μπορεί να περαστεί ως 0 ή ως NULL, γιατί έτσι κι αλλιώς αγνοείται. Με την προσθήκη της stack_destroy() αυτό σκέφτομαι να είναι το interface που θα χρησιμοποιεί ο user, χωρίς να χρειάζεται να προετοιμάσει ή να γνωρίζει απολύτως τίποτε άλλο! Θα προστεθούν καμιά-δυο ακόμα βοηθητικές συναρτήσεις/macros, όπως π.χ. peek_size( stack ), print_all( stack )... and that's all! Βασικά ως "big picture" πρόκειται περί trade-off μεταξύ ταχύτητας εκτέλεσης και ευκολίας χρήσης. Με ή χωρίς πίνακες (ταχύτητα), αν δεν χρησιμοποιηθούν type-specifiers (ευκολία) ο user θα πρέπει να αποστηθίσει πολλά enums για να μπορέσει να χρησιμοποιήσει το interface. Ακόμα και να τα κρύψουμε τα enums (private) το πρόβλημα μετατίθεται στο να αποστηθίσει αντίστοιχο αριθμό συναρτήσεων, αφού θα πρέπει κάπως να αντικατασταθεί η public απόκρυψη των enums. Οπότε σε αυτό το σημείο πρέπει να παρθεί απόφαση αν θα χρησιμοποιηθούν ή όχι type-specifiers. Τα υιοθέτησα λοιπόν γιατί νομίζω πως η ευκολία που παρέχουν αξίζει κάποιες άλλες παραχωρήσεις. Το βρίσκω απλό, εύχρηστο και straight-forward, αναλογιζόμενοι το πόσο ανομοιογενή δεδομένα καλείται να διαχειριστεί. Ο user τα δικά του data ας τα προετοιμάσει και ας τα διαχειριστεί όπως θέλει. Θέλει να έχει δικά του αναγνωριστικά για τον κάθε user-defined τύπο του, ας το περιλάβει στο struct του κι ας το διαχειρίζεται όπως αγαπά. Θέλει ξεχωριστές user-defined ρουτίνες εκτύπωσης ανά τύπο, ας έχει (θα μας την περνάει ως τελευταία παράμετρο στην push_custom() ). Θέλει κι άλλες δικές του ρουτίνες διαχείρισης, ξεχωριστές ανά user-defined τύπο, ας τις περιλάβει ως δείκτες στο struct του κάθε user-defined τύπου. Γενικώς ας κάνει ότι θέλει με τους user-defined τύπους του, εμείς το μόνο που θέλουμε είναι να μας τον περάσει με push_custom( &stack, "%p", &data, size, print_func); Βέβαια σε επίπεδο υλοποίησης δεν είναι "ρόδινα" τα πράγματα, αφού πλέον με τα type-specifiers πρέπει να ξεσκιστώ στα... > if ( string_comparator( user_input_type_specifier, "%d" ) ... else if ( string_comparator( user_input_type_specifier, "%f") ... σε διάφορα μέρη του κώδικα, π.χ. στις push(), peek(), print(). Ανεξάρτητα από την υλοποίηση του string_comparator() πρέπει και σε αυτό το σημείο να παρθεί μια απόφαση, αυτή τη φορά με trade-off μεταξύ ταχύτητας (και πάλι) και ευκολία στη συγγραφή αλλά και στη συντήρηση του κώδικα (upgradability). Κατά κανόνα, οι γρήγοροι κώδικες είναι λιγότερο δεκτικοί σε συντήρηση/αναβάθμιση. Οπότε και πάλι για trade-off μιλάμε... ως συνήθως Πιστεύτε πως αξίζει να μπω σε περαιτέρω διαδικασίες για speed optimization; Έχω ένα int encoding για κάθε type-specifier που δεχόμαστε στην push() και το αποθηκεύω κωδικοποιημένο στον κάθε κόμβο. Όποτε όταν χρειάζομαι σύγκριση κάνω encode τον type-specifier που μου δίνει ο χρήστης και το αποτέλεσμα το συγκρίνω με τον encoded int που βρίσκεται αποθηκευμένος στον κόμβο (έχω αλλάξει το πεδίο από typid σε enctype). Το encoding είναι η αργή διαδικασία, γιατί σκανάρει τον πίνακα με τους type-specifiers (δείτε παρακάτω, στον κώδικα του spoiler) και αν βρει τον type-specifier τότε επιστρέφει έναν 3ψήφιο int. Σε αυτόν τον 3ψήφιο int τα 2 πρώτα στοιχεία αντιστοιχούν στο TYPE_ID enum του specifier (αντιστοιχεί σε γραμμή του πίνακα) και το τελευταίο ψηφίο αντιστοιχεί στη θέση που καταλαμβάνει το alias του TYPE_ID μέσα στη γραμμή του, στη 2η στήλη (από 0 έως 4, μιας και μέχρι 5 aliases προβλέπω για κάθε τύπο). Οπότε ο string_comparator() χρησιμοποιείται μέσα στην συνάρτηση που κάνει encoding, και αυτή τη στιγμή είναι hardcoded με 2 for-loops και !strncmp()... > #define HST_TDESC_ENCODE( tid, specalias ) ( (tid) * 10 + (specalias) ) #define HST_TDESC_DECODE_GET_TID( enctype ) ( (enctype) / 10 ) #define HST_TDESC_DECODE_GET_SPECALIAS( enctype ) ( (enctype) % 10 ) typedef struct TDesc { char label[ HST_TDESC_LABSIZE ]; char spec[HST_TDESC_SPECALIASES][ HST_TDESC_SPECSIZE ]; } TDesc; TDesc g_tdesc[ HST_TID_TOTAL ] = { /* LABelCOL SPECifiersCOL */ { "long double", {"%Lg", "%Lf", "%Le", "LE", "LG"} }, { "char", {"%c", "", "", "", ""} }, { "signed char", {"%c", "", "", "", ""} }, { "unsigned char", {"%c", "", "", "", ""} }, { "short int", {"%hd", "hi", "", "", ""} }, { "unsigned short", {"%hu", "", "", "", ""} }, { "hex unsigned short", {"%hx", "hX", "", "", ""} }, { "oct unsigned short", {"%ho", "", "", "", ""} }, { "signed int", {"%d", "%i", "", "", ""} }, { "unsigned int", {"%u", "", "", "", ""} }, { "hex unsigned", {"%x", "X", "", "", ""} }, { "oct unsigned", {"%o", "", "", "", ""} }, { "long int", {"%ld", "%li", "", "", ""} }, { "unsigned long", {"%lu", "", "", "", ""} }, { "hex unsigned long", {"%lx", "lX", "", "", ""} }, { "oct unsigned long", {"%lo", "", "", "", ""} }, { "float", {"%f", "%e", "", "", ""} }, { "double", {"%g", "%e", "%f", "E", "G"} }, { "char *", {"%s", "", "", "", ""} }, { "void *", {"%p", "", "", "", ""} } }; static int hst_tdesc_get_enctype( const char *spec ) { extern TDesc g_tdesc[ HST_TID_TOTAL ]; register int i,j; if ( !spec || !*spec ) return HST_TID_NOID; for (i=0; i < HST_TID_TOTAL; i++) for (j=0; g_tdesc[ i ].spec && g_tdesc[i].spec[0] && j < HST_TDESC_SPECALIASES; j++ ) if ( !strncmp(spec, g_tdesc[ i ].spec[ j ], HST_TDESC_SPECSIZE-1) ) goto ret; ret: return i == HST_TID_TOTAL ? HST_TID_NOID : HST_TDESC_ENCODE(i,j); } Οι 2 έξτρα έλεγχοι στη συνθήκη του nested for-loop είναι για να μην αναλώνεται σε περιττά strncmp()... αγνοεί όσα aliases βρίσκονται μετά από 1ο NULL ή κενό ("") alias, ανά γραμμή. Για μικρή επίσπευση, μπορούν να αντικατασταθούν με NULL όλα τα "" στον πίνακα, ώστε να αφαιρεθεί ο 2ο έξτρα έλεγχος (και να μείνει μόνο του NULL). Ο πίνακας είναι 20 γραμμές, με max 5 aliases ανά γραμμή, με το κάθε alias να είναι max 3+1 chars long. Δηλαδή στο χειρότερο σενάριο κάνει 1200 επαναλήψεις ανά encoding, ενώ κατά μέσο όρο (π.χ. με 2 γεμισμένα aliases ανά γραμμή) κάνει 500 επαναλήψεις. Στην πράξη κάνει πολύ λιγότερες, αφού είναι λιγότερα από 2 γεμισμένα aliases ανά γραμμή συν ότι παραπάνω από τα μισά aliases είναι 2+1 χαρακτήρες. Οπότε αναρωτιέμαι αν αξίζει τελικά τον κόπο να ασχοληθώ με speed optimization του encoding (και του string comparator). Δεν ρωτάω ρητορικά, πραγματικά αναρωτιέμαι και θα ήθελα τις απόψεις σας! Από την άλλη μεριά, η ανάποδη διαδικασία είναι ταχύτατη αφού η εύρεση του type-specifier που αντιστοιχεί σε ένα enctype είναι απλά θέμα ενός γρήγορου decoding (tid = enctype / 10, alias = enctype % 10) που δίνει τη γραμμή του πίνακα καθώς και τη θέση του alias, για άμεσο indexing. ΥΓ. Για όποιον ενδιαφέρεται, το παραπάνω απόσπασμα είναι από κουβέντα που έχω με τον φίλο bxenos σε άλλο φόρουμ, ο οποίος όχι μόνο έχει συμβάλει καθοριστικά σε πολλές από τις επιλογές που έχω κάνει, αλλά έχει προτείνει κιόλας και πολύ ενδιαφέρουσες εναλλακτικές υλοποιήσεις.
Directx Δημοσ. 22 Νοεμβρίου 2011 Δημοσ. 22 Νοεμβρίου 2011 [..]Οπότε αναρωτιέμαι αν αξίζει τελικά τον κόπο να ασχοληθώ με speed optimization του encoding (και του string comparator). Δεν ρωτάω ρητορικά, πραγματικά αναρωτιέμαι και θα ήθελα τις απόψεις σας! Φίλε migf1, δυστυχώς εξαρτάται από το που θα τρέξει ο κώδικας σου και τι δυνατότητες έχει το hardware. Για παράδειγμα μπορεί να έχει γρήγορη CPU αλλά λίγη μνήμη, μπορεί αντίστροφα να έχει πολύ μνήμη αλλά αργή CPU, μπορεί να είναι μια "ειδική" CPU όπου κάποιες εντολές κοστίζουν πολύ περισσότερους κύκλους από άλλες σε σχέση με εκείνες στα PC μας. Σε κάθε περίπτωση θα έπρεπε να είχες ενημερωθεί εκ των προτέρων για το που θα «πάει» ο κώδικας ώστε να λάβεις τις critical decisions σου πριν την σχεδίαση του. Γνωρίζω όμως ότι δυστυχώς δεν σου λένε περισσότερα οπότε τώρα απλά προχωράς με ότι σου έχουν πει και υποθέτεις ότι περισσότερο μπορεί να επιθυμούν από τα συμφραζόμενα τους. Καταλαβαίνεις τώρα φίλε DirectX γιατί από την αρχή σκέφτηκα να μπουν και στην push() τα type-specifiers, σιγά μην θυμούνται όλα αυτά τα enum !!!! Πράγματι είναι πολλά, μια λύση που θα μπορούσε να σώσει ως έναν βαθμό τα enum (καθαρά θεωρητικά τώρα) είναι ένα έξυπνο auto-suggest σε επίπεδο IDE ώστε με την πληκτρολόγηση των πρώτον δυο διακριτικών (πχ) να τους δώσει το σύνολο των enum αμέσως. Πάντως την φιλικότητα & επεκτασιμότητα των type-specifiers δεν την έχουν. ΥΓ. Για όποιον ενδιαφέρεται, το παραπάνω απόσπασμα είναι από κουβέντα που έχω με τον φίλο bxenos σε άλλο φόρουμ, ο οποίος όχι μόνο έχει συμβάλει καθοριστικά σε πολλές από τις επιλογές που έχω κάνει, αλλά έχει προτείνει κιόλας και πολύ ενδιαφέρουσες εναλλακτικές υλοποιήσεις. Αν είναι ο bxenos που έγραφε παλαιότερα στο παρόν φόρουμ, χαιρετισμούς (εξαιρετικός προγραμματιστής και αν δεν με απατά η μνήμη μου έγραφε και για embedded systems)!!
migf1 Δημοσ. 22 Νοεμβρίου 2011 Μέλος Δημοσ. 22 Νοεμβρίου 2011 Όπως τα λες είναι φίλε DirectX, θα του πω... "ή μου λες για που το θέλεις ή θα στο δώσω με minimum hardware requirements" ΥΓ. Πολύ καλός ο φίλος bxenos, ναι! Σκέτη απόλαυση οι συζητήσεις μαζί του (όπως και με αρκετά αλλά παιδιά, κι εκεί κι εδώ )
Timonkaipumpa Δημοσ. 23 Νοεμβρίου 2011 Δημοσ. 23 Νοεμβρίου 2011 migf1 Δεν έκατσα να το τεστάρω... απλά ένα παράδειγμα να σου δώσω, και μόνο για την print, πως θα μπορούσες να το κάνεις, με την δική μου οπτική γωνία, για primitive types (εάν θες και άλλα types δες λίιιγο παρακάτω) το .h αρχείο: > /** * @file test.h */ #ifndef TEST_H #define TEST_H #include <string.h> typedef enum DataTypeID_{ DTYPE_NOID = 0, DTYPE_CHAR, DTYPE_INT, DTYPE_DOUBLE, DTYPE_STRING, DTYPE_MAX }DataTypeID; typedef struct myStack_ { DataTypeID dTypeId; void* next; void* elemnt; } Stack, *pStack; extern void print (pStack* theStack); extern void push (pStack* theStack); extern void pop (pStack* theStack); #endif το .c αρχείο: > /** * @file test.c */ #include "test.h" static void printChar (pStack* theStack) { printf("Element of the node is %c", (char) (*(*theStack)->elemnt)); } static void printInt (pStack* theStack) { printf("Element of the node is %d", (int) (*(*theStack)->elemnt)); } static void printDouble (pStack* theStack) { printf("Element of the node is %f", (double) (*(*theStack)->elemnt)); } static void printString (pStack* theStack) { printf("Element of the node is %s", (char*) ((*theStack)->elemnt)); } void (*printFcns[DTYPE_MAX]) = { NULL, printChar, printInt, printDouble, printString, NULL }; void print(pStack* theStack) { printFcns[(*theStack)->dtypeID](theStack); } Για άλλα types, θα πρέπει να παρέχει το κάθε type μία print function όπου θα την καλείς με function pointer όταν το DataTypeID είναι μεγαλύτερο από το DTYPE_MAX. Υ.Γ. Εάν θες να φτιάξεις ένα API, θα μπορούσες να χρησιμοποιήσεις structs από function pointers και να έχεις μία function που να καλεί την αντίστοιχη εάν υπάρχει η print για το data type (π.χ., εάν το struct ειναι fncPointers, θα μπορούσες να το τσεκάρεις με fncPointers->pFcnType != NULL) π.χ. > struct extraType { void* theExtraType; void (*printExtra) (pStack* theStack); }theExtraType_t, *pTheExtraType_t; void printTheNewType(pStack* theStack); theExtraType_t aType = {(void*) (pTotheType), printTheNewType};
migf1 Δημοσ. 23 Νοεμβρίου 2011 Μέλος Δημοσ. 23 Νοεμβρίου 2011 ... Για άλλα types, θα πρέπει να παρέχει το κάθε type μία print function όπου θα την καλείς με function pointer όταν το DataTypeID είναι μεγαλύτερο από το DTYPE_MAX. Υ.Γ. Εάν θες να φτιάξεις ένα API, θα μπορούσες να χρησιμοποιήσεις structs από function pointers και να έχεις μία function που να καλεί την αντίστοιχη εάν υπάρχει η print για το data type (π.χ., εάν το struct ειναι fncPointers, θα μπορούσες να το τσεκάρεις με fncPointers->pFcnType != NULL) ... Μου θυμίζει ως προσέγγιση μια πρόταση του bxenos (στο άλλο φόρουμ) ο οποίος πρότεινε μια συνάρτηση... > s_define_usertype( const char *usermodifier, size_t size, void (*print)(void *data) ); όπου ο χρήστης θα προετοιμάζει τα custom data-types του, και σε συνδυασμό με δική μου πρόβλεψη για έξτρα enums DTYPE_IDs πέραν των primitive (πρότεινε μέχρι 100 μαζί με τα primitive) να έχω ένα στατικό array[ DTYPE_ID_ALL ] για όλα τα data-types, τον οποίον θα τον κάνω άμεσα index βάση DTYPE_ID. Έτσι ώστε να αρκεί απλά να μου περνάει το typid στις συναρτήσεις του interface... > push( &stack, typid, &user_data ); Αυτό σε μια προσπάθεια ενοποίησης των πάντων σε μια και μόνη push() (αντί για push_basic() και push_custom() που χρησιμοποιώ εγώ στην τελευταία μου πρόταση)... δυστυχώς ενώ είναι πολύ καλή ιδέα "σκοντάφτει" στην απαίτηση να μπορούν τα primitive data-types να περνάνε και "by value", π.χ... > push( &stack, DTYPE_INT /* (ή "%d") */, 123 ); Και η δική σου ιδέα για γενική ρουτίνα εκτύπωσης που θα καλεί μέσω indexing ενός array of function-pointers υπο-συναρτήσεις εκτύπωσης για κάθε τύπο (primitive ή μη) εκ πρώτης μου αρέσει (!) αλλά θα πρέπει να κοιτάξω αφενός αν μπορεί να υιοθετηθεί και για τις push() και peek() σύμφωνα με τις απαιτήσεις των προδιαγραφών (κυρίως εκείνο το "αγκάθι" να περνάνε by value τα primitive data-types) και αφετέρου αν έχει συγκριτικά πλεονεκτήματα με αυτό που έχω τώρα. Τα type-specifiers πάντως δεν βλέπω πως μπορούν να εξαλειφθούν χωρίς να χρειάζεται ο χρήστης να αποστηθίσει πάρα πολλά enums στο pushing. Άρα το θέμα της μετατροπής από string type-specifier σε enumed DTYPE_ID, που περιλαμβάνει encoding στη push() και decoding στις peek() & print() παραμένει. Btw, η γενική ρουτίνα εκτύπωσης που χρησιμοποιώ τώρα, αποτελείται από 1 (γρήγορο) decoding του enctype που έχει αποθηκεύσει η push() σε κάθε κόμβο, 3 συγκρίσεις DTYPE_ID ως worst case ( CUSTOM, STRING, anything else), δημιουργία formating string με το κατάλληλο type-specifier για την printf() και την printf()... > typedef struct HstDataT { int enctype; /* encoded type (contains tid & specifier alias) */ union { long double valldouble; char valchar; signed char valschar; unsigned char valuchar; short int valhint; unsigned short int valuhint; int valint; unsigned int valuint; long int vallint; unsigned long int valulint; float valfloat; double valdouble; } basic; void *pcustom; size_t size; void (*func_print_custom_data)(void *); } HstDataT; typedef struct HstNode { HstDataT data; unsigned int count; struct HstNode *down; }HstNode; /* -------------------------------------------------------------- * * -------------------------------------------------------------- */ static HstBool hst_print_node( const HstDataT *pdata ) { extern TDesc g_tdesc[ HST_TID_TOTAL ]; /* arr of type decriptions */ char tempfmt[10+1] = {'\0'}; HstDataTid tid; int tid_specalias; if ( !pdata || pdata->enctype == HST_TID_NOID ) return FALSE; /* decode saved enctype into tid & corresponding specifier-alias */ tid = HST_TDESC_DECODE_GET_TID( pdata->enctype ); tid_specalias = HST_TDESC_DECODE_GET_SPECALIAS( pdata->enctype ); /* print pdata as custom typed */ if ( tid == HST_TID_CUSTOM ) { if ( pdata->func_print_custom_data ) pdata->func_print_custom_data( pdata->pcustom ); else putchar('\n'); } /* print pdata as c-string */ else if ( tid == HST_TID_STRING ) printf("%s\n", (char *) pdata->pcustom ); /* print data as primitive typed */ else { /* construct the printf formating template: "%?\n" * arguably, 2 strcat() are faster than... * sprintf( tempfmt, "%s\n", g_tdesc[ tid ].spec[ tid_specalias ] ); */ strcat( tempfmt, g_tdesc[ tid ].spec[ tid_specalias ] ); strcat( tempfmt, "\n"); /* print the field: basic.valldouble (the largest in union) */ printf( tempfmt, pdata->basic.valldouble ); } return TRUE; } /* -------------------------------------------------------------- * * -------------------------------------------------------------- */ HstBool hst_print( const HstNode *stack ) { if ( !stack ) { printf("\tthe stack is empty or non-existant"); return FALSE; } while ( stack ) { hst_print_node( &stack->data ); stack = stack->down; } return TRUE; } Το καλό με το union είναι πως μας δίνει speed, νομίζω ακόμα ταχύτερο από το να κάναμε άμεσο indexing σε array & μας γλιτώνει από πολύ γράψιμο (αρκεί απλά να τυπώσουμε το μεγαλύτερο πεδίο του με τον κατάλληλο specifier στην printf... ούτε cast δεν χρειάζεται). Το κακό όμως είναι πως όλα τα primitive data-types της στοιβας καταλαμβάνουν sizeof(long double) χώρο στη μνήμη (που μπορεί να είναι ακόμα και 64 bytes), ακόμα κι όταν πρόκειται απλά για ένα char Σχετικά με την ξεχωριστή διαχείριση των strings, είναι απαραίτητη (νομίζω) γιατί στην υλοποίησή μου το κάνω treat ως ειδική περίπτωση των custom data-types... βασικά το διαχειρίζομαι κάπως σαν "υβριδικό" data type. Δηλαδή γίνεται pushed με την push_custom() γιατί με την push_basic() δεν μπορώ να το περάσω by value (εκτός αν επιστρέψω στην λύση της variadic push(), την οποία την απέφυγα τελικά γιατί έτεινα να συμφωνήσω με τον φίλο defacer σχετικά με τα επιθυμητά warnings του compiler, παρόλο που η χρήση των type-specifiers αντί για int typeid συνεχίζει να υπονομεύει το concept, σε μικρότερο όμως βαθμό). Τα strings λοιπόν γίνονται pushed μόνο με την push_custom() ως special case των custom types, αλλά μπορούν να γίνουν peeked και με peek_basic() και με peek_custom(). Στην 1η περίπτωση επιστρέφονται byval (δηλαδή τα περιεχόμενα του string) ενώ στη 2η περίπτωση επιστρέφονται byref (δηλαδή ο δείκτης του string). EDIT: ... > ... typedef struct myStack_ { DataTypeID dTypeId; void* next; void* elemnt; } Stack, *pStack; ... Άσχετο με το θέμα μας, αλλά αν μου επιτρέπεις μια (υποκειμενική) επισήμανση για το: typedef struct myStack { ... } *pStack, για πολλούς (συμπεριλαμβανομένου κι εμένα) αποτελεί bad-practice γιατί αυξάνει τις πιθανότητες δημιουργίας bugs και επίσης δυσκολεύει τη συντήρηση/αναβάθμιση του κώδικα (ειδικά αν γίνεται από άλλους από αυτούς που τον έγραψαν αρχικά). Ο λόγος είναι πως το typedef κάνει ουσιαστικά "αόρατο" έναν έξτρα αστερίσκο, δίνοντας την ενστικτώδη εντύπωση πως οι μεταβλητές του δεν είναι δείκτες (ψευδαίσθηση). Το p στο όνομά του είναι μεν ενδεικτικό, αλλά όσο ανεβαίνει το level of referencing (π.χ. η by-reference γραφή μιας μεταβλητής τύπου pStack τόσο περισσότερο αυξάνει το ρίσκο παρερμηνείας). Δηλαδή δηλώνοντας μια μεταβλητή: pStack mystack; ουσιαστικά έχεις: Stack *mystack που είναι πολύ πιο straight forward στην ανάγνωσή του, σε ότι αφορά δηλαδή την ακριβή απεικόνιση του τύπου της μεταβλητής Μη το πάρεις πως σου κάνω "παρατήρηση" επί προσωπικού, απλά με αφορμή τον κώδικά σου θεώρησα καλό να το επισημάνω μιας και το φόρουμ το διαβάζει πολύς κόσμος και κυρίως κόσμος που κάνει τα πρώτα του βήματα. Γνωρίζω πολύ καλά πως αποτελεί κοινή πρακτική, ειδικά στο επαγγελματικό πεδίο, με την οποία όμως τυγχάνει προσωπικά να μη συμφωνώ
migf1 Δημοσ. 15 Δεκεμβρίου 2011 Μέλος Δημοσ. 15 Δεκεμβρίου 2011 Σε αναμονή απάντησης από την Αμερική για το interface, έχω σχεδόν τελειώσει μια άλλη μικρή βιβλιοθήκη για στοίβες, αλλά αυτή τη φορά για... πάρτη μου Είναι κι αυτή generic, αλλά με περιορισμό χρήσης ενός μόνο τύπου ανά στοίβα. Υποστηρίζει κι αυτή abstractly δυο γενικούς τύπους δεδομένων: generic και primary, με τα stings να αποτελούν ειδική περίπτωση του generic. Μιας και δεν υπάρχουν συγκεκριμένες προδιαγραφές, προσέθεσα και τον τύπο long long (u)int στα primary typed data (στο C89 πρότυπο δεν υπάρχουν long long (u)ints ). Σημειολογικά, οι ονομασίες των enum που αντιστοιχούν στα integer types ακολουθούν το naming convention του header file: <limits.h> (επίσης προστέθηκε στο C99 νομίζω) .. δηλαδή, CHAR, SCHAR, UCHAR, κλπ, απλά με την προσθήκη ενός GST_ προθέματος: GST_CHAR, GST_SCHAR, GST_UCHAR, κλπ. Αντίθετα, για τους τύπους πραγματικών αριθμών δεν ακολουθώ τα πρότυπα του <float.h>, προτίμησα πιο ευανάγνωστα ονόματα: GST_FLOAT, GST_DOUBLE και GST_LDOUBLE. Για τη διαχείριση των στοιβών αυτή τη φορά ακολούθησα πιο καθαρή προσέγγιση, παρέχοντας 2 διαφορετικά σετ συναρτήσεων για τα 2 διαφορετικά abstract είδη τύπων. Με πεζά όλα τους τα γράμματα είναι όσες ασχολούνται με primary typed στοίβες, ενώ με κεφαλαίο το 1ο τους γράμμα όσες αναφέρονται σε generic typed στοίβες. Οπότε για παράδειγμα, ο κώδικας που ακολουθεί διαχειρίζεται primary typed στοίβα με integers (παραλείπω τα πολλά error-checks για να μη βγει μακρινάρι)... > GStack *stack = gs_new( GST_INT ); register int i; srand( time(NULL) ); for (i=0; i < 10; i++) gs_push( &stack, rand() % 100 ); printf( "count = %d\n", gs_count( &stack ) ); while ( !gs_empty( &stack ) ) printf("%d\n", (int)gs_pop( &stack ) ); gs_destroy( &stack ); Ενώ ο επόμενος κώδικας διαχειρίζεται generic typed στοίβα... > struct mydata { int n,m; float x; char c; }; struct mydata data1 = { .n=10, .m=20, .x=50.10, c='A' }; struct mydata data2 = { .n=1, .m=2, .x=5.1, c='Z' }; struct mydata temp; GStack *stack = gs_New( GST_POINTER, sizeof(struct mydata) ); gs_Push( &stack, &data1 ); gs_Push( &stack, &data2 ); printf("data 2: %d, %d, %f, %c\n", ((struct mydata *)gs_PopData(&stack, &temp))->n, temp.m, temp.x, temp.c ); temp = *(struct mydata *) gs_Τop( &stack ); printf("data 1: %d, %d, %f, %c\n", temp.n, temp.m, temp.x, temp.c ); gs_Destroy( &stack ); Και αυτός διαχειρίζεται c-string typed στοίβα, που ουσιαστικά δέχεται c-strings of arbitrary size στον κάθε της κόμβο... > #define MAX_STRSIZE (10+1) char s[ MAX_STRSIZE ] = "12345"; GStack *stack = gs_New( GST_STRING, 0 ); // ignored 2nd param gs_Push( &stack, s ); gs_Push( &stack, "I'm a string with more than MAX_STRSIZE characters" ); strcat( s, "678"); gs_Push( &stack, s ); gs_Push( &stack, "fdsfjk ddskfj dsklfj dsklfj sdkljfdskjf dskfjdsk jdkjf dskfj dskfj"); while ( !gs_Empty( &stack ) ) { puts( gs_Top( &stack ) ); gs_Pop( &stack ); } gs_Destroy( &stack ); Ακόμα δεν την έχω τελειώσει, ούτε καν της έχω φτιάξει ξεχωριστό header file, αλλά την παραθέτω επειδή νομίζω μπορεί να φανεί χρήσιμη... έστω και απλά σαν κώδικας. Στην main() έχω στριμώξει μια απλή παραλλαγή της Ξερής, ως δείγμα χρήσης συναρτήσεων της βιβλιοθήκης. Αρχικά μοιράζονται στο τραπέζι 4 φύλλα κι από 6 στον καθένα από τους 2 (CPU controlled) παίκτες. που παίζουν εναλλάξ επί 4 γύρους. Ο κάθε παίκτης ρίχνει το τελευταίο φύλλο που του μοιράστηκε, το οποίο αν έχει τον ίδιο αριθμό με τον πάνω-πάνω φύλλο του τραπεζιού τα μαζεύει όλα. Στο τέλος όσα φύλλα μείνουν στο τραπέζι πάνε στον τελευταίο παίκτη, εκτός αν μέχρι τότε δεν έχει μαζέψει κανείς κανένα φύλλο στη διάρκεια των 4 γύρων (σε αυτή την περίπτωση δεν κερδίζει κανείς). Νικητής είναι όποιος έχει μαζέψει τα περισσότερα φύλλα... > /* =================================================================== * Name: Generic Stack (GStack) * Type: Library * Author: migf1 < [email protected] > * Language: C (C99) * * Description: A simple library impelemeting the basic stack operations, * capable of handling data of many types (primary and generic). * * Stack Operations: new(), push(), pop(), top(), empty(), count(), destroy() * New(), Push(), Pop(), PopData(), Top(), Empty(), Count(), Destroy() * * Notes: Make sure you have read the readme.txt before using the library. * * =================================================================== */ #include <stdio.h> #include <stdlib.h> #include <string.h> /* for mem*() functions */ #include <limits.h> /* for integer limits */ #include <stdint.h> /* for SIZE_MAX */ #include <stdarg.h> /* for variadic functions support */ #include <float.h> /* for float limits */ /* for denoting function failures loudly */ #define GS_VERBOSE 1 #define MSG_FAILURE( msg ) \ do \ if ( GS_VERBOSE ) \ fprintf( stderr, "*** %s: %s\n\n", __func__, (msg) ); \ while(0) /* a crossplatform alternative to system("pause") */ #define pressENTER() \ do{ \ char myInBUFer[255]={'\0'}; \ printf("\npress ENTER..."); \ fgets(myInBUFer, 255, stdin); \ }while(0) typedef enum { FALSE=0, TRUE } Bool; enum GSType { GST_INVALID = -1, /* UNUSED by the library */ GST_CHAR, GST_SCHAR, /* signed char */ GST_UCHAR, /* unsigned char */ GST_SHRT, /* short int */ GST_USHRT, /* unisgned short int */ GST_INT, GST_UINT, /* unsigned int */ GST_LONG, /* long int */ GST_ULONG, /* unsigned long int */ GST_LLONG, /* long long int */ GST_ULLONG, /* unsigned long long int */ GST_FLOAT, GST_DOUBLE, GST_LDOUBLE, /* long double */ GST_STRING, GST_POINTER, /* must always be last (not a type, just their total count ) */ GST_NTYPES }; #define VALID_GSType( tid ) ( (tid) > GST_INVALID && (tid) < GST_NTYPES ) /* * signed types range-checking related macros * (prom) must be the value in a promoted type * (min_t) & (max_t) must be the range boundaries of the un-promoted type to be checked */ #define GST_SIGNED_IS_INRANGE( prom, min_t, max_t ) \ ( (prom) >= (min_t) && (prom) <= (max_t) ) #define GST_SIGNED_ADJUST( prom, min_t, max_t) \ ( (prom) < (min_t) ? (min_t) : ( (prom) > (max_t) ? (max_t) : (prom) ) ) /* * table with all GSType sizes (for details read the readme.txt file) * IMPORTANT: table indexing MUST MATCH enum GSType */ size_t g_gstsize[ GST_NTYPES ] = { sizeof(int), sizeof(int), sizeof(unsigned int), /* GST_CHAR, GST_SCHAR, GST_UCHAR, */ sizeof(int), sizeof(unsigned int), /* GST_SHRT, GST_USHRT */ sizeof(int), sizeof(unsigned int), /* GST_INT, GST_UINT */ sizeof(long long int), sizeof(unsigned long long int), /* GST_LONG, GST_ULONG */ sizeof(long long int), sizeof(unsigned long long int), /* GST_LLONG, GST_ULLONG */ sizeof(double), sizeof(double), /* GST_FLOAT, GST_DOUBLE */ sizeof(long double), /* GST_LDOUBLE */ 0U, 0U /* GST_STRING, GST_POINTER */ }; typedef struct GSLnode { void *data; struct GSLnode *prev; }GSLnode; typedef struct GStack GStack; struct GStack { enum GSType tid; /* id of the data type for all the nodes */ size_t tsize; /* size of the data type */ unsigned long count; /* # of nodes curently in the stack */ GSLnode *list; /* the actual stack of nodes */ }; /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ int gs_push( GStack **gstack, long double data ) { GSLnode *lnode = NULL; /* sanity check */ if ( !gstack ) { MSG_FAILURE( "pushing failure! ( invalid gstack pointer )" ); return 0; /* false */ } else if ( !*gstack ) { MSG_FAILURE("pushing failure! ( *gstack is NULL )" ); return 0; /* false */ } else if ( !VALID_GSType( (*gstack)->tid) ) { MSG_FAILURE("pushing failure! ( invalid type )" ); return 0; /* false */ } if ( (*gstack)->tid == GST_POINTER || (*gstack)->tid == GST_STRING ) { MSG_FAILURE("pushing failure! ( for strings or custom types use: gs_Push() )"); return 0; /* false */ } /* reserve memory for a new list node */ lnode = calloc( 1, sizeof( GSLnode ) ); if ( !lnode ) { MSG_FAILURE( "out of memory, please cleanup & exit the program!" ); return 0; /* false */ } /* allocate space for primary data */ if ( (*gstack)->tsize > 0 ) lnode->data = malloc( (*gstack)->tsize ); if ( !lnode->data ) { MSG_FAILURE("invalid size or out of memory, please cleanup & exit!" ); free( lnode ); return 0; /* false */ } switch ( (*gstack)->tid ) { case GST_CHAR: /* NOTE: GST_CHAR is considered signed char*/ case GST_SCHAR: { long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, SCHAR_MIN, SCHAR_MAX ) ) { val = GST_SIGNED_ADJUST( val, SCHAR_MIN, SCHAR_MAX ); MSG_FAILURE("out of range GST_SCHAR auto adjusted!"); } memcpy( lnode->data, (signed char *)&val, (*gstack)->tsize ); break; } case GST_UCHAR: { long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, 0, UCHAR_MAX ) ) { val = GST_SIGNED_ADJUST( val, 0, UCHAR_MAX ); MSG_FAILURE("out of range GST_UCHAR auto adjusted!"); } memcpy( lnode->data, (unsigned char *)&val, (*gstack)->tsize ); break; } case GST_SHRT: { long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, SHRT_MIN, SHRT_MAX ) ) { val = GST_SIGNED_ADJUST( val, SHRT_MIN, SHRT_MAX ); MSG_FAILURE("out of range GST_SHRT auto adjusted!"); } memcpy( lnode->data, (short int *)&val, (*gstack)->tsize ); break; } case GST_USHRT: { long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, 0, USHRT_MAX ) ) { val = GST_SIGNED_ADJUST( val, 0, USHRT_MAX ); MSG_FAILURE("out of range GST_USHRT auto adjusted!"); } memcpy( lnode->data, (unsigned short int *)&val, (*gstack)->tsize ); break; } case GST_INT: { long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, INT_MIN, INT_MAX ) ) { val = GST_SIGNED_ADJUST( val, INT_MIN, INT_MAX ); MSG_FAILURE("out of range GST_INT auto adjusted!"); } memcpy( lnode->data, (int *)&val, (*gstack)->tsize ); break; } case GST_UINT: { long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, 0, UINT_MAX ) ) { val = GST_SIGNED_ADJUST( val, 0, UINT_MAX ); MSG_FAILURE("out of range GST_UINT auto adjusted!"); } memcpy( lnode->data, (unsigned int *)&val, (*gstack)->tsize ); break; } case GST_LONG: { /* WARNING: range-checking is IMPOSSIBLE! */ long long int val = (long long int) data; if ( !GST_SIGNED_IS_INRANGE( val, LONG_MIN, LONG_MAX ) ) { val = GST_SIGNED_ADJUST( val, LONG_MIN, LONG_MAX ); MSG_FAILURE("out of range GST_LONG auto adjusted!"); } memcpy( lnode->data, (long int *)&val, (*gstack)->tsize ); break; } case GST_ULONG: { /* WARNING: range-checking is IMPOSSIBLE! */ long long int val = (long long int ) data; if ( !GST_SIGNED_IS_INRANGE( val, 0, ULONG_MAX ) ) { val = GST_SIGNED_ADJUST( val, 0, ULONG_MAX ); MSG_FAILURE("out of range GST_ULONG auto adjusted!"); } memcpy(lnode->data, (unsigned long int *)&val, (*gstack)->tsize); break; } case GST_LLONG: { /* WARNING: range-checking is IMPOSSIBLE! */ long long int val = (long long int) data; memcpy( lnode->data, (long long int *)&val, (*gstack)->tsize ); break; } case GST_ULLONG: { /* WARNING: range-checking is IMPOSSIBLE! */ unsigned long long val = (unsigned long long int) data; memcpy(lnode->data, (unsigned long long *)&val, (*gstack)->tsize); break; } case GST_DOUBLE: /* WARNING: range-checking is IMPOSSIBLE! */ case GST_FLOAT: { /* GST_FLOAT & GST_DOUBLE are the same */ double val = (double) data; memcpy( lnode->data, (double *)&val, (*gstack)->tsize ); break; } case GST_LDOUBLE: { memcpy(lnode->data, (long double *)&data, (*gstack)->tsize); break; } default: free( lnode->data); free( lnode ); return 0; } (*gstack)->count = !(*gstack)->list ? 1 : (*gstack)->count + 1; lnode->prev = (*gstack)->list; (*gstack)->list = lnode; return 1; /* true */ } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ long double gs_pop( GStack **gstack ) { GSLnode *templnode = NULL; long double ret = LDBL_MAX; /* sanity checks */ if ( !gstack ) { MSG_FAILURE( "Popping failure! ( invalid gstack pointer )" ); return LDBL_MAX; } if ( !(*gstack) ) { MSG_FAILURE( "popping failure! ( *gstack is NULL )" ); return LDBL_MAX; } if ( !(*gstack)->list ) { MSG_FAILURE( "popping failure! ( (*gstack)->list is NULL )" ); return LDBL_MAX; } if ( !(*gstack)->list->data ) { MSG_FAILURE( "popping failure! ( (*gstack)->list->data is NULL )" ); return LDBL_MAX; } if ( (*gstack)->tid == GST_POINTER || (*gstack)->tid == GST_STRING ) { MSG_FAILURE("popping failure! ( for strings or custom types use: gs_Pop() )"); return LDBL_MAX; } templnode = (*gstack)->list; (*gstack)->list = (*gstack)->list->prev; (*gstack)->count--; ret = *(long double *)templnode->data; free( templnode->data ); free( templnode ); return ret; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ long double gs_top( GStack *const *gstack ) { /* sanity check */ if ( !gstack ) { MSG_FAILURE("topping failure! ( invalid gstack pointer )"); return LDBL_MAX; } if ( !*gstack ) { MSG_FAILURE("topping failure! ( *gstack is NULL )"); return LDBL_MAX; } if ( (*gstack)->tid == GST_POINTER || (*gstack)->tid == GST_STRING ) { MSG_FAILURE("topping failure! ( for strings or custom types use: gs_Top() )"); return (long double) LDBL_MAX; /* error */ } return (*gstack)->list && (*gstack)->list->data ? *(long double *)(*gstack)->list->data : LDBL_MAX; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ int gs_empty( GStack *const *gstack ) { /* sanity check */ if ( !gstack ) { MSG_FAILURE( "invalid gstack pointer! ( returned value: TRUE )" ); return 1; /* true */ } if ( !*gstack ) { MSG_FAILURE( "you must create a stack first! ( returned value: TRUE )" ); return 1; /* true */ } if ( (*gstack)->tid == GST_POINTER || (*gstack)->tid == GST_STRING ) { MSG_FAILURE("invalid type! for custom or string data use: gs_Pop()"); return 1; /* true */ } return (*gstack)->list == NULL; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ unsigned long int gs_count( GStack *const *gstack ) { /* sanity check */ if ( !gstack ) { MSG_FAILURE( "invalid gstack pointer! ( returned value: 0U )" ); return 0U; } if ( !*gstack ) { MSG_FAILURE( "you must create a stack first! ( returned value: 0U )" ); return 0U; } if ( (*gstack)->tid == GST_POINTER || (*gstack)->tid == GST_STRING ) { MSG_FAILURE("invalid type! for strings or custom types use: gs_Count()"); return 0U; /* true */ } return (*gstack)->count; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ void gs_destroy( GStack **gstack ) { /* sanity check */ if ( !gstack || !(*gstack) ) { MSG_FAILURE( "sanity check failed, destroying ignored!" ); return; } if ( (*gstack)->tid == GST_POINTER || (*gstack)->tid == GST_STRING ) { MSG_FAILURE("invalid type! for strings or custom types use: gs_Destroy()"); return; } while ( (*gstack)->list ) gs_pop( gstack ); (*gstack)->list = NULL; /* just in case */ free (*gstack ); *gstack = NULL; return; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ GStack *gs_new( const enum GSType tid ) { GStack *self = NULL; /* sanity checks */ if ( !VALID_GSType(tid) ) { MSG_FAILURE("sanity check failed, stack object was NOT created!"); return NULL; } if ( tid == GST_POINTER || tid == GST_STRING) { MSG_FAILURE("stack was NOT created! ( for custom-types use gs_New() )"); return NULL; } self = calloc(1, sizeof( GStack ) ); if ( !self ) { MSG_FAILURE( "out of memory, please cleanup & exit the program!" ); return NULL; } /* no need to zero/NULL self->count and self->data (due to calloc) */ self->tid = tid; self->tsize = g_gstsize[ tid ]; return self; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ int gs_Push( GStack **gstack, const void *data ) { GSLnode *lnode = NULL; size_t tsize = 0U; /* sanity check */ if ( !data ) { MSG_FAILURE( "Pushing failure! ( invalid data pointer )" ); return 0; /* false */ } else if ( !gstack ) { MSG_FAILURE( "Pushing failure! ( invalid gstack pointer )" ); return 0; /* false */ } else if ( !*gstack ) { MSG_FAILURE("Pushing failure! ( *gstack is NULL )" ); return 0; /* false */ } else if ( !VALID_GSType( (*gstack)->tid) ) { MSG_FAILURE("Pushing failure! ( invalid type )" ); return 0; /* false */ } if ( (*gstack)->tid != GST_POINTER && (*gstack)->tid != GST_STRING ) { MSG_FAILURE("Pushing failure! ( for primary types use: gs_push() )" ); return 0; /* false */ } /* reserve memory for a new list node */ lnode = calloc( 1, sizeof( GSLnode ) ); if ( !lnode ) { MSG_FAILURE( "out of memory, please cleanup & exit the program!" ); return 0; /* false */ } /* for strings ignore (*gstack)->tsize, use strlen(str)+1 instead */ tsize = (*gstack)->tsize; if ( (*gstack)->tid == GST_STRING ) { tsize = strlen( (char *)data ) + 1; if ( tsize == 1 ) MSG_FAILURE("NOTE: an empty string is about to get pushed!"); } /* allocate tsize bytes of space for the custom data or the string */ lnode->data = malloc( tsize ); if ( !lnode->data ) { MSG_FAILURE("invalid size or out of memory, please cleanup & exit!" ); free( lnode ); return 0; /* false */ } /* copy custom data or string into the newly created list node */ memcpy( lnode->data, data, tsize ); /* push the new list node onto the stack */ (*gstack)->count = !(*gstack)->list ? 1 : (*gstack)->count + 1; lnode->prev = (*gstack)->list; (*gstack)->list = lnode; return 1; /* true */ } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ int gs_Pop( GStack **gstack ) { GSLnode *templnode = NULL; /* sanity checks */ if ( !gstack ) { MSG_FAILURE( "Popping failure! ( invalid gstack pointer )" ); return 0; /* false */ } if ( !(*gstack) ) { MSG_FAILURE( "Popping failure! ( *gstack is NULL )" ); return 0; /* false */ } if ( !(*gstack)->list ) { MSG_FAILURE( "Popping failure! ( (*gstack)->list is NULL )" ); return 0; /* false */ } if ( !(*gstack)->list->data ) { MSG_FAILURE( "Popping failure! ( (*gstack)->list->data is NULL )" ); return 0; /* false */ } if ( (*gstack)->tid != GST_POINTER && (*gstack)->tid != GST_STRING ) { MSG_FAILURE("Popping failure! ( for primary types use: gs_pop() )"); return 0; /* false */ } templnode = (*gstack)->list; (*gstack)->list = (*gstack)->list->prev; (*gstack)->count--; free( templnode->data ); free( templnode ); return 1; /* true */ } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ void *gs_PopData( GStack **gstack, void *single ) { GSLnode *templnode = NULL; /* sanity checks */ if ( !gstack ) { MSG_FAILURE( "Popping failure! ( invalid gstack pointer )" ); return NULL; } if ( !single ) { MSG_FAILURE( "Popping failure! ( invalid single pointer )" ); return NULL; } if ( !(*gstack) ) { MSG_FAILURE( "Popping failure! ( *gstack is NULL )" ); return NULL; } if ( !(*gstack)->list ) { MSG_FAILURE( "Popping failure! ( (*gstack)->list is NULL )" ); return NULL; } if ( !(*gstack)->list->data ) { MSG_FAILURE( "Popping failure! ( (*gstack)->list->data is NULL )" ); return NULL; } if ( (*gstack)->tid == GST_STRING ) { MSG_FAILURE("this operation is not allowed on GST_STRING typed stacks!"); return NULL; } if ( (*gstack)->tid != GST_POINTER ) { MSG_FAILURE("Popping failure! ( for primary types use: gs_pop() )"); return NULL; } templnode = (*gstack)->list; (*gstack)->list = (*gstack)->list->prev; (*gstack)->count--; if ( (*gstack)->tsize > 0 ) memcpy( single, templnode->data, (*gstack)->tsize ); else { MSG_FAILURE("Popping failure! ( invalid (*gstack)->tsize )"); return NULL; } free( templnode->data ); free( templnode ); return single; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ void *gs_Top( GStack *const *gstack ) { /* sanity check */ if ( !gstack ) { MSG_FAILURE("Topping failure! ( invalid gstack pointer )"); return NULL; } if ( !*gstack ) { MSG_FAILURE("Topping failure! ( *gstack is NULL )"); return NULL; } if ( (*gstack)->tid != GST_POINTER && (*gstack)->tid != GST_STRING ) { MSG_FAILURE("Topping failure! ( for primary types use: gs_top() )"); return NULL; } return ( (*gstack)->list && (*gstack)->list->data) ? (*gstack)->list->data : NULL; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ int gs_Empty( GStack *const *gstack ) { /* sanity check */ if ( !gstack ) { MSG_FAILURE("invalid gstack pointer! ( returned value: TRUE )"); return 1; /* true */ } if ( !*gstack ) { MSG_FAILURE("you must create a stack first! ( returned value: TRUE )"); return 1; /* true */ } if ( (*gstack)->tid != GST_POINTER && (*gstack)->tid != GST_STRING ) { MSG_FAILURE("invalid type! for primary types use: gs_pop()"); return 1; /* true */ } return (*gstack)->list == NULL; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ unsigned long int gs_Count( GStack *const *gstack ) { /* sanity check */ if ( !gstack ) { MSG_FAILURE( "invalid gstack pointer! ( returned value: 0U )" ); return 0U; } if ( !*gstack ) { MSG_FAILURE( "you must create a stack first! ( returned value: 0U )" ); return 0U; } if ( (*gstack)->tid != GST_POINTER && (*gstack)->tid != GST_STRING ) { MSG_FAILURE("invalid type! for primary types use: gs_count()"); return 0U; /* true */ } return (*gstack)->count; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ void gs_Destroy( GStack **gstack ) { /* sanity check */ if ( !gstack || !(*gstack) ) { MSG_FAILURE( "sanity check failed, destroying ignored!" ); return; } if ( (*gstack)->tid != GST_POINTER && (*gstack)->tid != GST_STRING ) { MSG_FAILURE("invalid type! for primary types use: gs_destroy()"); return; } while ( (*gstack)->list ) gs_Pop( gstack ); (*gstack)->list = NULL; /* just in case */ free (*gstack ); *gstack = NULL; return; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ GStack *gs_New( const enum GSType tid, const size_t tsize ) { GStack *self = NULL; /* sanity checks */ if ( !VALID_GSType(tid) ) { MSG_FAILURE("sanity check failed, stack object was NOT created!"); return NULL; } if ( tid != GST_POINTER && tid != GST_STRING) { MSG_FAILURE("stack was NOT created! ( for primary types use: gs_new() )"); return NULL; } self = calloc(1, sizeof( GStack ) ); if ( !self ) { MSG_FAILURE( "out of memory, please cleanup & exit the program!" ); return NULL; } /* no need to zero/NULL self->count and self->data (due to calloc) */ self->tid = tid; /* tsize needs to be considered ONLY for GST_POINTER, not for GST_STRING */ if ( self->tid == GST_STRING ) return self; /* accept tsize for type GST_POINTER */ if ( tsize > 0 ) { self->tsize = tsize; g_gstsize[ GST_POINTER ] = tsize; } else { MSG_FAILURE("invalid size argument, stack was NOT created! (return value: NULL)"); free( self ); return NULL; } return self; } /* ----------------------------------------------------------------------- * * ----------------------------------------------------------------------- */ #include <time.h> /* for randomizer */ #define NROWS 4 /* 4 suits */ #define NCOLS 13 /* 13 symbols per suit */ #define NCARDS (NROWS * NCOLS) /* total # of cards in the deck */ #define ROW(n) ( (n) / NCOLS ) /* unused */ #define COL(n) ( (n) % NCOLS ) /* unused */ #define IDX(i,j) ( (i)*NCOLS + (j) ) /* convert a suit-id to string */ #define STRSUIT( su ) \ ( \ H == (su) ? "Hearts" : D == (su) ? "Diamonds" : C == (su) ? "Clubs" : "Spades" \ ) enum SuitId { H, D, C, S }; enum SymbId { SA=0, S2, S3, S4, S5, S6, S7, S8, S9, S10, SJ, SQ, SK }; typedef struct card { enum SuitId suitId; enum SymbId symbId; int isdealt; } Card; typedef struct player { GStack *hand, *coll; } Player; int main( void ) { char *strsymb[ SK+1 ] = { "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King" }; Card deck[ NCARDS ], dummy; Player player[ 2 ] = { { .hand = gs_New( GST_POINTER, sizeof(Card) ), .coll = gs_New( GST_POINTER, sizeof(Card) ) }, { .hand = gs_New( GST_POINTER, sizeof(Card) ), .coll = gs_New( GST_POINTER, sizeof(Card) ) } }; GStack *table = gs_New( GST_POINTER, sizeof( Card ) ); register int i, j, round, hand; srand( time(NULL) ); /* initialize the deck */ for (i=H; i <= S; i++) { for (j=SA; j <= SK; j++ ) { deck[ IDX(i,j) ].suitId = i; deck[ IDX(i,j) ].symbId = j; deck[ IDX(i,j) ].isdealt = 0; /* false */ } } /* suffle the deck (swap random pairs of cards 200 times ) */ for (i=0; i < 200; i++) { int rand1 = rand() % NCARDS; int rand2; Card temp = deck[ rand1 ]; do { rand2 = rand() % NCARDS; } while (rand2 == rand1 ); deck[ rand1 ] = deck[ rand2 ]; deck[ rand2 ] = temp; } printf( "deck inited & suffled..." ); /* deal 4 cards on the table */ j = 0; /* remember 1st non-dealt card in deck */ for (i=j; i < 4; i++, j++) { deck[i].isdealt = 1; /* true */ gs_Push( &table, &deck[ i ] ); } printf("4 cards dealt on the table\n"); /* now play 4 rounds, dealing 6 cards to each player in every round */ round = 4; while ( round-- ) { printf("\n____________________________ ROUND #%d\n\n", 4-round); /* deal 6 cards to each player */ for ( i=0; i < 12; i++, j++ ) { if ( i < 6 ) { deck[ j ].isdealt = 1; /* true */ gs_Push( &player[ 0 ].hand, &deck[ j ] ); } else { deck[ j ].isdealt = 1; /* true */ gs_Push( &player[ 1 ].hand, &deck[ j ] ); } } /* each player plays his top card on the table (if match, he collects them)*/ /* 6 cards per hand */ hand = 6; while ( hand-- ) { printf("\n-- Round %d | Hand %d -----------------\n\n", 4-round, 6-hand); /* 2 players */ for ( i=0; i < 2; i++ ) { Card *tabtop = gs_Top( &table ); Card *plrtop = gs_Top( &player[i].hand ); int ismatch = tabtop && plrtop && tabtop->symbId == plrtop->symbId; printf( "on table: %s (%2d cards)\n", tabtop ? strsymb[ tabtop->symbId ] : "< empty >", tabtop ? gs_Count( &table ) : 0 ); printf( "player %d: %s\n\n", i+1, strsymb[ plrtop->symbId ]); if ( ismatch ) { unsigned int tabcount = gs_Count( &table ); gs_Push(&player[i].coll, gs_PopData(&player[i].hand, &dummy) ); while ( !gs_Empty( &table ) ) { gs_Push(&player[i].coll, gs_PopData(&table, &dummy) ); } printf( "\n\aPLAYER %d SWEEPS THE TABLE (%2u cards )\n\n", i+1, tabcount+1 ); } else { if ( plrtop ) { gs_Push(&table, gs_PopData(&player[i].hand, &dummy)); } } } /* end of for (players) */ } /* end of while (hands) */ } /* end of while (rounds) */ /* transfer any cards left on the table into the collected stack of player-2 */ while ( !gs_Empty( &table ) ) { /* only if table has less than 52 cards */ if ( gs_Count( &table ) != NCARDS ) gs_Push( &player[1].coll, gs_PopData( &table, &dummy ) ); } puts("\n========== R E S U L T S ==========\n"); printf("player 1 collected %2u cards\n", gs_Count( &player[0].coll) ); printf("player 2 collected %2u cards\n", gs_Count( &player[1].coll) ); /* cleanup and exit */ for (i=0; i < 1; i++) { gs_Destroy( &player[i].hand ); gs_Destroy( &player[i].coll ); } gs_Destroy( &table ); pressENTER(); return 0; } Όταν τη σουλουπώσω και της φτιάξω και το public .h θα την ποστάρω σε δικό της νήμα, και Θεού θέλοντος θα της προσθέσω και queue και lists, ενδεχομένως και binary search trees. Στο μεταξύ έχω γράψει κι ένα Reame.txt που εξηγεί αναλυτικά τις λεπτομέρειες της υλοποίησης των στοιβών (εννοείται πως κι αυτό δεν είναι πλήρως έτοιμο )... http://www.box.com/s/3nr8er2xhq3rgyn5tuqv ΥΓ. Αν μπείτε στον κόπο να ασχοληθείτε κάποια στιγμή, πείτε παρατηρήσεις, επισημάνσεις, υποδείξεις... κυρίως για τυχόν λαλακίες που ενδέχεται να έχω κάνει.
migf1 Δημοσ. 19 Δεκεμβρίου 2011 Μέλος Δημοσ. 19 Δεκεμβρίου 2011 Μου έχουν βγάλει τη ψυχή τα range-checks των primary types Αφενός χαζομάρα που δεν τα έβαλα σε union όπως στο αρχικό κι αφετέρου δεν με βλέπω να τη βγάζω καθαρή με τόσα primary types και το overhead που σέρνουν μαζί τους σε κάθε συνάρτηση. Όσο είχα μονάχα μία στοίβα, ήταν οκ. Τώρα που έβαλα και queue, αρχίζει και γίνεται εκνευριστικό και κυρίως επιρρεπές σε αβλεψίες. Που να βάλω δηλαδή και λίστες και δέντρα! Οπότε τα πετάω στα σκουπίδια τα primary types και κρατάω μονάχα 2 types: GENERIC και STRINGS, που ουσιαστικά η μόνη τους διαφορά είναι στο ότι στα c-strings υπολογίζεται αυτόματα το μέγεθός τους. Στην πράξη αυτό σημαίνει πως στα c-strings αγνοείται τελείως το 2ο όρισμα των constructors: > gs_New( GST_STRING, type-size ); /* stack constructor */ gq_New( GQT_STRING, type-size ); /* queue constructor */ που με τη σειρά του σημαίνει πως σε αντίθεση με τα GENERIC typed data, τα c-strings αποθηκεύονται στα nodes των στοιβών/ουρών με arbitrary size. Χρήσιμο και δικαιολογεί πιστεύω την εξειδίκευση. Προστέθηκε επίσης ένα επιπλέον πεδίο στις δομές GStack και GQueue, το οποίο χρησιμοποιείται για την προσωρινή αποθήκευση των data μετά από κάθε pop() και dequeue(), έτσι ώστε να μπορούν αυτές οι συναρτήσεις να επιστρέφουν έναν δείκτη στο αντίγραφο των δεδομένων που γίνονται free. Ως φυσικό επακόλουθο, οι τύποι επιστροφής αυτών των συναρτήσεων άλλαξαν από bool σε void *, οπότε είναι πλέον καθόλα εφικτό π.χ. το παρακάτω... > gs_Push( &stack, gq_Dequeue( &queue ) ); Με την προηγούμενη υλοποίηση έπρεπε να σπάει σε 2 μέρη... > gs_Push( &stack, gq_Peek( &queue ) ); gq_Dequeue( &queue ); Έφτιαξα κι ένα 2ο sample πρόγραμμα ως δείγμα χρήσης και στοίβας και ουράς (το 1ο sample με την Ξερή χρησιμοποιεί μονάχα στοίβες). Το 2ο αυτό sample πρόγραμμα διαβάζει μια infix αριθμητική παράσταση εκφρασμένη ως c-string, τις αφαιρεί μη αποδεκτούς χαρακτήρες (οτιδήποτε δηλαδή δεν είναι αριθμός, τελεστής ή παρένθεση) καθώς την μετατρέπει σε postfix ουρά και κατόπιν υπολογίζει και τυπώνει το τελικό αποτέλεσμα. Η διαφορά του από την πλειάδα σχετικού κώδικα που μπορεί να βρει κανείς γκουγκλάροντας είναι αφενός πως χρησιμοποιεί ουρές αντί για c-strings κι αφετέρου πως δεν απαιτεί να υπάρχουν κενά ανάμεσα στα tokens. Δεν κάνει όμως ελέγχους για συντακτικά λάθη (απόντες τελεστές, ανοιχτές παρενθέσεις που δεν κλείνουν, κλειστές παρενθέσεις που δεν ανοίγουν, κλπ). Αυτά ίσως τα προσθέσω όταν με το καλό βάλω και trees στην βιβλιοθήκη (προηγούνται οι λίστες). Οπότε κάτι σαν το παρακάτω... > (1 + 200abc ) *hjhsd3 μετατρέπεται σε... > (1+200)*3 και συνεπώς δίνει αποτέλεσμα 603. Δεν έχω όμως ασχοληθεί με ενδελεχείς ελέγχους γιατί ο πρωταρχικός σκοπός του κώδικα δεν είναι το syntax parsing, οπότε υπάρχουν πολλά και διάφορα περίεργα input που δεν ελέγχονται, πχ το: 1 2 + 3 μετατρέπεται σε: 2+3 και δίνει αποτέλεσμα 5. Υπάρχουν και input , όπως π.χ. το: 1+ που παράγουν segmentation faults (δεν οφείλονται στη βιβλιοθήκη όμως). Επίσης οι πράξεις γίνονται σε ακεραίους. Τέλος το κάθε ξεχωριστό data-structure (stack και queue προς το παρόν) είναι ένα ξεχωριστό object file, έτσι ώστε αν μπουν σε βιβλιοθήκη να γίνεται link μονάχα το object file της δομής που καλεί το πρόγραμμα, π.χ.σε Posix περιβάλλον, για βιβλιοθήκη με το όνομα: libgds.a (generic data structures)... > ar rvs libgds.a gstack.o gqueue.o gcc myprog.c -L. -lgds a.out Το παραπάνω εξηγεί και τον φαινομενικά περιττό διπλο-ορισμό π.χ. των enumerators για τα data types που έχουν ξεχωριστά ονόματα για τις στοίβες και τις ουρές (μπορούν να μπουν σε ξεχωριστό header file, κοινό σε για όλες τις επί μέρους δομές, αλλά προς το παρόν τις έχω τελείως ανεξάρτητες μεταξύ τους). Ο κώδικας του 2ου sample προγράμματος... > /* =================================================================================== * Program: Sample 2 * Type: Executable * Author: migf1 < [email protected] > * Language: C (C99) * File: sample2.c * Lib Depedancies: gstack.o gqueue.o * * Description: Sample program demonstrating the usage of generic stacks and queues, * as impelmented in the object files gstack.o & gqueue.o, respectively * * =================================================================================== */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include "gstack.h" #include "gqueue.h" #define MAXINPUT (1023+1) #define MAXTOKENS 100 #define MAXTOKSIZE (20+1) #define OPERATORS "*/%+-" #define ACCEPTABLE "()*/%+-" /* ==================== * Function Prototypes * ==================== */ static GQueue *infix2queue( const char *infix, GQueue **qinfix ); static GQueue *qin2qpost( GQueue **qinfix, GQueue **qpostfix ); static int eval_qpostfix( GQueue **qpostfix ); static int calc( char op, int op1, int op2 ); static int op_compare( const char op1, const char op2 ); /* -------------------------------------------------------- * * -------------------------------------------------------- */ int main( void ) { char infix[ MAXINPUT ] = {'\0'}; GQueue *qinfix = gq_New( GST_STRING, 0 ); GQueue *qpostfix = gq_New( GST_STRING, 0 ); printf("infix: "); fgets( infix, MAXINPUT, stdin ); /* read infix string */ infix2queue( infix, &qinfix ); /* convert it to infix queue (q) */ qin2qpost( &qinfix, &qpostfix ); /* convert infix q to postfix q */ printf("= %d\n", eval_qpostfix(&qpostfix) ); gq_Destroy( &qpostfix ); gq_Destroy( &qinfix ); return 0; } /* -------------------------------------------------------- * int calc( char op, int op1, int op2 ); * * Applies the operator op onto the operands op1 and op2. * Returns the result of the operation, or 0 on error. * -------------------------------------------------------- */ static int calc( char op, int op1, int op2 ) { int ret = 0; switch ( op ) { case '+': ret = op1 + op2; break; case '-': ret = op1 - op2; break; case '%': ret = op2 != 0 ? op1 % op2 : 0; break; case '/': ret = op2 != 0 ? op1 / op2 : 0; break; case '*': ret = op1 * op2; break; default: ret = 0; break; } return ret; } /* -------------------------------------------------------- * int eval_qpostfix( GQueue **qpostfix ); * * Evaluates & returns the result of a postfix expression, which is stored in a queue. * * To see the algorithm when the expression is stored in a string, visit: * http://jcsites.juniata.edu/faculty/rhodes/cs2mm/stackapps.htm * -------------------------------------------------------- */ static int eval_qpostfix( GQueue **qpostfix ) { char *tok = NULL; int ret = 0, op1 = 0, op2 = 0; GStack *stack = gs_New( GST_GENERIC, sizeof(int) ); if ( !stack || !qpostfix || !*qpostfix ) return 0; while ( !gq_Empty(qpostfix) ) { tok = (char *) gq_Dequeue(qpostfix); switch ( *tok ) { case '+': case '-': case '%': case '/': case '*': op2 = *(int *)gs_Pop( &stack ); op1 = *(int *)gs_Pop( &stack ); ret = calc( *tok, op1, op2 ); gs_Push( &stack, &ret ); break; default: ret = atoi(tok); gs_Push( &stack, &ret ); break; } } ret = gs_Empty(&stack) ? 0 : *(int *) gs_Pop(&stack); gs_Destroy( &stack ); return ret; } /* -------------------------------------------------------- * int op_compare( const char op1, const char op2 ); * * Compares priority between two operators. * Returns 0 if the operators are equal, 1 if op1 > op2, -1 otherwise * -------------------------------------------------------- */ static int op_compare( const char op1, const char op2 ) { char *cp = NULL; int rank1 = (cp=strchr(OPERATORS, op1)) != NULL ? (int)(cp-OPERATORS) : 0; int rank2 = (cp=strchr(OPERATORS, op2)) != NULL ? (int)(cp-OPERATORS) : 0; return rank1 > rank2 ? -1 : rank1 == rank2 ? 0 : 1; } /* -------------------------------------------------------- * GQueue *qin2qpost( GQueue **qinfix, GQueue **qpostfix ); * * Converts an infix expression stored in a queue into a postfix queue. * Returns a pointer to the postfix queu, or NULL on error. * * To see the algorithm when the expressions are stored in strings, visit: * http://everything2.com/title/Infix+to+postfix+conversion+algorithm * -------------------------------------------------------- */ static GQueue *qin2qpost( GQueue **qinfix, GQueue **qpostfix ) { char *tok = NULL; GStack *stack = gs_New( GST_STRING, 0 ); if ( !stack || !qinfix || !*qinfix || !qpostfix || !*qpostfix) return NULL; while ( !gq_Empty(qinfix) ) { tok = (char *) gq_Dequeue(qinfix); if ( strchr( OPERATORS, *tok ) ) { while ( !gs_Empty(&stack) && '(' != *(char *)gs_Top(&stack) ) { if ( op_compare( *(char *)gs_Top( &stack ), *tok) > 0 ) gq_Enqueue( qpostfix, gs_Pop(&stack) ); else break; } gs_Push( &stack, tok ); } else if ( *tok == '(' ) gs_Push( &stack, tok ); else if ( *tok == ')' ) { while ( !gs_Empty(&stack) && '(' != *(char *) gs_Top(&stack) ) gq_Enqueue( qpostfix, gs_Pop( &stack ) ); if ( !gs_Empty( &stack ) ) gs_Pop( &stack ); } else gq_Enqueue( qpostfix, tok ); } while ( !gs_Empty(&stack) ) gq_Enqueue( qpostfix, gs_Pop(&stack) ); return *qpostfix; } /* -------------------------------------------------------- * GQueue *infix2queue( const char *infix, GQueue **qinfix ); * * Converts a c-string holding an infix expression into a queue of valid postfix tokens. * Returns a pointer to the queue, or NULL on error. * * Notes: The function considers as non-acceptable input anything that is NOT * a number, an operator or a parenthesis (opening and closing) but it * does NOT check for syntax errors (mismatched parenthesis, missing * operands, etc). * -------------------------------------------------------- */ static GQueue *infix2queue( const char *infix, GQueue **qinfix ) { char tok[MAXTOKSIZE] = {'\0'}; char *cp1 = NULL, *cp2 = NULL; register int i=0, j=0; /* count tokens & tokensize */ /* sanity checks */ if ( !infix || !*infix || !qinfix || !*qinfix) return NULL; cp1 = (char *) infix; /* pointer to the c-string */ cp2 = tok; /* pointer to a token */ j = 0; for (i=0; i < MAXTOKENS && j < MAXTOKSIZE && *cp1 && *cp1 != '\n'; i++ ) { if ( strchr(ACCEPTABLE, *cp1) ) /* is acceptable char */ { *cp2++ = *cp1++; *cp2 = '\0'; j = 0; gq_Enqueue( qinfix, tok ); cp2 = tok; } else if ( isdigit( *cp1 ) ) /* is digit (acceptable) */ { /* read consequent digits, up to MAXTOKSIZE-1 (inclusive) */ while ( j < MAXTOKSIZE && isdigit(*cp1) && *cp1 != '\n') { *cp2++ = *cp1++; j++; } *cp2 = '\0'; /* eat up any extra non-acceptable chars */ if ( j == MAXTOKSIZE ) while ( !strchr(ACCEPTABLE, *cp1) ) cp1++; j = 0; gq_Enqueue( qinfix, tok ); cp2 = tok; } else cp1++; } *cp2 = '\0'; return *qinfix; } Και ο κώδικας για τα gstack.o και gqueue.o και sample1 (μερικά αποσπάσματα από διάφορες δοκιμές τα έχω απενεργοποιήσει με τον preprocessor). Σημειώστε πως χρειάζεστε C99 compiler για να τα κάνετε compile, λόγω ορισμένων C99 specific header files που χρησιμοποιώ για τις δομές (και που μάλλον είναι περιττά τώρα που πέταξα τα primary types, αλλά δεν το 'χω προσρμόσει ακόμα). gds.zip
Προτεινόμενες αναρτήσεις
Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε
Πρέπει να είστε μέλος για να αφήσετε σχόλιο
Δημιουργία λογαριασμού
Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!
Δημιουργία νέου λογαριασμούΣύνδεση
Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.
Συνδεθείτε τώρα