Znovupoužitelnost datových struktur v C

[dl]

Jak se nejlépe dají implementovat znovupoužitelné datové struktury v C? Pokud mám jednosměrný/obousměrný spojový seznam, liší se v ukazateli na head, který je typem single_node nebo double_node:

[item]-->next vs prev<--[item]-->nex.

Chtěl bych co nejvíce přepoužívat hlavičkové soubory, něco jako jako dědičnost. Budu to muset zuřivě přetypovávat? Jak si neuseknout nohy?

           
     +-----List-----+
     ^              ^
Single-List   Doubly-List <-- uses Double-Node
^ uses Single-Node


Tak nějak. Pak třeba zásobník  implementovaný pomocí Single Listu, který už je předpřipraven. Děkuji za rady.
Implementovat každou zvlášť zvládnu. Jde mi o nějakou hiararchii -- jako v Javě a spol.

[Reklama]

[fvzcvzcvzv]

nevim jestli java je uplne nejlepsi priklad, v jave si lehce pouzijes interface a nadefinujes rozhrani trid, ktere pak muze sdilet
cela hierarchie trid, tohle bych do C ani netahal.

to je takovy problem  mit hlavicku a implementaci pro single linked list a samostatnou pro double linked list?
kod samozrejme muzu znovupouzit a trochu prepsat.

myslim, ze chcete udelat z komara velblouda.

[Jakub Galgonek]

Pokud chceš simulovat dědičnost, tak můžeš vložit rodičovskou strukturu jako první položku do dceřiné struktury:

Kód: [Vybrat]

struct parent
{
    struct parent *prev;
    struct parent *next;
};


struct child
{
    struct parent _super;  // musí být první položkou!
    int data;
};

Pokud pak máš ukazatel na struct child, tak ho můžeš přímo přetypovat na struct parent. Norma ti zaručuje, že je to korektní:

Kód: [Vybrat]

struct child *pointer1 = get_child();
struct parent *pointer2 = (struct parent *) pointer1;

Explicitním přetypováním se ale přitom nevyhneš.

[Jakub Galgonek]

Jinak seznamy se často řeší pomocí maker. Nadefinuješ si třeba takovou strukturu:

Kód: [Vybrat]

struct my_struct
{
   struct my_struct *foo_prev;
   struct my_struct *foo_next;
   int data;
}

Makru pro práci se seznamem pak předáváš typ položek (struct my_struct *) a prefix ukazatelů prev a next (foo). Takový přístup má pak tu výhodu, že můžeš strkat jednu instanci do více seznamů, pokud si na to definuješ více pointerů:

Kód: [Vybrat]

struct my_struct2
{
   struct my_struct2 *foo_prev;
   struct my_struct2 *foo_next;
   struct my_struct2 *bar_prev;
   struct my_struct2 *bar_next;
   int data;
}

Pro práci s prvním seznamem předáš makru parametr foo, pro práci s druhým pak bar.

[dl]

to je takovy problem  mit hlavicku a implementaci pro single linked list a samostatnou pro double linked list?
kod samozrejme muzu znovupouzit a trochu prepsat.

Mne jen zajímá jestli to někdo v C dělá ..., jinak máte pravdu. Trochu se nutím do procedurálního -- modulárního programování, tak mne to vrtá hlavou, kde jsou limity. Jak říkám, udělat si to zvláště umím, stejně jako jsem koukal jak je uděláno v linux/list.h. Díky za podnět.

[Reklama]

[fvzcvzcvzv]

jinak s tema strukturama a pretypovanim jdou i takove veci, protoze ten int je v paneti jako bajty za sebou, takze se to muze rozseknout
na mensi typ:

#include<stdio.h>

struct aaa {

unsigned int a;
};


struct bbb {

unsigned char x;
unsigned char y;

};

int main()
{

struct aaa bitu16;

bitu16.a=65535;

printf ("%d\n",bitu16.a);

struct bbb *bitu8 = (struct bbb*) &bitu16;

printf ("%d %d\n",bitu8->x,bitu8->y);

return 0;
}

[Kolemjdoucí]

Na tohle používá přetypování, funkce na operace se seznamem pak pracují pouze s hlavičkami.
Kdo se bojí přetypování musí použít union, což je převlečené přetypování

Kód: [Vybrat]

struct item_head
{
    struct item_head * prev;
    struct item_head * next;
}

union custom_item
{
    item_head head;
    struct   
    {
        item_head head1;
        int data1;
        int data2;
    }   
}

Jednosměrný spojový seznam se nepoužívá od té doby co je paměti přebytek.

[Kolemjdoucí]

int je v paneti jako bajty za sebou, takze se to muze rozseknout na mensi typ

