Dvostruki pokazivac u C-u

[ikonoklast]

Ovo mi nije bas najjasnije...pa bih zamolio nekog da mi malo pojasni
Kada se definise jednostruka ili dvostruka spregnuta lista sa typedef naredbom, npr :
typedef struct cvor { int br;
struct cvor *sl; } Cvor;

i kada posle pisemo neku f-ju koja koristi tu strukturu npr. za kreiranje liste, mozemo da stavimo ili :

void upis( Cvor **c)
{ Cvor *n; int b;
*c=NULL;
while(scanf("%d", &b)!=EOF))
{ n=(Cvor*) malloc (sizeof(Cvor));
n->br=b;
n->sl=*c;
*c=n; }
}

ili

Cvor *upis(Cvor *c)
{ Cvor *n; int b;
c=NULL;
while(scanf("%d", &b)!=EOF))
{ n=(Cvor*) malloc (sizeof(Cvor));
n->br=b;
n->sl=c;
c=n;
return c; }
}


Kapiram da 2. slucaju f-ja vraca pokazivac na , a sta vraca u prvom? Vrednost adrese na koju pokazuje pokazivac ili ?
Isto tako, u 2. slucaju *c je pokazivac na prvu strukturu u listi, a sta predstavlja u **c prvom skucaju ? Profesor nam kaze da je to pokazivac na celu listu, ali mi nije jasno kako on funkcionise...
I da li sve f-je vezane za liste mogu da se urade tako - na 2 nacina, sa obicnim i dvostrukim pokazivacem?
Hvala

 

[Raptus]

U prvom slucaju, funkcija je void, tako da ne vraca nista

Koliko ja skontah, u prvom slucaju, **c pokazuje na konkretan element liste, *c sadrzi adresu tog konkretnog elementa liste, a c sadrzi adresu pokazivaca koji pokazuje na konkretan element liste. U oba slucaja c bi trebalo da pokazuje na poslednji element dodat u listu. Sto se tice dvostrukog pokazivaca i funkcija nad listom, verujem da moze i na jedan i na drugi nacin, pa sad, zavisi kako ti vise odgovara i kako ti vise lezi.

 

[srdjan_r]

Dvostruki pokazivac ili tacnije pokazivac na pokazivac; sadrzi adresu pokazivaca.Funkcija void ima kao argument pokazivac na pokazivac **c. Prva funkcija je void jer vec radi sa objektom preko dvostrukog pokazivaca, zato i ne vraca rezultat. Recimo:
int prom = 10;
int *p1 = &prom;
int **p2 = &p2;
(da bi pristupio prom pokazivac se mora dva puta dereferencirati, dakle **pp2, dok sa jednim deferenciranjem *p2 pristupas adresi p1)

Druga funkcija kao rezultat vraca pokazivac koji pokazuje na adresu objekta.

 

[ikonoklast]

Koliko ja skontah, u prvom slucaju, **c pokazuje na konkretan element liste, *c sadrzi adresu tog konkretnog elementa liste

Zar ovo nije ista stvar? Kazes da **c pokazuje na element liste, a da *c sadrzi adresu tog elementa. Da bi pokazivac pokazivao na nesto, on mora da sadrzi adresu toga na sta pokazuje, u ovom slucaju elementa liste, jel tako? I onda su, prema ovome sto si napisao *c i **c isti

int prom= 10;
int *p1 = &prom;
int **p2 = &p2;
(da bi pristupio prom pokazivac se mora dva puta dereferencirati, dakle **pp2, dok sa jednim deferenciranjem *p2 pristupas adresi p1)

Kako sa **pp2 mozes da pristupis pom? To bi moglo kada bi stavio: int **pp2=&p1; zar ne ?

Znaci, da sumiramo, **c sadrzi adresu pokazivaca koji pokazuje na zadnji element koji je dodat u listu?

 

[Raptus]

*c i **c verujem da su razlicite stvari u ovom slucaju. Pokazivac *c sadrzi adresu pokazane promenljive, ali to nije isto sto i pokazana promenljiva (u ovom slucaju element liste), (**c).polje bi trebalo da prodje, (*c).polje ne, osim ako ja nisam napravio vecu omasku u rezonovanju, u kojem slucaju se izvinjavam.

 

[genuine]

