[C]Linked lists; wat is wijsheid?

[Verwijderd]

Ik ben bezig met een programma dat een aantal tabellen bevat. Deze zijn geimplementeerd als linked lists.

C:

struct inputinfo
{
char description[32];
char device[FILENAME_MAX];
char baud[8];
char fmt[4];
};

struct inputnode
{
struct inputnode *next,*prev;
struct inputinfo *info;
};

struct inputhead
{
int len;
struct inputnode *first,*last;
};

struct outputinfo
{
char description[32];
char device[FILENAME_MAX];
int bitrate;
int padding;
};

struct outputnode
{
struct outputnode *next,*prev;
struct outputinfo *info;
};

struct outputhead
{
int len;
struct outputnode *first,*last;
};

int add_input(struct inputinfo *info, struct inputhead *head);
int add_output(struct outputinfo *info, struct outputhead *head);

De huidige implementatie heeft voor iedere tabel een aparte routine om elementen toe te voegen. Dit vanwege het feit dat de velden in de tabellen anders zijn. Ik kan me echter niet aan de indruk onttrekken dat dit wat overdreven is.
Ik kan een algemene routine maken die char-pointers accepteert en bij de aanroep de casting doen? Is dit te prefereren boven een aantal verschillende routines? Zijn er nadelen (casting kost tijd)?
Of is dit een probleem waarbij iedereeen direct roept dat C++ (geen bal verstand van) de uitgelezen opvolger van C is om dit eenvoudig op te lossen en moet ik dus eindelijk eraan geloven? In dat geval graag een stukje code hoe het zou moeten werken (met overerving ed).

[Verwijderd]

Ik zou inderdaad gewoon een algemene routine gebruiken en dan je pointer naar de data casten. Werkt prima... overhead is te negeren. Scheelt een hoop code die weer fouten kan bevatten.

[Glimi]

Verwijderd schreef op 08 maart 2004 @ 08:07:
De huidige implementatie heeft voor iedere tabel een aparte routine om elementen toe te voegen. Dit vanwege het feit dat de velden in de tabellen anders zijn. Ik kan me echter niet aan de indruk onttrekken dat dit wat overdreven is.
Ik kan een algemene routine maken die char-pointers accepteert en bij de aanroep de casting doen? Is dit te prefereren boven een aantal verschillende routines? Zijn er nadelen (casting kost tijd)?

Als jij een char* een input/outputinfo wilt laten coderen, dan gaan dat je niet lukken met een cast. Immers hoe moet C een char* converteren naar een char*, char*, int en int? Dan zul je moeten gaan parsen.
Parsen gaat opzich wel redelijk snel (kan in O(n) als je LALR(k) / LL(k) ) grammatica's gebruikt, maar het is wel redelijk gecompliceerd om het 1-2-3 te implementeren.
Wat wel mogelijk is, is het op de pre-java-1.5 manier te doen: Zorg ervoor dat je node structuur geen informatie beslaat over de op te slaan data, maar puur over hoe van de ene data naar de volgende te komen. Vervolgens sla je je data op in een void* in de node-struct en zul je moeten casten bij het accessen van de data. Lekker unsafe, maarja een andere manier zie ik zo snel even niet in C, maar ik ben ook niet zo'n C coder

Of is dit een probleem waarbij iedereeen direct roept dat C++ (geen bal verstand van) de uitgelezen opvolger van C is om dit eenvoudig op te lossen en moet ik dus eindelijk eraan geloven? In dat geval graag een stukje code hoe het zou moeten werken (met overerving ed).

In C++ kan het type-safer. Je hebt een linked_list template, die initialiseer je met een superclasse van de 'info' structuur en je kunt aan de slag
Ik heb even geen tijd, moet zo naar m'n werk, om je voorbeeldcode te geven, maar kijk ondertussen even hier zodat je kunt zien wat de C++ LinkedList kan

edit:
markjanssen: De R1 DVD's van Noir zijn al een tijdje uit hoor

[ Voor 3% gewijzigd door Glimi op 08-03-2004 08:34 ]

[igmar]

Glimi schreef op 08 maart 2004 @ 08:29:
[...]

Als jij een char* een input/outputinfo wilt laten coderen, dan gaan dat je niet lukken met een cast. Immers hoe moet C een char* converteren naar een char*, char*, int en int? Dan zul je moeten gaan parsen.