Teoreticky ano, prakticky je problém s align a endianess. Vyřešit to lze, ale dá to práci.

[Jakub Galgonek]

struct bbb *bitu8 = (struct bbb*) &bitu16;

Já teda nejsem kdoví jaký znalec normy jazyka C, ale myslím, že tohle není (od C99) validní (porušuje to strict-aliasing rule).

[dl]

Díky za náměty, musím si je projít zítra s čistou hlavou. Teď jen odbočka -- sáhli byste raději po knihovně jako Glib či jiné, nebo implementovat základní DS vlastnoručně má své místo? -- s ohledem na C nikoliv C++.

[PsychoIT]

http://home.gna.org/gdsl/

[Pavel Tišnovský]

struct aaa {
unsigned int a;
};

struct bbb {
unsigned char x;
unsigned char y;
};

struct aaa bitu16;
bitu16.a=65535;
struct bbb *bitu8 = (struct bbb*) &bitu16;

Musím tedy varovat, že toto je nepřenositelné, navíc i na jedné architektuře to může a nemusí pracovat na základě příznaků při překladu, fáze měsíce, verze překladače a kdovíčeho dalšího, takže prosím pozor.

[Mirek Prýmek]

Já bych k tomu ještě dodal, že docela záleží na tom, o co ti vlastně jde. Jestli je to jenom takové cvičení, aby sis vyzkoušel pokročilejší C, ok, nic proti. Pokud jsi v C začátečník a snažíš se na něj naroubovat něco, co znáš z jiných jazyků (Java apod.), tak to mi nepřijde jako dobrej nápad - dřív nebo později se do toho imho zamotáš a stejně se ti nepodaří získat chování, na které jsi byl zvyklý. Jestli se chceš učit C, tak se ho snaž poznat takové, jaké je, jak se používá, nesnaž se na něj naroubovat něco cizího...

A pokud z nějakého důvodu fakt na vážno potřebuješ objektový přístup a zároveň C, tak by možná stálo za zvážení jít cestou http://cs.wikipedia.org/wiki/Vala_%28programovac%C3%AD_jazyk%29 nebo nějakou podobnou.

---
P.S.

Znovupoužitelnost kódu nespočívá jenom v "objektovosti" a dědičnosti. Ve funkcionálním programování bys viděl spoustu znovupoužitelného kódu a žádná dědičnost se tam nepoužívá Zrovna snažit se abstrahovat společné vlastnosti double- a single-linked listu mi nepřijde úplně dobrý příklad, množina společných operací* tam bude minimální (např. pokud bys chtěl takový "zobecněný" list třídit, jak to budeš dělat? Přidáš do double-linked nějaký callback, který ex post opraví vazby? Nebo budeš uvnitř funkce pořád ifovat? To by bylo přesně to peklo, do kterýho se dostat nechceš ).

* tj. operací, které bys mohl jedním způsobem implementovat nad oběma typy seznamů

A ještě jeden tip bych měl: ke zobecňování můžeš přistupovat i tak trochu "z druhé strany" - pomocí přístupu, který se v Elixiru jmenuje protokoly (http://elixir-lang.org/getting_started/16.html). Podobně to má i Go (http://golangtutorials.blogspot.cz/2011/06/structs-in-go-instead-of-classes-in.html) Princip spočívá v tom, že si nadefinuješ nějakou množinu operací nad strukturou, naimplementuješ pro každý typ struktury zvlášť (nejsi ničím omezený!), ale přistupuješ k nim pak jednotným způsobem. V C bys to mohl udělat třeba tak, že bys měl strukturu callbacků a pak bys volal nějaké makro třeba sort(my_linked_list) a přeložilo by se ti to třeba na "my_linked_list -> sorting -> sort(my_linked_list)", kde tvůj typ obsahuje pointer na strukturu obsahující pointery na jednotlivé operace. Strukturu s pointery máš pak jenom jednu a každý "objekt" na ni má jenom ukazatel. (pointa: v OOP se začala děsně zdůrazňovat dědičnost a zapomnělo se na skládání Pořád je to ale "neCéčkovský" přístup, který bys měl volit jenom z hodně dobrých důvodů.

[Cm]

Doporučuji podívat se jak to dělají v Linuxovém jádru. Moc pěkné. Jednoduché výkonné a elegantní. Sám používám (svou lite) modifikaci pro jednočipy.

[Mirek Prýmek]

Doporučuji podívat se jak to dělají v Linuxovém jádru. Moc pěkné. Jednoduché výkonné a elegantní. Sám používám (svou lite) modifikaci pro jednočipy.

Jo, http://lwn.net/Articles/444910/ a http://lwn.net/Articles/446317/