pokazivaci su najveca glupost izmisljena i zato ih vise nema u modernim jezicima.... a ovo gore je primer
promenljiva generalno ima samo jedno mesto i ono se nalazi u operativnoj memoriji na unapred ( staticki ) ili u toku rada ( dinamicki ) odredjenom mestu... dakle promenljiva je na neki nacin sadrzaj neke memorijske lokacije sa nase strane dok sa strane kompajlera je to samo adresa....
kada dodeljujete nesto promenljivoj vi zapravo u njenu adresu upisujete vrednost koju ste joj namenili , recimo a = 5 ; znaci u operativnu memoriju na adresi koja je dodeljena promenljivoj a upisati 5....
u c programu adresi promenljive pristupamo sa &a
int a;
struct TMojaStruktura struktura;
int *pokazivac;
&a je adresa na kojoj se nalazi broj
&struktura je adresa na kojoj pocinje struktura
&pokazivac je adresa na kojoj se nalazi pokazivac
sve ove adrese su unapred odredjene i odredjuje ih kompajler..... neke od njih kao sto su lokalne se zapravo odredjuju relativno u odnosu na pokazivac vrh steka ali je to opet jednoznacno jer su vidljive samo u bloku u kome su deklarisane...
pored adrese jako je bitno kolika je velicina promenljive... u slucaju int je 4 bajta u slucaju char 1 bajt i sl... kolika je velicina pokazivaca? u zasticenom rezimu win32 je 4 bajta znaci isto kao int... znaci pokazivac je adresa memorijske lokacije na kojoj se nalazi neki broj od 0-2^32-1... taj broj je adresa... adresa cega zavisi od toga kog je tipa pokazivac... dakle svi pokazivaci su jedna te ista stvar bez obzira kako su deklarisani ali sama deklaracija pokazivaca govori o krajnoj odrednici.. ako je pokazivac int *a; onda je to adresa promenljive tipa int.. ako je int **a; mozete da gledate kao (int *)*a; to je adresa nekog drugog pokazivaca i tako redom...

ako je u pitanju deklaracija
int ** a;
tada je &a adresa naseg pokazivaca...
int **a; NIJE DUPLI POKAZIVAC to je samo jedan pokazivac .. pokazivac na nesto sto je tipa
(int *)
a to je nista drugo nego pokazivac na nasu promenlijvu....
dereferenciranje razlikuje od deklaracije pokazivaca...
dereferenciranje znaci uzimanje sadrzaja na koji pokazivac pokazuje..
sta je sadrzaj pokazivaca int **a;?
sadrzaj je adresa nekog drugog pokazivaca...
kog je tipa taj pokazivac?
onog tipa kada u deklaraciji pokazivaca a skinete jednu zvezdicu sa desne strane...
to je nista drugo nego int *

 

[VicTheTrader]

pokazivaci su najveca glupost izmisljena i zato ih vise nema u modernim jezicima.... a ovo gore je primer

Pokazivaci su nesto najbolje sto ozbiljan programer moze da nauci na racunaru. Oni koji ih preskoce pa krenu sa "modernim programskim jezicima" nikada ne shvate kako stvarno rade masine.

 

[ikonoklast]

genuine, hvala, pino si mi pomogao

 

[genuine]

Pokazivaci su nesto najbolje sto ozbiljan programer moze da nauci na racunaru. Oni koji ih preskoce pa krenu sa "modernim programskim jezicima" nikada ne shvate kako stvarno rade masine.

Pa znas kako uvek imas vise nivoa apstrakcije. Recimo kada bih birao da pisem neki normalni program pre bih izabrao javu ili C# nego C++ jednim delom bas zbog tih pokazivaca, alokacije i dealokacije memorije i kojekakvih budalastina koje ti samo oduzimaju i vreme ( da se pakces sa njima ) i paznju jer te skrecu sa glavne teme a to je sustina problema i kako ga resiti.. bas kao sto je nekada bilo

int uradiNestoTesko ( ... ) {
if (greska) return -1;
}
pre izuzetaka

isto glupost da u if mozes da stavis bilo sta i da ce to da prodje bez obzira sto nije boolean tipa ..
koliko je samo bilo curenja memorije zbog budjavih pokazivaca ee...
sto se performansa tice eto recimo DirectX ima za C# pa ima vec i igrica u istom i isto tako ima OpenGL za javu ( JGL)...