Veels te gecompliceerd. Gewoon een algemeen type (een union), en een int die het type aangeeft.

[Verwijderd]

Dank u voor de input.

Overigens is een union niet helemaal de oplossing aangezien ik daar zooien ruimte mee ga verspillen. Dat kan uit het gegeven voorbeeld niet afgeleid worden, maar dat zijn slechts twee van de tabellen. En de gegeven tabellen zullen ook slechts weinig records bevatten. De anbdere tabellen bevatten niet het veld 'device' en missen dus 4096 bytes. Echter, er zijn wel significant meer records in die tabellen.

[Zoijar]

Hier een voorbeeldje van de C++ manier, vooral 'list.h'. http://www.cs.vu.nl/~fasmit/codestuff/

igmar schreef op 08 maart 2004 @ 09:54:
Veels te gecompliceerd. Gewoon een algemeen type (een union), en een int die het type aangeeft.

Ja, zo maak ik ook (sub)classes in C.

Kan even niks korters vinden, voorbeeld:

C:

typedef enum
{
    assignment_stat,
    compound_stat,
    expr_stat,
    for_stat,
    if_stat,
    repeat_stat,
    return_stat,
    while_stat
}
Stat_subtype;

    
struct statement
{
    Stat_subtype    subtype;

    union
    {
    struct
    {
        Expression  *lvalue;
        Expression  *rvalue;
    }
    assignment_stat;

    struct
    {
        List    *declarations;
        List    *statements;
        Scope   *scope;
        Bool    must_delete_scope;
    }
    compound_stat;

    struct
    {
        Expression  *expression;
    }
    expr_stat;

    struct for_stat
    {
        Expression  *loop_variable;
        Expression  *begin_value;
        Expression  *end_value;
        Expression  *increment_value;
        Statement   *body;
    }
    for_stat;

    struct if_stat
    {
        Expression  *condition;
        Statement   *then_body;
        Statement   *else_body; /* 0 if no else-part */
    }
    if_stat;

    struct loop_stat
    {
        Statement   *body;
        Expression  *condition;
    }
    loop_stat;

    struct return_stat
    {
        Expression  *return_value;  /* 0 if no return value */
        Token   *token;
    }
    return_stat;
    }
    un;
};


#define ASSIGNMENT_STAT(s)  ((s)->un.assignment_stat)
#define COMPOUND_STAT(s)    ((s)->un.compound_stat)
#define EXPR_STAT(s)        ((s)->un.expr_stat)
#define FOR_STAT(s)     ((s)->un.for_stat)
#define IF_STAT(s)      ((s)->un.if_stat)
#define LOOP_STAT(s)        ((s)->un.loop_stat)
#define RETURN_STAT(s)      ((s)->un.return_stat)

[ Voor 91% gewijzigd door Zoijar op 08-03-2004 11:44 ]

[Verwijderd]

Zoals je zelf al aangeeft zou je inderdaad naar C++ kunnen kijken.
Het voordeel daar is dat er al structuren als linked lists bestaan, waar je je eigen datastructuren in kunt hangen. Het hele gedoe met head, last, previous en next pointers wordt je uit handen genomen. Dat is al één voordeel van C++ boven C.


Wat je wel houdt is het probleem dat je twee verschillende structuren in één lijst wilt stoppen. Dat kun je doen als de structuren iets gemeenschappelijk hebben (zoals je zelf al zegt, met overerving van classes). Je maakt dat een baseclass Node, waar je In- en Outputnodes van afleidt; Je maakt een lijst van het type Node, en je hangt er In- en outputnodes in.

Dat werkt als de funties in die classes dezelfde datatypen teruggeven.

Maar in jouw geval hangt het datatype af van het type node. Ze hebben dus niet zoveel gemeeschappelijk als de naam doet vermoeden.
Je gaat dan toe naar een structuur waarbij je toch eerst het type van de node moet weten (de List bevat alleen elementen van het generieke 'Node' type).
Als je het type weet kun je, na een cast, de juiste functie aanspreken.


