migf1 Δημοσ. 27 Νοεμβρίου 2012 Δημοσ. 27 Νοεμβρίου 2012 (επεξεργασμένο) Μετέφερα την συζήτηση σε δικό της νήμα: http://www.insomnia.gr/topic/466854-generic-programming-%CE%BC%CE%B5-c/#entry5099246 ... Και κατι ακομα, ασχετο με τα προηγουμενα( που μου ηρθε φλασια), σχετικο ομως με τη C , που αμα αρχισεις δεν μπορεις να σταματησεις .... Εστω οτι εχουμε πχ μια συναρτηση εισαγωγης κομβων στο τελος μιας λιστας η οποια περνει ως ορισμα ενα δεικτη στην αρχη της λιστας, ενα δεικτη στο τελος της λιστας ( "by-ref" και οι δυο ) και ενα int για το field της δομης... η συναρτηση ειναι αυτη Βοοl Insert( NODE **list , NODE **tail , int data ); Μπορουμε με καποιον τροπο να χρησιμοποιησουμε την ιδια συναρτηση για για ορισματα τυπου ΝΟDE2 **list, NODE2 **tail , float data ; Δηλαδη να μην ξανα γραφουμε την ιδια συναρτηση για διαφορετικους τυπους δεδομενων ;; Στη C δεν μπορείς, επειδή δεν επιτρέπει function overloading. Μπορείς να φτιάξεις αν θέλεις ένα ADT Interface (Abstract Data Type Interface) το οποίο όμως κοστίζει πολύ και σε επιδόσεις και σε πολυπλοκότητα ανάπτυξης. Από όταν είχες κάνει αυτή την ερώτηση ήθελα να σου γράψω ένα μικρό πρόγραμμα που να δείχνει έναν τρόπο του πως μπορείς να κάνεις κάτι παραπλήσιο με C. Μετά έμπλεξα με την C# (ακόμα δεν έχω ξεμπλέξει) μου έτυχε και μια δουλίτσα σε C και έτσι έμεινε πίσω. Σήμερα βρήκα λίγο χρόνο και ορμώμενος από εκείνο το νήμα με την τομή πινάκων, έκανα μια υποτυπώδη βιβλιοθήκη "sets" που τα μόνα που έχει είναι constructors, destructor, ταξινόμηση, αναζήτηση και intersection. Την έκανα όμως να δουλεύει με οποιοδήποτε data-type για τα στοιχεία των sets (τα sets elements δηλαδή). Για τον κάθε τύπο με τον οποίον θέλεις να τη χρησιμοποιήσεις , φτιάχνεις 2 συναρτήσεις: μια που εκτυπώνει την τιμή μιας μεταβλητής του τύπου, και μια που συγκρίνει τις τιμές 2 μεταβλητών του τύπου. Αυτές τις συναρτήσεις τις περνάς ως ορίσματα στις συναρτήσεις της βιβλιοθήκης. Στον constructor του set που θες να δημιουργηθεί με elements του τύπου σου, περνάς και το sizeof του τύπου (το μέγεθος δηλαδή ενός στοιχείου σε bytes). Περνάς και κάτι άλλα, που όμως δεν έχουν να κάνουν με το abstraction που ρώτησες (π.χ. περνάς μια boolean για να ξέρει αν είναι ταξινομημένα τα στοιχεία όταν δημιουργείς το set, αλλιώς τα ταξινομεί... και κάτι τέτοια). Δεν προλαβαίνω τώρα να κάνω αναλυτικό ποστ επεξήγησης (αύριο μάλλον) σου παραθέτω όμως ένα sets_test.c που χρησιμοποιεί την βιβλιοθήκη και διαχειρίζεται ομοιογενώς σύνολα ακεραίων και σύνολα strings, μέσα στο ίδιο πρόγραμμα. > #include <stdio.h> #include <stdlib.h> #include <string.h> #include <float.h> #include <limits.h> #include "sets.h" // prepare info for primary-type sets (say int) typedef int PrimaryElemT; static const PrimaryElemT elemPrimaryMaxval = INT_MAX; char fmttxtPrintPrimaryElem[] = "%d "; // prepare info for string sets #define SIZEOF_StrELEM ( 20+1 ) typedef char StringElemT; static const StringElemT elemStringMaxval[sizeOF_StrELEM] = "zzzzzzzzzzzzzzzzzzzz"; static const char *fmttxtPrintStringElem = "%s "; static const SetsBool dupsYesNo = setsNO; /*****************************************************//** * Print the value of a primary-typed element */ static void cb_print_primaryElement( const void *pElem ) { const PrimaryElemT *pelem = (const PrimaryElemT *)pElem; if ( pElem ) { printf( fmttxtPrintPrimaryElem, *pelem ); fflush( stdout ); } } /*****************************************************//** * Compare the values of two primary-typed elements */ static int cb_compare_primaryElements( const void *pElem1, const void *pElem2 ) { const PrimaryElemT *pelem1 = (const PrimaryElemT *) pElem1; const PrimaryElemT *pelem2 = (const PrimaryElemT *) pElem2; if ( !pelem1 || !pelem2 ) return INT_MAX; return (*pelem1 > *pelem2) - (*pelem1 < *pelem2); } /*****************************************************//** * Print the value of string element */ void cb_print_stringElement( const void *pElem ) { const StringElemT *pelem = (const StringElemT *)pElem; if ( pElem ) { printf( fmttxtPrintStringElem, pelem ); fflush( stdout ); } } /*****************************************************//** * Compare the values of two string elements */ static int cb_compare_stingElements( const void *pElem1, const void *pElem2 ) { const StringElemT *pelem1 = (const StringElemT *) pElem1; const StringElemT *pelem2 = (const StringElemT *) pElem2; if ( !pelem1 || !pelem2 ) return INT_MAX; return (strncmp(pelem1, pelem2, SIZEOF_StrELEM) > 0) - (strncmp(pelem1, pelem2, SIZEOF_StrELEM) < 0); } /*****************************************************//** * ********************************************************* */ int main( void ) { // define 3 arrays of strings (to be used for creating & manipulating 3 string sets) StringElemT strArr1[4][sizeOF_StrELEM] = {"John", "John", "Mary", "Alex"}; StringElemT strArr2[3][sizeOF_StrELEM] = {"Tony", "John", "John"}; StringElemT strArr3[2][sizeOF_StrELEM] = {"John", "John"}; // define 3 arrays of ints (to be used for creating & manipulating 3 int sets) PrimaryElemT primArr1[] = {65, 65, 61, 68}; PrimaryElemT primArr2[] = {67, 65, 65}; PrimaryElemT primArr3[] = {65, 65}; /* ----------------------------------------- * let's start with the 3 string sets first * ----------------------------------------- */ size_t len1 = 4; size_t len2 = 3; size_t len3 = 2; Set *set1 = NULL; Set *set2 = NULL; Set *set3 = NULL; Set *result = NULL; sets_setting_dbgmode( setsYES ); // create and populate 3 unsorted string sets set1 = set_new_init( len1, SIZEOF_StrELEM, elemStringMaxval, strArr1, setsFALSE ); set2 = set_new_init( len2, SIZEOF_StrELEM, elemStringMaxval, strArr2, setsFALSE ); set3 = set_new_init( len3, SIZEOF_StrELEM, elemStringMaxval, strArr3, setsFALSE ); // print contents of the 3 string sets set_print( set1, "1st set: ", "\n", &cb_print_stringElement ); set_print( set2, "2nd set: ", "\n", &cb_print_stringElement ); set_print( set3, "3rd set: ", "\n", &cb_print_stringElement ); // get and print the intersection of the 3 string sets result = set_get_3intersection(set1, set2, set3, dupsYesNo, &cb_compare_stingElements); set_print( result, "Intersection: ", "\n\n", &cb_print_stringElement ); // free all string sets set_free( &set1 ); set_free( &set2 ); set_free( &set3 ); set_free( &result ); /* ----------------------------------------- * now let's use the same set & len variables, but for 3 int sets this time * ----------------------------------------- */ len1 = sizeof(primArr1) / sizeof(primArr1[0]); len2 = sizeof(primArr2) / sizeof(primArr2[0]); len3 = sizeof(primArr3) / sizeof(primArr3[0]); // create and populate 3 unsorted int sets set1 = set_new_init( len1, sizeof(PrimaryElemT), &elemPrimaryMaxval, primArr1, setsFALSE ); set2 = set_new_init( len2, sizeof(PrimaryElemT), &elemPrimaryMaxval, primArr2, setsFALSE ); set3 = set_new_init( len3, sizeof(PrimaryElemT), &elemPrimaryMaxval, primArr3, setsFALSE ); // print contents of the 3 int sets set_print( set1, "1st set: ", "\n", &cb_print_primaryElement ); set_print( set2, "2nd set: ", "\n", &cb_print_primaryElement ); set_print( set3, "3rd set: ", "\n", &cb_print_primaryElement ); // get and print the intersection of the 3 int sets result = set_get_3intersection(set1, set2, set3, dupsYesNo, &cb_compare_primaryElements); set_print(result, "Intersection: ", "\n\n", &cb_print_primaryElement); /* ----------------------------------------- * since our initial int arrays contained char "compatible" values, * let's try to print all the sets and their intersection as char * ----------------------------------------- */ strncpy(fmttxtPrintPrimaryElem, "%c ", strlen(fmttxtPrintPrimaryElem) ); set_print( set1, "1st set: ", "\n", &cb_print_primaryElement ); set_print( set2, "2nd set: ", "\n", &cb_print_primaryElement ); set_print( set3, "3rd set: ", "\n", &cb_print_primaryElement ); set_print( result, "Intersection: ", "\n\n", &cb_print_primaryElement ); // free all int sets set_free( &set1 ); set_free( &set2 ); set_free( &set3 ); set_free( &result ); system( "pause" ); exit( EXIT_SUCCESS ); } Ότι βλέπεις να ξεκινάει με "set_" ή με "sets_" ανήκει στην βιβλιοθήκη. Έξοδος: > 1st set: John John Mary Alex 2nd set: Tony John John 3rd set: John John Intersection: John 1st set: 65 65 61 68 2nd set: 67 65 65 3rd set: 65 65 Intersection: 65 1st set: = A A D 2nd set: A A C 3rd set: A A Intersection: A Επεξ/σία 28 Νοεμβρίου 2012 από migf1
migf1 Δημοσ. 28 Νοεμβρίου 2012 Δημοσ. 28 Νοεμβρίου 2012 (επεξεργασμένο) Μετέφερα την συζήτηση σε δικό της νήμα: http://www.insomnia.gr/topic/466854-generic-programming-%CE%BC%CE%B5-c/#entry5099246 Λοιπόν, ας το πάμε λίγο πιο αναλυτικά σήμερα, μιας και νομίζω είναι σημαντικό να γνωρίζει κανείς τις βασικές ιδέες περί generic programming στην C (btw, το function overloading μπορεί να προσομοιωθεί στην C με variadic functions, σε C99 έχουν προστεθεί και variadic macros, ενώ σε C11 έχει προστεθεί και το Type-Generic Selection που συνήθως συνδυάζει το keyword _Generic με macros ως ένα είδος overloading). Σε γενικές γραμμές όμως, καλό είναι να γνωρίζουμε πως για generic programming η C δεν είναι ψηλά στη λίστα των προτιμώμενων γλωσσών. Εξαιρώντας τα macros, ο βασικός μηχανισμός για generic programming με C είναι μέσω δεικτών void (void *). Ο τύπος void όχι μόνο είναι incomplete τύπος αλλά και δεν γίνεται ποτέ complete. Αυτό στην πράξη σημαίνει πως δεν μπορούμε να κάνουμε dereference έναν void δείκτη. Πρέπει πρώτα να τον κάνουμε cast σε έναν complete-type pointer. Π.χ.... > float f = 0.3; void *pVoid = &f; printf( "%f\n", *pVoid ); // COMPILE TIME ERROR Ενώ... > float f = 0.3; void *pVoid = &f; printf( "%f\n", *(float *)(char *)pVoid ); // ALL FINE Μια άλλη ιδιαιτερότητα είναι πως εφόσον ο τύπος void δεν έχει size (είναι μονίμως incomplete) δεν μπορούμε να εφαρμόσουμε pointer-arithmetic σε void pointers. EDIT: Όμως το πρότυπο της γλώσσας απαιτεί οι void pointers να είναι συμβατοί με τους char pointers ως προς το pointer arithmetic, οπότε μπορούμε να εφαρμόσουμε χειροκίνητη αριθμητική δεικτών. Ως double safety measure μπορούμε πρώτα να τους κάνουμε cast σε (char *) Όπως πολύ σωστά παρατήρησε ο imitheos, το πρότυπο απαγορεύει πάντα το void pointer arithmetic. Άρα πρέπει πάντα να τους κάνουμε ΠΑΝΤΑ cast σε (char *) και κατόπιν να εφαρμόσουμε χειροκοκίνητη pointer arithmetic πάνω τους. Π.χ... > float arrFloat[5] = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f }; void *pVoid = arrFloat; printf( "%f\n", pVoid[2] ); // COMPILE TIME ERROR printf( "%f\n", *(pVoid+2) ); // COMPILE TIME ERROR printf( "%f\n", *(float *)((char *)pVoid+2) ); // NO ERRORS, αλλά δείχνει στον γάμο του καραγκιόζη Στο τελευταίο printf() δεν δείχνει ακριβώς στον γάμο του καραγκιόζη, δείχνει στο 3ο byte από την αρχή του arrFloat (αντί για τον 3ο float που θέλαμε), το οποίο byte θεωρείται κατόπιν λόγω του casting ως έναρξη ενός float αριθμού... οπότε τυπώνει άσχετο πράγμα (αντί για 3.0 που θέλαμε). Για να πάρουμε το επιθυμητό αποτέλεσμα πρέπει να κάνουμε χειροκίνητα τον ακριβή υπολογισμό της θέσης του 3ου στοιχείου, στην αριθμητική του void pointer μας... > printf( "%f\n", *(float *)((char *)pVoid + 2*sizeof(float)) ); Όπως γράφω και πιο πάνω, EDIT: μπορούμε ως extra safety measure πρέπει να τον κάνουμε πρώτα cast σε (char *) ... αλλά είναι περιττό αν ξέρουμε πως ο compiler μας ακολουθεί πιστά το πρότυπο. Για ευκολία μπορούμε να περιτυλίξουμε τα παραπάνω σε ένα βολικό macro, στο οποίο θα περνάμε τον void pointer, την τιμή του indexer i και τον τύπο στον οποίον αναφέρονται τα δεδομένα μας, και θα μας επιστρέφει την σωστή διεύθυνση casted στον δοθέντα τύπο. Οπότε θα αρκεί απλώς να κάνουμε dereference ότι μας επιστρέφει το εν λόγω macro. Π.χ... > #include <stdlib.h> #define PVOID_PLUS_I(pVoid, i, type) \ (type *)((char *)(pVoid) + (i) * sizeof(type) ) /*****************************************************//**/ int main( void ) { float arrFloat[5] = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f }; void *pVoid = arrFloat; printf( "%f\n", *PVOID_PLUS_I(pVoid, 2, float) ); exit( EXIT_SUCCESS ); } Μπορούμε να χρησιμοποιήσουμε κι απευθείας char δείκτες αντί για void, και μάλιστα είναι ουκ ολίγοι οι κώδικες που χρησιμοποιούν char δείκτες αντί για void. Με char δείκτες αντί για void ο παραπάνω κώδικας δείχνει κάπως έτσι... > #include <stdlib.h> #define ARRTYPE_PLUS_I(arr, i, type) \ (type *)((char *)(arr) + (i) * sizeof(type) ) /*****************************************************//** * ********************************************************* */ int main( void ) { float arrFloat[5] = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f }; char *pChar = (char *)arrFloat; printf( "%f\n", *ARRTYPE_PLUS_I(pChar, 2, float) ); exit( EXIT_SUCCESS ); } Η βασική διαφορά είναι πως κάνουμε εξαρχής cast τον δείκτη όταν του αναθέτουμε ως τιμή τη διεύθυνση του πίνακα, αλλιώς παραπονιέται ο compiler (ως warning όμως, όχι ως error... εξακολουθεί να λειτουργεί σωστά). Πάνω σε αυτά λοιπόν βασίζεται κι αυτή η υποτυπώδης βιβλιοθήκη που έφτιαξα ως παράδειγμα. Πέρα από τα παραπάνω, δείχνει επίσης κι έναν απλό τρόπο υλοποίησης του information hiding σε C. Λίγο αργότερα όμως, σε άλλο ποστ... EDIT: typos + διορθώσεις περί προτύπου, κατόπιν σωστής παρατήρησης του imitheoy. Επεξ/σία 28 Νοεμβρίου 2012 από migf1
imitheos Δημοσ. 28 Νοεμβρίου 2012 Δημοσ. 28 Νοεμβρίου 2012 Αν και είναι γνωστό πόσο συμπαθώ τα macro και ειδικά σε περιπτώσεις όπως αυτή που κάνουμε μπακάλικα με ματσακονιές κάτι που γίνεται εύκολα και δόκιμα σε άλλες γλώσσες, παρόλα αυτά ωραίος. Περιμένουμε και το επόμενο μέρος. Μια άλλη ιδιαιτερότητα είναι πως εφόσον ο τύπος void δεν έχει size (είναι μονίμως incomplete) δεν μπορούμε να εφαρμόσουμε pointer-arithmetic σε void pointers. Όμως το πρότυπο της γλώσσας απαιτεί οι void pointers να είναι συμβατοί με τους char pointers ως προς το pointer arithmetic, οπότε μπορούμε να εφαρμόσουμε χειροκίνητη αριθμητική δεικτών. Π.χ... > printf( "%f\n", *(float *)(pVoid+2) ); // NO ERRORS, αλλά δείχνει στον γάμο του καραγκιόζη > printf( "%f\n", *(float *)(pVoid + 2*sizeof(float)) ); // ALL FINE Όπως γράφω και πιο πάνω, μπορούμε ως extra safety measure να τον κάνουμε πρώτα cast σε (char *) ... > printf( "%f\n", *(float *)((char *)pVoid + 2*sizeof(float)) ); αλλά είναι περιττό αν ξέρουμε πως ο compiler μας ακολουθεί πιστά το πρότυπο. Για να γίνω grammar nazi άλλη μια φορά, είσαι σίγουρος για αυτό ? Συμφωνώ με το 1ο που είπες ότι απαγορεύεται η αριθμητική σε void δείκτες όχι όμως με το 2ο. Αυτό που θυμάμαι είναι ότι οι void δείκτες πρέπει να έχουν όχι ίδια αριθμητική αλλά ίδια αναπαράσταση με τους δείκτες σε char. Αυτό το γεγονός εκμεταλλεύονται πολλοί compilers και επιτρέπουν αριθμητική void δεικτών με αύξηση κατά 1 byte σαν να ήταν δείκτες σε char και έτσι μπορούμε όντως να έχουμε την "χειροκίνητη" αριθμητική που ανέφερες. Αυτό όμως είναι επέκταση κάποιων compilers. In GNU C, addition and subtraction operations are supported on pointers to void and on pointers to functions. This is done by treating the size of a void or of a function as 1. A consequence of this is that sizeof is also allowed on void and on function types, and returns 1. > % for i in c89 c99 c11; do > gcc -Wall -std=$i -pedantic tmp.c > done tmp.c: In function ‘main’: tmp.c:8:34: προειδοποίηση: pointer of type ‘void *’ used in arithmetic [-pedantic] tmp.c: In function ‘main’: tmp.c:8:34: προειδοποίηση: pointer of type ‘void *’ used in arithmetic [-pedantic] tmp.c: In function ‘main’: tmp.c:8:34: προειδοποίηση: pointer of type ‘void *’ used in arithmetic [-pedantic]
migf1 Δημοσ. 28 Νοεμβρίου 2012 Δημοσ. 28 Νοεμβρίου 2012 (επεξεργασμένο) Μετέφερα την συζήτηση σε δικό της νήμα: http://www.insomnia.gr/topic/466854-generic-programming-%CE%BC%CE%B5-c/#entry5099246 Σε συνέχεια του προηγούμενου post, μια πολύ συνηθισμένη χρήση του abstraction που περιγράφω παραπάνω είναι όταν καλούμε τις συναρτήσεις memXXX() της <stdlib.h>... > void *memset(void *buffer, int c, size_t size); void *memcpy(void *restrict dst, const void *restrict src, size_t size); void *memmove(void *dst, const void *src, size_t size); Όπως παρατηρούμε στα πρότυπα των συναρτήσεων, όλες ορίζουν με δείκτες void (void *) τα buffers που περιμένουν. Επίσης αναμένουν ως όρισμα και το συνολικό μέγεθος του buffer σε bytes. Μια πιθανή υλοποίηση ας πούμε της memcpy() θα μπορούσε να είναι κάπως έτσι (αγνοώ τα restrict για να μην μπερδεύουν χωρίς λόγο την συζήτησή μας)... > void *myMemcpy(void *dst, const void * src, size_t size) { void *ret = dst; while (size--) { *(char *)dst = *(char *)src; dst = (char *)dst + 1; src = (char *)src + 1; } return ret; } δηλαδή να γίνονται οι void δείκτες treat ως char δείκτες, προκειμένου να μπορούν να γίνουν dereferenced οι τιμές τους κατά την διαδικασία της αντιγραφής από το src buffer στο dst buffer. Αυτές οι συναρτήσεις δεν χρειάζεται να συγκρίνουν μεταξύ τους τα στοιχεία των buffers που διαχειρίζονται. Όταν χρειάζεται να γίνει σύγκριση στοιχείων, τότε υπάρχει δυσκολία. Καταρχήν πρέπει η συνάρτηση να γνωρίζει το μέγεθος του κάθε στοιχείου. Έπειτα χρειάζεται να ξέρει πως νοείται η σύγκριση 2 στοιχείων, διότι για παράδειγμα αλλιώς συγκρίνονται μεταξύ τους 2 int στοιχεία, αλλιώς 2 string στοιχεία κι αλλιώς 2 στοιχεία που είναι ας πούμε nodes μιας συνδεδεμένης λίστας. Τις πληροφορίες που χρειάζεται μια τέτοια generic συνάρτηση τις περιμένει στα ορίσματά της. Το πιο χαρακτηριστικό παράδειγμα εδώ είναι και πάλι μια συνάρτηση της <stdlib>, η qsort() που ταξινομεί όποιο buffer της περάσουμε. Το πρότυπό της είναι το εξής... > void qsort( void *buffer, size_t nelems, size_t elemSize, int (*compare)(const void *, const void *) ); Δηλαδή η συνάρτηση θέλει να ξέρει: την αρχή του buffer, το συνολικό πλήθος των στοιχείων του buffer, το μέγεθος του κάθε στοιχείου σε bytes και τέλος το πως ορίζεται η σύγκριση μεταξύ 2 στοιχείων. Όλα οκ με τα 3 πρώτα, το 4ο όρισμα όμως ίσως θέλει επεξήγηση. Δεν μπορούμε να περάσουμε ως τρόπο σύγκρισης των στοιχείων ότι μας καπνίσει. Θέλουμε έναν δείκτη σε μια συνάρτηση που πρέπει να την ορίσουμε με πολύ συγκεκριμένο τρόπο, δηλαδή στα πρότυπα που την αναμένει η qsort(). Πιο συγκεκριμένα, η συνάρτηση σύγκρισης πρέπει να παίρνει ως ορίσματα δυο δείκτες στα προς σύγκριση στοιχεία (έναν για το καθένα τους), και να επιστρέφει έναν ακέραιο μικρότερο, ίσο ή μεγαλύτερο του 0, ανάλογα με τον αν το 1ο στοιχείο είναι μικρότερο, ίσο ή μεγαλύτερο του 2ου στοιχείου (κατά αναλογία δηλαδή των συναρτήσεων strcmp() και strncmp() της <string>, κάτι που προφανώς δεν είναι σύμπτωση ). Όταν καλούμαστε λοιπόν να υλοποιήσουμε τη συνάρτηση σύγκρισης δυο ίδιων τύπου μεταβλητών (για να την περάσουμε κατόπιν ως callback στην qsort()), είμαστε υποχρεωμένοι να ακολουθήσουμε το πρότυπό της όπως το αναμένει η qsort()... δηλαδή ως void δείκτες τα 2 της ορίσματα. Οπότε, αν θέλουμε να ταξινομήσουμε ας πούμε έναν πίνακα από int μέσω της qsort(), τότε η συνάρτηση σύγκρισης θα πρέπει να πάρει τα 2 της ορίσματα ως void δείκτες και μέσα της να τα κάνει cast σε int δείκτες, προκειμένου να μπορέσει να τα κάνει dereference και να συγκρίνει τις τιμές τους. Αυτό γίνεται κάπως έτσι... > int cb_compare_integers( const void *pInt1, const void *pInt2 ) { // sanity checks should be added here const int *pint1 = (const int *) pInt1; // cast pInt1 to (const int *) const int *pint2 = (const int *) pInt2; // cast pInt2 to (const int *) return (*pint1 > *pint2) - (*pint1 < *pint2); } ή ισοδύναμα... int cb_compare_integers( const void *pInt1, const void *pInt2 ) { // sanity checks should be added here return ( *(int *)pInt1 > *(int *)pInt2 ) - ( *(int *)pInt1 < *(int *)pInt2 ); } Οπότε όταν θέλουμε για παράδειγμα να ταξινομήσουμε έναν πίνακα από 5 floats, μπορούμε να γράψουμε κάτι σαν το παρακάτω... > #include <stdio.h> #include <stdlib.h> /*****************************************************//**/ int cb_compare_floats( const void *pFloat1, const void *pFloat2 ) { // sanity checks should be added here return ( *(float *)pFloat1 > *(float *)pFloat2 ) - ( *(float *)pFloat1 < *(float *)pFloat2 ); } /*****************************************************//** * ********************************************************* */ int main( void ) { float arrFloat[5] = { 1.0f, 10.0f, 5.0f, 8.0f, 2.0f }; for (size_t i=0; i < 5; i++) printf( "%f ", arrFloat[i] ); putchar('\n'); qsort(arrFloat, 5, sizeof(float), &cb_compare_floats ); for (size_t i=0; i < 5; i++) printf( "%f ", arrFloat[i] ); putchar('\n'); system( "pause" ); exit( EXIT_SUCCESS ); } Ένα άλλο σημείο που θέλει προσοχή όταν κάνουμε generic programming είναι ο assignment operator. Δηλαδή όταν υλοποιούμε μια συνάρτηση η οποία δουλεύει με abstract data types (δηλαδή void δείκτες) δεν μπορούμε να χρησιμοποιήσουμε τον τελεστή = για να αναθέτουμε τιμές στις abstract μεταβλητές μας. Ούτε μεταξύ τους ούτε με σταθερές. Πρέπει να πληρούνται 2 προϋποθέσεις: 1. Να ξέρουμε και το μέγεθος της μεταβλητής που θα μπει στην αριστερή μεριά της ανάθεσης, το οποίο προφανώς είναι ίδιο με το μέγεθος εκείνης που θα μπει στην δεξιά μεριά της ανάθεσης. 2. Το 1. αποκλείει η τιμή που θα μπει στη δεξιά μεριά να είναι σταθερά. Πρέπει κι αυτή να είναι μια μεταβλητή που περιέχει την επιθυμητή τιμή, και να περαστεί κατόπιν στην generic συνάρτηση ένας δείκτης προς αυτή την μεταβλητή. Αφού εξασφαλιστούν οι παραπάνω προϋποθέσεις, τότε μπορεί η generic συνάρτηση μας που λειτουργεί ως assignment operator να κάνει την ανάθεση είτε με memcpy() είτε καλύτερα με memmove(). Παράδειγμα... > ... void *generic_assignment( void *left, const void *right, size_t size ) { // sanity checks should be added here return memmove( left, right, size ); } ... int main( void ) { float f1, f2 = 3.7f; generic_assignment( &f1, &f2, sizeof(float) ); ... } Το παραπάνω είναι ο τρόπος υλοποίησης generic assignment operator με χρήση δεικτών void. Ένας άλλος τρόπος είναι με macro... > #define GENERIC_ASSIGNMENT(x,y) (x=y) αλλά προφανώς προκύπτουν ακόμα περισσότερα θέματα validation από ότι με τους void δείκτες. Και κάπου εδώ τελειώνουν ο βασικές γνώσεις που χρειάζεται να έχει κανείς προκειμένου να πραγματοποιήσει generic programming μέσω void δείκτες στην C Σε επόμενο post θα δώσω και την βιβλιοθήκη, η οποία δεν χρησιμοποιεί τίποτα περισσότερα από όσα περιέγραψα στα 2 αυτά posts @imitheos: Απόλυτα σωστός! My bad, πάω να το διορθώσω (άτιμος gcc ... αν και στην βιβλιοθήκη τους κάνω έτσι κι αλλιώς cast σε char *, για αυτό δεν χτύπησε σε κανέναν από τους 3 compilers που το δοκίμασα: gcc, lcc-win32 και pelles-c). EDIT: Προστέθηκαν μερικές ακόμα απαραίτητες πληροφορίες, για generic programming προς το τέλος του post (και μερικά code snippets). Επεξ/σία 28 Νοεμβρίου 2012 από migf1
migf1 Δημοσ. 28 Νοεμβρίου 2012 Δημοσ. 28 Νοεμβρίου 2012 Μιας και είναι κάπως αυτόνομο ως θέμα το περί Generic Programming με C, άνοιξα ξεχωριστό νήμα... http://www.insomnia.gr/topic/466854-generic-programming-%CE%BC%CE%B5-c/#entry5099246
nik324 Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 (επεξεργασμένο) > struct node* insert(struct node* node, int data) { // 1. If the tree is empty, return a new, single node if (node == NULL) { //δεσμευση μνήμης για τον νέο κόμβο, αρχικοποίηση σε NULL των παιδιών } else { // 2. Otherwise, recur down the tree if (data <= node->data) node->left = insert(node->left, data); else node->right = insert(node->right, data); return(node); // return the (unchanged) node pointer } } Πώς θα το κάνω να δείχνει στον πατρικό κόμβο; Επεξ/σία 29 Νοεμβρίου 2012 από nik324
Re4cTiV3 Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 Θέλω να διαβάσω ένα αρχείο και να χρονομετρήσω σε πόση ώρα το κάνει. Για να αποφύγω να μπει το αρχικό αρχείο στην cache πρέπει να το αντιγράψω πρώτα κάπου αλλού με όνομα π.χ. temp και θα χρονομετρήσω αυτό το διάβασμα στο temp. Σωστά; Θα πρέπει να δημιουργήσω fork η οποία θα εκτελεί την /bin/cp του συστήματος και μόλις τελειώνει αυτή να διαβαζω το temp; ή να γράψω μια δικιά μου συνάρτηση copy() η οποία θα αντιγράφει χαρακτήρα χαρακτήρα στο temp και μετά χρονομέτρημα; Για χρονομέτρηση να χρησιμοποιήσω την gettimeofday() ;;
albNik Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 Στην ταχύτητα έχει πολύ σημασία το μέγεθος του bloc που διαβάζεις κάθε φορά. Στα Windows και NTFS η βέλτιστη τιμή είναι 16ΚΒ buffer Αν διαβάζεις ένα-ένα τα byte θες 3-4 δευτερόλεπτα για 1MB αρχείο. Αν τα διαβάζεις ανά 16ΚΒ δε θες ουτε 0.001 sec για 1ΜΒ
Re4cTiV3 Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 Είμαι σε unix.. Αυτά είναι θεωτηρικά έτσι; Θέλω να το δω πρακτικά..
albNik Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 Δοκίμασε να διαβάσεις ένα μεγάλο αρχείο με τη read(int fd, char* buf, int n) με buffer size =1, 1000, 10000 .... while ((n = read(fd, buf, BUFSIZ)) > 0)
Re4cTiV3 Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 αν διαβάζω συνέχεια το ίδιο αρχείο.. το λειτουργικό θα το μεταφέρει στην cache και θα το διαβάζει πιο γρήγορα απο πριν που δεν ήταν γι αυτό θέλω να κάνω ένα copy το αρχείο.. Θα πρέπει να δημιουργήσω fork η οποία θα εκτελεί την /bin/cp του συστήματος και μόλις τελειώνει αυτή να διαβαζω το temp; ή να γράψω μια δικιά μου συνάρτηση copy() η οποία θα αντιγράφει χαρακτήρα χαρακτήρα στο temp και μετά χρονομέτρημα;
imitheos Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 Μπορείς είτε να αδειάσεις την buffer cache πριν την ανάγνωση είτε να την παρακάμψεις. Για να την αδειάσεις τρέξε σαν root > # free # echo 3 > /proc/sys/vm/drop_caches # free Θα δεις ότι ένα ποσοστό μνήμης θα ελευθερωθεί γιατί ακριβώς χρησιμοποιούταν σαν cache. Αν θέλεις να την παρακάμψεις, μπορείς να χρησιμοποιήσεις τις χαμηλού επιπέδου συναρτήσεις (open αντί για fopen, read αντί για fread, κτλ) και να χρησιμοποιήσεις την επιλογή O_DIRECT ώστε να χρησιμοποιηθεί direct I/O. Έχε υπόψην όμως ότι θα γλυτώσεις μόνο από την buffer cache. Υπάρχουν και άλλα buffers που χρησιμοποιεί το λειτουργικό και δεν είναι τόσο εύκολο να τα ελέγξεις και επίσης υπάρχει και το cache του σκληρού.
nik324 Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 > struct node* insert(struct node* node, int data) { // 1. If the tree is empty, return a new, single node if (node == NULL) { //δεσμευση μνήμης για τον νέο κόμβο, αρχικοποίηση σε NULL των παιδιών } else { // 2. Otherwise, recur down the tree if (data <= node->data) node->left = insert(node->left, data); else node->right = insert(node->right, data); return(node); // return the (unchanged) node pointer } } μέσα στη πρώτη if() προσπαθω να συνδέσω με τον πατερα αλλά δεν μπορώ να σκεφτώ τρόπο να κάνω τον parent pointer να δειχνει σε πατέρα κομβο αφου δεν έχω κάπου να "πατήσω" για να το κάνω αυτό...Μήπως είναι εντελώς λάθος η συνάρτηση μου?
albNik Δημοσ. 29 Νοεμβρίου 2012 Δημοσ. 29 Νοεμβρίου 2012 Πιστεύω είναι απλό (αν δεν έχω λάθος στην malloc) Βασικά αν είναι άδειο, αυτό θα γίνει πατέρας > if(node==NULL) { node=(struct node) malloc(sizeof(struct node)); node->data=data; } Την insert θα την καλείς πάντα με τον πατέρα (η NULL)
Προτεινόμενες αναρτήσεις