dakle sustina je .. dole pokazivaci...

 

[VicTheTrader]

Pa znas kako uvek imas vise nivoa apstrakcije. Recimo kada bih birao da pisem neki normalni program pre bih izabrao javu ili C# nego C++ jednim delom bas zbog tih pokazivaca, alokacije i dealokacije memorije i kojekakvih budalastina koje ti samo oduzimaju i vreme ( da se pakces sa njima ) i paznju jer te skrecu sa glavne teme a to je sustina problema i kako ga resiti.. bas kao sto je nekada bilo

int uradiNestoTesko ( ... ) {
if (greska) return -1;
}
pre izuzetaka

isto glupost da u if mozes da stavis bilo sta i da ce to da prodje bez obzira sto nije boolean tipa ..
koliko je samo bilo curenja memorije zbog budjavih pokazivaca ee...
sto se performansa tice eto recimo DirectX ima za C# pa ima vec i igrica u istom i isto tako ima OpenGL za javu ( JGL)...

dakle sustina je .. dole pokazivaci...

Samo sam hteo da kazem da pokazivaci nisu uopste "glupa" stvar. To sto C nema jake tipove pa svasta prolazi pri kompajliranju je problem (ili nije ) jezika. Naravno da je bolje da imas odradjene stvari kao sto je garbage collector, stek, lancane liste, stabla... implementirane u samom programskom jeziku (bibliotekama) i da se ne bakces sa njima, ali je dobro znati kako mozes da implementiras takve stvari od nule. Dakle jos jednom, pokazivaci jesu opasni i i veoma mocni, ali svakako nisu glupi.

Sve je stvar slobode i odgovornosti - sa pokazivacima ima punu slobodu da radis sta hoces ali je i odgovornost na tebi jer te niko ne sprecava da napravis fatalnu gresku u njihovom koriscenju. Ako vise volis da ti neko govori sta smes a sta ne to je tvoja stvar .

 

[ikonoklast]

Znaci, **c sadrzi adresu pokazivaca koji, opet, sadrzi adresu nekog elementa, tj. pokazuje na njega? I da li se ovo koristi samo kod lista ili u jos nekoj oblasti?

 

[genuine]

Znaci, **c sadrzi adresu pokazivaca koji, opet, sadrzi adresu nekog elementa, tj. pokazuje na njega? I da li se ovo koristi samo kod lista ili u jos nekoj oblasti?

ja izbegavam koriscenje duplih pokazivaca... obicno se koriste kada ti treba velika 2d matrica za koju nemas unapred definisane dimenzije pa moras da je napravis red po red...

int i;
int **matrix;

matrix = (int**)malloc(1000*sizeof (int*));
for (i=0;i<1000;i++)
matrix = (int*) malloc(1000*sizeof(int));

sada ti je matrix[j] jedan element matrice
mada moze i ovako
int *matrix;
matrix = (int*)malloc(8192*8192*sizeof(int));

elementu pristupas sa matrix[ col + row*8192 ]
neko bi rekao da moze i sa matrix [col + (row<<13)] ; // ako se ne varam
problem sa ovim matricama je taj da ako radis sa vise 8 redova istovremeno (recimo (red,neka fiksna kolona ) ) mozes da napravis teske konflikt misseve u kesu.. kod core2duo mozes najvise 8 kod amd-a mislim 4 reda istovremeno ( stim sto kod amd-a je umesto 8k 16k )] odo u offtopik