Als voorbeeld:
Je kunt een class 'Figuur' maken, die als functie 'TekenJezelf' heeft.
Dan maak je classes, afgeleid van 'Figuur', bijvoorbeeld Cirkel, Driehoek en Vierkant. Al deze classes hebben een eigen functie 'TekenJezelf' (voor alle drie verschillend, uiteraard).
Maar de class 'Cirkel' kan bijvoorbeeld een extra functie 'GetMiddelpunt' hebben, die een Driehoek niet heeft.
Je kunt een lijst van het type 'Figuur' maken en daar een aantal Driehoeken, Crikels en Vierkanten inhangen.
Je kunt dan door de lijst lopen en per lijstelement de functie 'TekenJezelf' aanroepen. Dit werkt zonder dat je weet wat het type van het element is. Het element weet zelf wat hij is, en roept de juiste TekenJezelf functie aan.
Maar als je een 'GetMiddelpunt' wilt aanroepen moet je
1) eerst weten dat het Figuur in kwestie een Cirkel is, en
2) het figuur casten naar een Cirkel, voordat je de Cirkel-specifieke functies kunt aanroepen.

Overerving werkt dus alleen als classes iets gemeenschappelijk hebben.


Gm.

[Commander Koen]

Waarom maak je niet gewoon een ADT (abstract data type) list, kan je ook hergebruiken in andere proggies.

Een klein voorbeeltje, uit mijn hoofd dus ongetest en kan stomme en typefouten bevatten

C:

typedef  void *data;

struct node {
    struct node *prev, *next;
    data d;
};

struct list {
    int nElements;
    node *first, *last;
};

int add_front(struct list *l, data d);
int add_end(struct list *l, data d);
void *look_up(struct list *l, int (*cmp)(data, data), data d); 

/* argument cmp is een pointer naar een vergelijkingsfunctie
 * met prototype:  int cmp(data d1, data d2);
 *
 * voorbeeld aanroep look_up: element = look_up(&inputl, vergelijk, (inputinfo *)input);
 */
node *look_up(struct list *l, int (*cmp)(data, data), data d) {
    node *nodep
    for(nodep = l.first; nodep != NULL; nodep = nodep->next) {
        if((*cmp)(nodep->d, d) == 0)
            return nodep;
    }
     
     return NULL;
}

[igmar]

Verwijderd schreef op 08 maart 2004 @ 11:29:
Dank u voor de input.

Overigens is een union niet helemaal de oplossing aangezien ik daar zooien ruimte mee ga verspillen.

Verspillen ? Een union voorkomt dat nu juist (mits de verschillen in inhoud niet te groot zijn). En anders toch void *, en een int die het type aangeeft.

[MSalters]

Macro? Dat is het C antwoord op templates

[Zoijar]

MSalters schreef op 08 maart 2004 @ 21:48:
Macro? Dat is het C antwoord op templates

Maar ... maar ... macros.. zijn EeeeVIiiL

[Verwijderd]

igmar schreef op 08 maart 2004 @ 14:17:
[...]


Verspillen ? Een union voorkomt dat nu juist (mits de verschillen in inhoud niet te groot zijn). En anders toch void *, en een int die het type aangeeft.

Niet echt volgens mij.

C:

typedef struct in_rs232
{
char device[FILENAME_MAX];
char baudrate[8];
char fmt[4];
} sINRS232;

typedef struct in_tcpip
{
char host[256].
char srvc[256];
} sINTCPIP;


union inparams
{
sINRS232 inrs232;
sINTCPIP intcpip;
};

Als deze union gebruikt wordt, zal een element dat sINTCPIP gebruikt, 4108 bytes groot zijn. Toch zo'n kleine 3500 bytes verspilt.
PS FILENAME_MAX = 4096 bytes.

[igmar]

Verwijderd schreef op 09 maart 2004 @ 08:54:
[...]
Niet echt volgens mij.
Als deze union gebruikt wordt, zal een element dat sINTCPIP gebruikt, 4108 bytes groot zijn. Toch zo'n kleine 3500 bytes verspilt.
PS FILENAME_MAX = 4096 bytes.

Ik zei anders vrij duidelijk 'mits de verschillen niet te groot zijn'. Aan de andere kant : Voor elk type een linked list maken is pas echt verspilling.

[Verwijderd]

igmar schreef op 09 maart 2004 @ 09:10:
[...]


Ik zei anders vrij duidelijk 'mits de verschillen niet te groot zijn'. Aan de andere kant : Voor elk type een linked list maken is pas echt verspilling.

Sorry, even overheen gelezen.

[MSalters]

Zoijar schreef op 08 maart 2004 @ 22:21:
[...]
Maar ... maar ... macros.. zijn EeeeVIiiL

C is EeeeVIiiL. Get used to it