stvar je da kada punis matricu punis je duz reda prolazeci kroz sve kolone da ne bi napravio sve moguce osim coherence miseva u kesu... a kako je punis to je najbitnije
ne punis je sa
recimo
for (i=0;i<8192;i++)
matrix[col+ (row<<13) ] = x ;
zato sto imas jedno siftovanje i jedno sabiranje viska
punis je sa
int *rowMatrix = matrix[row<<13];
for (i=0;i<1024;i++)
rowMatrix = x;
zaboravio sam da li je u c-u dozvoljena aritmetika sa pointerima i uporedjivanje ali mozda bi moglo i
for (rowMatrix=matrix[row<<13];rowMatrix<matrix[row<<14];rowMatrix++) {
rowMatrix = x;
ako ovo gore ne moze onda sigurno moze
for (rowMatrix=matrix[row<<13];(long)rowMatrix<(long)(matrix[row<<14]);rowMatrix++) {
rowMatrix = x;

kada pokazivacu kazes ++ na primer rowMatrix++; ti si uradio sledece
adresa na koju pokazuje rowMatrix uvecana je velicinu tipa na koju pokazuje.. recimo kod nas je to int ...

ako hocete jos mogu da nastavim
valjda nisam izgresio previse

 

[VicTheTrader]

Znaci, **c sadrzi adresu pokazivaca koji, opet, sadrzi adresu nekog elementa, tj. pokazuje na njega? I da li se ovo koristi samo kod lista ili u jos nekoj oblasti?

Recimo ako hoces da kreiras objekat u nekoj funkciji ali zelis i da vratis rezultat operacije:

struct a
{
int x;
};

int KreirajObjekat(struct a** ppa)
{
*ppa = (struct a*)malloc(sizeof(struct a));
if (*ppa == NULL) return 1;
*ppa->x = 3;
return 0;
}
Ovo je moglo i direktno kao struct a * KreirajObjekat() ali ako imas vise argumenata funkcije onda mora preko dvostrukog pokazivaca.

 

[ikonoklast]

ali ako imas vise argumenata funkcije onda mora preko dvostrukog pokazivaca.

Ne mora, moze npr. :
ovo je dodavanje novog elementa na ocetak liste:

Cvor *na_poc (Cvor *p, int b)
{ Cvor *novi=(Cvor * ) malloc (sizeof(Cvor));
novi->broj=b;
novi->sl=p;
p=novi;
return p; }

 

[genuine]

Ne mora, moze npr. :
ovo je dodavanje novog elementa na ocetak liste:

Cvor *na_poc (Cvor *p, int b)
{ Cvor *novi=(Cvor * ) malloc (sizeof(Cvor));
novi->broj=b;
novi->sl=p;
p=novi;
return p; }

slazem se, mnogo je prirodnije.. lici na konstruktor
ima samo jedna stvar koju nisi predvideo... malloc moze da vrati null

 

[ikonoklast]

ima samo jedna stvar koju nisi predvideo... malloc moze da vrati null

Da, samo ne znam u kom slucaju vraca null?

 

[zeleni_zub]

Da, samo ne znam u kom slucaju vraca null?

Vraća NULL ako ne uspe da rezerviše memoriju (ako nema dovoljno slobodne memorije).

 

[Blackmore]

Potrebno je javiti korisniku da nije uspela alokacija memorije!
Dakle, nesto kao

zauzimanje = malloc...
if(zauzimanje==null) printf("Neuspela alokacija memorije");

Takodje, na kraju, oslobodi zauzetu memoriju kad ti ne treba vise, naredbom free..

 

[Caslav]

Matrice je najbolje praviti tako što se rezerviše jedan m x n niz za podatke, i jedan m niz za pokazivače na početke vrsta, i onda ih uvezati:

double *data = (double) malloc(m * n * sizeof(double));
double **mat = (double *) malloc(m * sizeof(double *));
for (i = 0; i < m; ++i)
    mat[i] = data + i * n;

Ovako je osigurano da su elementi matrice u neprekidnom poretku u memoriji, a zadržana je mogućnost dvoindeksiranja:

for (i = 0; i < m; ++i)
    for (j = 0; j < n; ++j)
        mat[i][j] = x;

Dodatan bonus je i što onda matrica može da se oslobodi bez poznavanja dimenzija:

free(mat[0]);
free(mat);

 

[genuine]

fino resenje ali ima penal u performansama.. da bi pristupio elementu [a,b] treba da dohvatim jedan pokazivac na red pa preko njega da dobijem adresu polja.. dupli posao samo zbog elegantnijeg zapisa [][]
koliko sam ja video u praksi je bas teznja da se matrice fiksiraju, tj. da se unapred zna velicina istih i da se prema tome programira.
sve sto je poznato tek u run-time-u se mnogo teze optimizuje posebno sada u eri visejezgarnih procesora

 

[Caslav]

fino resenje ali ima penal u performansama..

Nema penala u performansama, barem ne na modernim platformama (procesor+kompilator).

Čak naprotiv, ako se nekako „domišljato“ pristupa elementima matrice, kompilator može da se zbuni i ne optimizuje za dobar pristup memoriji. U prilogu je jedan jednostavan program, kome sam dodao makroe za dvoindeksni (-D_MAT_DBLIND) i računsko-indeksni pristup (-D_MAT_CMPIND). Rezultati sa GCCom 4.1.1 i Intelom 9.1, na P4 2,8 GHz:

$ --------------------
$ gcc -Wall -O3 -march=pentium4 -lm -D_MAT_DBLIND main.c
$ time ./a.out
L2: 1.122e-04

real    0m10.831s
user    0m10.053s
sys     0m0.095s
$ 
$ --------------------
$ gcc -Wall -O3 -march=pentium4 -lm -D_MAT_CMPIND main.c
$ time ./a.out
L2: 1.122e-04

real    0m13.355s
user    0m12.301s
sys     0m0.107s
$ 
$ --------------------
$ icc -Wall -O3 -march=pentium4 -lm -D_MAT_DBLIND main.c
main.c(34) : (col. 9) remark: LOOP WAS VECTORIZED.
main.c(47) : (col. 5) remark: LOOP WAS VECTORIZED.
main.c(49) : (col. 5) remark: LOOP WAS VECTORIZED.
main.c(60) : (col. 13) remark: LOOP WAS VECTORIZED.
main.c(66) : (col. 9) remark: LOOP WAS VECTORIZED.
$ time ./a.out
L2: 1.122e-04

real    0m6.411s
user    0m5.901s
sys     0m0.068s
$
$ --------------------
$ icc -Wall -O3 -march=pentium4 -lm -D_MAT_CMPIND main.c
main.c(43) : (col. 5) remark: LOOP WAS VECTORIZED.
main.c(45) : (col. 5) remark: LOOP WAS VECTORIZED.
$ time ./a.out
L2: 1.122e-04

real    0m11.359s
user    0m9.931s
sys     0m0.114s
$

Vidi se da sa računatim indeksom programu treba nekih 25% više vremena sa GCCom, ili čak 65% više vremena sa Intelovim kompilatorom. Posebno, Intel ispisuje kada je uspeo da vektorizuje petlje (za SSE jedinice na P4), i vidi se da u slučaju računatog indeksa nije skontao da može da vektorizuje ključnu petlju (onu u liniji 60).

 

[genuine]

e.. sad sam malo bolje razmislio i skroz si u pravu... ne samo sto se tice paralelizacije vec u samoj osnovi
kada pristupam redu kompletno kompajler ga iskompajlira tako da uzme pokazivac na red i onda samo cepa elemente jedan za drugom.. u slucaju sa racunanjem indeksa on nepotrebno vrsi mnozenje....
priznajem Bolje Je . cak i veoma glup kompajler to moze da provali

 

[Caslav]

Nemoj tako brzo da se slažeš Kad sam malo bolje razmislio, nema zapravo razloga zašto bi verzija sa računatim indeksom bila sporija (ili brža). I kad se radi sa dva indeksa, u suštini u pozadini mora da se obavi isti račun.

Stvar je u tome što sam zabrljao redosled indeksa pri računanju zbirnog indeksa, tako da je ovaj gore program efektivno radio sa transponovanom matricom. Kad sam to ispravio, obe verzije indeksiranja daju istu brzinu. Mada, Intel i dalje nije vektorizovao ovu petlju sa računatim indeksom, ali se to sada nije odrazilo na brzinu (valjda jer je matrica prevelika da stane u keš, pa je ionako pristup memoriji usko grlo).

 

[genuine]

ja sam konkretno mislio na sledecu situaciju :

onaj kod sa dva indeksa bi kompajler mogao ovako da optimizuje za pristup redu cime nema mnozenja...
float **matrix;
float *pRow = matrix[1];

for (int i=0;i<100;i++ )
pRow = sin(i);

e sad pitanje je cemu se cesce pristupa .. ako je sa redovima ja bi eksplicitno koristio kod gore... ako je sa kolonama onda bi koristio onaj tipa matrix[x + y*columns] ili ako moze jos bolje matrix[x + y<<columnsShift] posto neki procesori imaju jednu instrukciju za racunanje x + y<<colShl kao sto je ARM procesor
p.s.
mislio sam na razlicite kolone.. za istu kolonu je najjednostavnije
float *matrix;

float *col = &matrix[x + y<<colSHL ];

for (int i =0 ; i< 128;i++) {
*col = sin(i);
col += 128
}

pretpostavka je 128x128 matrica