Imperatív programozás 10.
Típusabsztrakció
Komponensek
Nagy programok esetében nem reális, hogy az elejétől a végéig minden részét mi írjuk meg. Ez részben igen sok munkaóra lenne (ne csak a fejlesztési időt, hanem a tesztelést, és a későbbi karbantartást is vegyük figyelembe), részben pedig felesleges is: nagy valószínűséggel számos komponensre másoknak is szüksége volt már, és ezek a komponensek léteznek.
A többszöri újrafelhasználásra szánt szoftver-komponenseket könyvtárak-nak (library) nevezzük. A legtöbb programozási nyelv rendelkezik egy olyan szabványos könyvtárral (standard library), ami a legalapvetőbb funkcionalitást biztosítja: input/output, string műveletek, alapvető matematikai műveletek, stb. Ezen felül egyes nyelvek számos további szolgáltatást biztosíthatnak: a C++ STL szabványos adatszerkezeteket és rajtuk végrehajtható általános algoritmusokat szolgáltat, a Java nagyszámú könyvtára között pedig grafikus interfészt, adatbázis- és hálózatkezelést és rengeteg más komponenst találunk. A C nyelv szabványos könyvtára a kisebbek közé tartozik.
A könyvtárak megjelenési formája gyakran a nyelv által támogatott programozási paradigmától függ: Java-ban, C#-ban gyakran osztálykönyvtárakként valósulnak meg, C++-ban sokszor template osztályok és függvények. A procedurális C-ben, többnyire függvénykönyvtárakat találunk. Azt a kódot, amelyik felhasználja a könyvtárat, felhasználói, vagy kliens kódnak nevezzük.
Interfész és implementáció
Egy (akár hardver- akár szoftver-) komponens pontosan meghatározott módon kell kommunikáljon az őt használó többi komponenssel. Fontos, hogy ezen a felületen kívül ne lehessen elérni a komponens belsejét. Ezt a felületet a komponens interfészének (interface) nevezzük. Az interfész egyfajta szerződés a komponens (létrehozója) és az azt használók (szoftverek) között: a komponens ezen keresztül garantál egy funkcionalitást, amire a felhasználók (szoftverek) építhetnek. Másrészről, mivel a kliensek csak ezen a felületen keresztül érhetik el a szolgáltatásokat, azok megvalósítása, azaz az implementáció (implementation) teljes egészében a komponens megvalósítójának kezében van, azon szükség esetén (bizonyos kereteken belül) módosíthat is.
Az interfész sokféle összetevőből állhat: konstansok, adattípusok, függvények, kivételek akár még változók is. Az alábbi példában egy dátum komponens látható.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct date
{
int year;
int month;
int day;
};
void f(void)
{
/* mezőnkénti inicializálás */
struct date exam = { 2019, 12, 17};
++exam.day; /* egy nappal elhalasztva */
exam.day += 40; /* valószínűleg hiba */
}
Ha van valamilyen komponens szintű állandó, akkor azt nyugodtan definiálhatjuk csak olvasható (constant, immutable) változónak. Amennyiben azonban írható/olvasható változóink vagy adattagjaink vannak, akkor nehéz megakadályozni, hogy a kliens hibás adatot (január 42-e, vagy február 30-a) állítson be. Ezért gyakoribb, hogy az interfészben változók helyett alprogramok-at (függvény, metódus, property) használunk.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct date
{
int year;
int month;
int day;
};
void f(void)
{
/* inicializálás, ellenőrzi az egyes mezők értékeit */
struct date exam = dateCreate(2019, 12, 17);
dateNext(&exam); /* egy nappal elhalasztva */
dateAdd(&exam,40); /* lekezeli a hónap végét */
}
Egy eljárás, mint az dateAdd() ellenőrizni tudja a paramétereit, illetve a dátum szemantikájának megfelelően hajtja végre a növelést, pl. növeli a hónap vagy év értékét is. A fent C példában azért adtuk át az interfész függvényeknek a dátum objektum címét, mert csak így tudjuk módosítani magát az objektumot.
A klienssel közölni kell, hogy milyen módon tudja használni a könyvtárat. Ez alapján a fordítóprogram képes (valamilyen szinten) ellenőrizni ezt a használatot és jelzi, ha valahol eltértünk a megfelelő módtól. Ez java-ban az import, C#-ban a use utasítással történik. C-ben és C++-ban a felhasználni kívánt könyvtár headerének include-ja segítségével tesszük meg.
Megjegyzések
-
Példa az implementáció/interfész szétválasztására: A UNIX operációs rendszert pl. csak a megfelelő rendszerhívásokon keresztül lehet elérni. Ez egy hosszútávon stabil felület, akár 20-30 évvel ezelőtt megírt rendszerprogramok is lefordulnak és futnak. Másrészt a rendszerhívások mögött a javítások, fejlesztések folyamatosak lehetnek.
-
A C és C++ nyelvekben egy komoly korlát lehet a bináris kompatibilitás megőrzése, amire akkor van szükség, ha dinamikus szerkesztésű programok esetén megváltoztatjuk a könyvtárat. Ennek az oka a C és C++ nyelvek érték szemantikája, azaz a kliensnek pl. tudnia kell, hány bájt méretű egy változó vagy függvényparaméter. ha pl. a fenti programban megváltozik a struct date struktúra szerkezete, akkor nem csak a dátum komponenst, hanem a dátumot felhasználó kliens programokat is újra kell fordítani.
Egységbezárás
A fenti dátum példához megadhatunk egy teljes értékű interfészt, ami alapján a kliens programok a teljes funkcionalitást fel tudják használni. De hogyan tudjuk megakadályozni, hogy a kliens az interfészt megkerülve közvetlenül elérje az implementációt?
Azokat a programnyelvi mechanizmusokat, amelyek az implementáció elérését megakadályozzák és rákényszeríti a klienst az interfész felhasználására kényszeríti, egységbezárás-nak (enkapszuláció, encapsulation, information hiding) nevezzük.
A különböző programozási paradigmák eltérő eszközöket adnak és az egyes
nyelvek is eltérő mélységben támogatják ezeket. Az objektum-orientált
nyelvekben pl. az adattagok és metódusok elérési jogai (access modifiers)
(pl. public, protected, private) teszik lehetővé az információ elrejtését.
A class private vagy protected neveit nem érhetjük el az osztályon
kívülről, az fordítási időben szintaktikus hibát okoz.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Ez C++ kód
class date
{
public:
date(int y, int m, int d); /* konstruktor */
void set(int y, int m, int d); /* módosító tagfv-ek */
void next();
void add(int n);
int getYear() const; /* csak olvasó tagfüggvények */
int getMonth() const;
int getday() const;
date &operator++(); /* módosító operátorok */
date operator++(int);
date &operator+=(int);
private: /* adattagok */
int year;
int month;
int day;
};
/* globális operátor, de ugyancsak az interfész része */
std::ostream& operator<<(std::ostream& os, const date& d);
void f()
{
date exam(2018,12,15); /* konstruktor: inicializálás */
exam.set(2018,12,17); /* dátum beállítása dec. 17-re */
exam.next(); /* egy nappal elhalasztva */
exam.add(40); /* lekezeli a hónap végét */
std::cout << exam.getDay(); /* ok, 17-e kiírása */
exam.day += 40; /* syntax error: day is private */
std::cout << exam << '\n'; /* a teljes dátum kiírása */
}
Enkapszuláció C-ben
Az alábbiakban elkészítjük a fenti dátum típus C implementációját. A modul interfésze a date.h headerfájl lesz, ezt kell majd a klienseknek include-olniuk, ha használni akarják a könyvtárat. Az implementáció nagy része a date.c állományba kerül, ezt hozzá kell szerkeszteni (statikusan vagy dinamikusan) a dátumot felhasználó kliens programokhoz.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* date.h */
#ifndef DATE_H
#define DATE_H
#define EOK 0 /* ok */
#define ENOMEM 1 /* unable to allocate memory */
#define EINVALID 2 /* invalid date */
#define ENEGDAY 3 /* negative day for dateAdd */
struct DATE;
typedef struct DATE *date_t; /* forward deklaráció */
extern int dateError; /* error handling */
date_t dateCreate( int y, int m, int d);
void dateDestroy(date_t dp);
int dateSet( date_t dp, int y, int m, int d);
void dateNext( date_t dp);
int dateAdd( date_t dp, int n);
int dateGetYear(date_t dp);
int dateGetMonth(date_t dp);
int dateGetDay(date_t dp);
#endif /* DATE_H */
Az implementáció a date.c fájlba kerül. Itt hozzuk létre az interfész függvényeket, de itt definiálhatunk az interfészbe nem tartozó elemeket is: segédfüggvényeket és adatszerkezeteket. Ezeket, hogy a külvilág ne láthassa static függvényként vagy adatként definiáljuk.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/* date.c */
#include <stdio.h>
#include <stdlib.h>
#include "date.h"
struct DATE
{
int year;
int month;
int day;
};
/* napok száma az adott hónapban, kiv. szökőév */
static const int dOfm[] = {
31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
/* y szökőév? */
static int leapYear( int y)
{
/* TODO implementálni!!! */
return 0;
}
/* napok tényleges száma az év/hónapban */
static int daysOfMonth( int y, int m)
{
int maxDay = dOfm[m-1]; /* tömb 0-tól indexelődik */
if ( 2 == m && leapYear(y) )
++maxDay; /* szökőév */
return maxDay;
}
/* helyes dátum-e az (y, m, d) hármas? */
static int checkDate(int y, int m, int d)
{
return 0 != y &&
1 <= m && m <= 12 &&
1 <= d && d <= daysOfMonth(y, m);
}
/* interfész: hibakezelés */
int dateError = EOK;
/* interfész függvények */
date_t dateCreate( int y, int m, int d)
{
date_t dp;
if ( ! checkDate( y, m, d) )
{
dateError = EINVALID;
return NULL;
}
if (NULL == (dp = (date_t) malloc(sizeof(struct DATE)) ))
{
dateError = ENOMEM;
return NULL;
}
dp->year = y;
dp->month = m;
dp->day = d;
dateError = EOK;
return dp;
}
void dateDestroy( date_t dp)
{
free(dp);
}
int dateSet( date_t dp, int y, int m, int d)
{
if ( ! checkDate( y, m, d) )
{
dateError = EINVALID;
return 0;
}
dp->year = y;
dp->month = m;
dp->day = d;
dateError = EOK;
return 1;
}
int dateGetYear( date_t dp)
{
dateError = EOK;
return dp->year;
}
int dateGetMonth( date_t dp)
{
dateError = EOK;
return dp->month;
}
int dateGetDay( date_t dp)
{
dateError = EOK;
return dp->day;
}
void dateNext( date_t dp)
{
++dp->day;
if ( dp->day > daysOfMonth( dp->year, dp->month) )
{
dp->day = 1;
++dp->month;
if ( 13 == dp->month )
{
dp->month = 1;
++dp->year;
if ( 0 == dp->year )
{
++dp->year;
}
}
}
dateError = EOK;
}
int dateAdd( date_t dp, int n)
{
int i;
if ( n < 0 )
{
dateError = ENEGDAY;
return 0;
}
for ( i = 0; i < n; ++i )
{
dateNext( dp);
}
dateError = EOK;
return 1;
}
A főprogramban az interfész függvényeket hívjuk, létrehozunk egy dátumot, módosítjuk, illetve kiírjuk az értékeit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* main.c */
#include <stdio.h>
#include "date.h"
int main()
{
date_t exam = dateCreate(2018, 12, 17);
if ( ! exam )
{
return 1;
}
printf( "Eredeti vizsgadatum = (%d, %d, %d)\n",
dateGetYear(exam),
dateGetMonth(exam),
dateGetDay(exam));
dateNext(exam);
printf( "Vizsgadatum + 1 = (%d, %d, %d)\n",
dateGetYear(exam),
dateGetMonth(exam),
dateGetDay(exam));
dateAdd(exam, 40);
printf( "Elhalasztott vizsga = (%d, %d, %d)\n",
dateGetYear(exam),
dateGetMonth(exam),
dateGetDay(exam));
dateDestroy(exam);
return 0;
}
A forrásfájlokat egymástól függetlenül fordíthatjuk le, majd statikusan vagy dinamikusan össze kell szerkeszteni őket.
$ gcc -c -Wall -Wextra -c date.c
$ gcc -c -Wall -Wextra -c main.c
$ gcc date.o main.o -o examsFuttatjuk a programot.
$ ./exams
Eredeti vizsgadatum = (2018, 12, 17)
Vizsgadatum + 1 = (2018, 12, 18)
Elhalasztott vizsga = (2019, 1, 27)Vector típus implementációja
A következő példa egy dinamikusan növekvő vektor típus megvalósítása, hasonló, mint ami a C++ standard könyvtár std::vector típusa. C++-ban valahogy így szeretnénk használni a vector osztályt stringekkel:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Ez C++ kód
#include <iostream> // szabványos C++ input-output
#include <vector> // vector könyvtári típus
#include <string> // string könyvtári típus
template <typename T>
void print(char *name, std::vector<T> v)
{
std::cout << name << " == ";
for (unsigned int i = 0; i < v.size(); ++i)
{
std::cout << v[i] << " ";
}
std::cout << '\n';
}
int main()
{
std::vector<std::string> v1;
v1.push_back("Alma");
v1.push_back("Barack");
v1.push_back("Korte");
v1.push_back("Szilva");
v1.push_back("Szolo");
v1[1] = "Kajszi";
print("v1",v1);
std::vector<std::string> v2;
v2.push_back("Ringlo");
print("v2", v2);
v2 = v1;
print("v2", v2);
return 0;
} // a v2 és v1 destruktora itt meghívódik
A C nyelvben nem tudunk ilyen szép interfészt létrehozni, de bizonyos kompromisszumokkal azért tudunk hasonló funkcionalitást megvalósítani. Az std::vector interfészét kissé leegyszerűsítettük. Ezek után ez lesz a megvalósítandó funkcionalitás:
- Létre tudunk hozni egy üres vektort (vectorCreate)
- Be tudunk szúrni egy új elemet a vektor végére (vectorPushBack)
- Törölhetjük a vektor utolsó elemét (vectorPopBack)
- Írhatjuk a vektor i-edik elemét, ha i kisebb, mint a méret (vectorSet)
- Olvashatjuk a vektor i-edik elemét, ha i kisebb, mint a méret (vectorGet)
- Lekérdezhetjük a vektor elemeinek számát (vectorSize)
- Lekérdezhetjük az implementációs buffer méretét (vectorCapacity)
- Törölhetjük a vektort, annak tartalmával együtt (vectorDestroy)
- Átmásolhatjuk a vektor tartalmát egy másik vektorba (vectorCopy)
A hibaüzeneteket a vectorErrno globális változóból tudjuk kiolvasni.
A felhasználó például így szeretné használni a vector könyvtárat C-ben:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include "vector.h"
void print(char *name, vector_t v)
{
printf("%s == ", name);
for (int i = 0; i < vectorSize(v); ++i)
{
printf("%s ", vectorGet(v,i));
}
putchar('\n');
}
int main()
{
vector_t v1 = vectorCreate();
vectorPushBack( v1, "Alma");
vectorPushBack( v1, "Barack");
vectorPushBack( v1, "Korte");
vectorPushBack( v1, "Szilva");
vectorPushBack( v1, "Szolo");
vectorSet( v1, 1, "Kajszi");
print("v1",v1);
vector_t v2 = vectorCreate();
vectorPushBack( v2, "Ringlo");
print("v2", v2);
vectorCopy(v2,v1);
print("v2", v2);
vectorDestroy(v1);
vectorDestroy(v2);
return 0;
}
A fenti program lefutása az alábbi eredményt kell szolgáltassa:
$ gcc -Wall -Wextra vmain.c vector.c
$ ./a.out
v1 == Alma Kajszi Korte Szilva Szolo
v2 == Ringlo
v2 == Alma Kajszi Korte Szilva Szolo Az implementáció a dátum típuséhoz hasonló lesz. A felhasználó egy vector_t handler-t fog kapni, ami egy elrejtett szerkezetű, a szabad memóriában lefoglalt struktúrára mutat. Ez a struktúra egy ugyancsak a szabad memóriábn lefoglalt és szükség szerint realloc segítségével megnövelt bufferre hivatkozik a ptr pointeren keresztül.
A buffer pillanatnyi méretét a capacity mező tartalmazza. A bufferben karakterre mutató pointerek vannak és hivatkoznak a vektorban elhelyezett stringekre. A stringek számára persze ugyancsak saját memóriát kell lefoglalnunk.
A bufferben size string(-re hivatkozó) pointer lesz. Ha a buffer megtelik, azaz size == capacity akkor realloc segítségével megnöveljük. Ilyenkor a stringeket magukat nem kell másolni, mert a rájuk mutató pointer másolódott.
A vector.h fogja tartalmazni az interfészt. Lényegében egy headerfájl, ami az interfész függvények és a típusra specifikus konstansok deklarációja.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef VECTOR_H
#define VECTOR_H
#define VEC_EOK 0 /* nincsen hiba */
#define VEC_ENOMEM 1 /* elfogyott a memoria */
#define VEC_EINDEX 2 /* érvénytelen index */
#define VEC_EEMPTY 3 /* üres a vector */
struct VECTOR; /* csak forward deklaráció */
typedef struct VECTOR *vector_t;
extern int vectorErrno; /* hibakód számára */
extern vector_t vectorCreate();
extern void vectorDestroy( vector_t);
extern int vectorSize( vector_t v);
extern int vectorCapacity( vector_t v);
extern int vectorCopy( vector_t target, vector_t source);
extern int vectorSet( vector_t v, int idx, const char *s);
extern char *vectorGet( vector_t v, int idx);
extern int vectorPushBack( vector_t v, const char *s);
extern int vectorPopBack( vector_t v);
#endif /* VECTOR_H */
Az implementációt a vector.c forrásfájlban helyezzük el.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdlib.h>
#include <string.h>
#include "vector.h"
#define INIT_CAP 4 /* az első buffer-méret */
struct VECTOR
{
int capacity_; /* buffer mérete (elemszám) */
int size_; /* aktuális elemek száma */
char **ptr_; /* pointer a bufferre */
};
int vectorErrno; /* ide írjuk a hibakódot */
vector_t vectorCreate()
{
vector_t v = (vector_t) malloc(sizeof(struct VECTOR));
if ( NULL == v )
{
vectorErrno = VEC_ENOMEM;
return NULL;
}
v->capacity_ = INIT_CAP;
v->size_ = 0;
v->ptr_ = (char **)malloc(INIT_CAP*sizeof(char*));
if ( NULL == v->ptr_ )
{
vectorErrno = VEC_ENOMEM;
return NULL;
}
vectorErrno = VEC_EOK;
return v;
}
static void freeElems( vector_t v)
{
int i;
for ( i = 0; i < v->size_; ++i)
{
free(v->ptr_[i]);/* felszabadítani a tárolt elemeket */
}
free(v->ptr_); /* felszabadítani a pointer buffer-t */
}
void vectorDestroy( vector_t v)
{
freeElems(v); /* felszabadítani a buffer-t és elemeket */
free(v); /* felszabadítani a struct VECTOR-t */
vectorErrno = VEC_EOK;
return;
}
int vectorCapacity( vector_t v)
{
vectorErrno = VEC_EOK;
return v->capacity_;
}
int vectorSize( vector_t v)
{
vectorErrno = VEC_EOK;
return v->size_;
}
static int vectorGrowBuffer( vector_t v)
{
int newCapacity = 2*v->capacity_;
char **oldPtr = v->ptr_;
char **newPtr =
(char **) realloc(oldPtr, newCapacity*sizeof(char *));
if ( NULL == newPtr )
{
vectorErrno = VEC_ENOMEM;
return 0;
}
v->capacity_ = newCapacity;
v->ptr_ = newPtr;
return 1;
}
int vectorPushBack( vector_t v, const char *s)
{
if ( v->size_ == v->capacity_ ) /* nincs üres hely */
{
if ( ! vectorGrowBuffer(v) )
return 0;
}
++v->size_;
v->ptr_[v->size_-1] = NULL; /* vectorSet will use it */
vectorSet( v, v->size_-1, s);
vectorErrno = VEC_EOK;
return 1;
}
int vectorPopBack( vector_t v)
{
if ( v->size_ == 0 ) /* a vector üres */
{
vectorErrno = VEC_EEMPTY;
return 0;
}
free( v->ptr_[v->size_-1]);
--v->size_;
vectorErrno = VEC_EOK;
return 1;
}
int vectorSet( vector_t v, int idx, const char *s)
{
char *ptr;
if ( idx < 0 || idx >= v->size_ )
{
vectorErrno = VEC_EINDEX;
return 0;
}
if ( NULL == (ptr = (char*)malloc( strlen(s)+1 )) )
{
vectorErrno = VEC_ENOMEM;
return 0;
}
strcpy( ptr, s);
free(v->ptr_[idx]);
v->ptr_[idx] = ptr;
vectorErrno = VEC_EOK;
return 1;
}
char *vectorGet( vector_t v, int idx)
{
if ( idx < 0 || idx >= v->size_ )
{
vectorErrno = VEC_EINDEX;
return "";
}
vectorErrno = VEC_EOK;
return v->ptr_[idx];
}
int vectorCopy( vector_t target, vector_t source)
{
if ( target != source ) /* elkerülni v1 = v1 -et */
{
int i;
freeElems(target); /* felszámolni a régi elemeket */
target->capacity_ = source->size_; /* csökkenhet */
target->size_ = source->size_;
target->ptr_ = (char **)
malloc(target->capacity_*sizeof(char**));
if ( NULL == target->ptr_ )
{
vectorErrno = VEC_ENOMEM;
return 0;
}
for (i = 0; i < target->size_; ++i)
{
int len = strlen(source->ptr_[i]);
if( NULL == (target->ptr_[i]=(char*)malloc(len+1)) )
{
vectorErrno = VEC_ENOMEM;
return 0;
}
strcpy( target->ptr_[i], source->ptr_[i]);
}
}
vectorErrno = VEC_EOK;
return 1;
}
Megjegyzés C-ben a realloc() és a memcpy() függvények tökéletesek arra, hogy a (régi vagy forrás) buffer tartalmát átmásoljuk az (új vagy cél) bufferba. Ez azonban feltételezi hogy a bufferünkben egyszerű, bájtonként másolható objektumok vannak. Ilyen az int, a double vagy akár a struct date is. Azonban, ha pl. olyan objektumok vannak a bufferben, amelyek maguk is tartalmaznának pl. pointert, akkor ez már nem működik, hiszen a pointer bájtonkénti átmásolása shallow copy-t eredményezne. Erre majd különösen vigyáznunk kell C++ template-ek esetében, ezért ott a másolást a mostanihoz hasonló ciklussal kell elvégezni.
Generikus típusok
A fenti megoldás a string vektorok egy megfelelő megvalósítása. Mi lesz azonban a többi típussal. Hogyan tudjuk általánosítani a megoldásunkat?
-
Példányosítás: Újabb típusok generálása. Így működnek a C++ template-ek, de erre nincsen jó mechanizmus C-ben. Szimulálhatjuk preprocesszor varázslással.
-
Típustörlés: Minden típust ugyanaz a kódpéldány szolgál ki. Így működik a Java Generic. Ezt közelítjük az alábbi C megoldással.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <string.h>
#include "vector.h"
void copyDouble(void *tgt, void *src)
{
memcpy(tgt,src,sizeof(double));
}
int main()
{
int i;
vector_t vec1 = vectorCreate(sizeof(double),copyDouble); /* vector_t vec1; */
vector_t vec2 = vectorCreate(sizeof(double),copyDouble); /* vector_t vec2; */
vector_t vec3 = vectorCreate(sizeof(double),copyDouble); /* vector_t vec3; */
printf( "vec1 cap. = %lu\n", vectorCapacity( vec1)); /* vec1.capacity() */
printf( "vec1 size = %lu\n", vectorSize(vec1)); /* vec1.size() */
for(i = 0; i < 100; ++i)
{
double d = i*i;
vectorPushBack( vec1, &d); /* vec1.push_back(i) */
}
printf( "vec1 cap. = %lu\n", vectorCapacity( vec1)); /* vec1.capacity() */
printf( "vec1 size = %lu\n", vectorSize( vec1)); /* vec1.size() */
printf( "vec1[42] = %f\n",*(double*)vectorAt(vec1,42)); /* vec1[42] */
vectorCopy( vec2, vec1); /* vec2 = vec2 */
*(double*)vectorAt( vec2, 42) = 99.99; /* vec[2] = 99.99 */
printf( "vec1[42] = %f\n",*(double*)vectorAt(vec1,42));/* vec1[42] 1764.00 */
printf( "vec2[42] = %f\n",*(double*)vectorAt(vec2,42));/* vec2[42] 99.99 */
vectorPopBack( vec2); /* vec2.pop_back() */
printf( "vec2 cap. = %lu\n", vectorCapacity( vec2)); /* vec2.capacity() */
printf( "vec2 size = %lu\n", vectorSize( vec2)); /* vec2.size() */
vectorMove( vec3, vec1); /* vec3 = move(vec1) */
printf( "vec3 size = %lu\n", vectorSize( vec3)); /* vec3.size() */
printf( "vec1 size = %lu\n", vectorSize( vec1)); /* vec1.size() */
vectorDestroy( vec1); /* destructor */
vectorDestroy( vec2); /* destructor */
vectorDestroy( vec3); /* destructor */
return 0;
}
A módosított interfész:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#ifndef VECTOR_H
#define VECTOR_H
#include <stddef.h>
#define VEC_EOK 0
#define VEC_ENOMEM 1
#define VEC_EINDEX 2
#define VEC_EEMPTY 3
struct VECTOR_S;
typedef struct VECTOR_S *vector_t;
typedef void (*elem_copy_t)(void *tgt, void *src);
extern int vectorErrno;
extern vector_t vectorCreate( size_t esize, elem_copy_t cpyfunc);
extern void vectorDestroy( vector_t);
extern size_t vectorSize( vector_t v);
extern size_t vectorCapacity( vector_t v);
extern vector_t vectorCopy( vector_t target, vector_t source);
extern vector_t vectorMove( vector_t target, vector_t source);
extern void *vectorAt( vector_t v, size_t idx);
extern void vectorPushBack( vector_t v, void *src);
extern void vectorPopBack( vector_t v);
#endif /* VECTOR_H */
A megvalósítás:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include "vector.h"
#define INIT_CAPACITY 4
struct VECTOR_S
{
size_t capacity_;
size_t size_;
char *ptr_;
size_t esize_;
elem_copy_t cpyfun_;
};
int vectorErrno;
static int vectorGrowBuffer( vector_t v)
{
size_t i;
size_t newCapacity = v->capacity_ ? 2*v->capacity_
: INIT_CAPACITY;
char *oldPtr = v->ptr_;
char *newPtr = malloc(newCapacity * v->esize_);
if ( NULL == newPtr )
{
vectorErrno = VEC_ENOMEM;
return 0;
}
for (i = 0; i < v->size_; ++i)
{
v->cpyfun_( newPtr+(i*v->esize_), oldPtr+(i*v->esize_));
}
v->capacity_ = newCapacity;
v->ptr_ = newPtr;
free(oldPtr);
return 1;
}
vector_t vectorCreate( size_t esize, elem_copy_t cpyfun)
{
vector_t v = (vector_t) malloc(sizeof(*v));
if ( NULL == v )
{
vectorErrno = VEC_ENOMEM;
return NULL;
}
v->capacity_ = 0;
v->size_ = 0;
v->ptr_ = NULL;
v->esize_ = esize;
v->cpyfun_ = cpyfun;
vectorErrno = VEC_EOK;
return v;
}
void vectorDestroy( vector_t v)
{
free(v->ptr_);
free(v);
vectorErrno = VEC_EOK;
return;
}
size_t vectorCapacity( vector_t v)
{
vectorErrno = VEC_EOK;
return v->capacity_;
}
size_t vectorSize( vector_t v)
{
vectorErrno = VEC_EOK;
return v->size_;
}
vector_t vectorCopy( vector_t target, vector_t source)
{
if ( target != source )
{
free(target->ptr_);
target->capacity_ = source->size_; /* esetleg csökken */
target->size_ = source->size_;
target->cpyfun_ = source->cpyfun_;
if ( source->size_ > 0 )
{
size_t i;
size_t esz = source->esize_;
target->ptr_ = malloc(target->capacity_ * esz);
if ( NULL == target->ptr_ )
{
vectorErrno = VEC_ENOMEM;
return NULL;
}
for (i = 0; i < target->size_; ++i)
source->cpyfun_( target->ptr_+i*esz, source->ptr_+i*esz);
}
else
{
target->ptr_ = NULL;
}
}
vectorErrno = VEC_EOK;
return target;
}
extern vector_t vectorMove( vector_t target, vector_t source)
{
if ( target != source )
{
free(target->ptr_);
target->capacity_ = source->capacity_;
target->size_ = source->size_;
target->ptr_ = source->ptr_; /* move */
source->capacity_ = 0;
source->size_ = 0;
source->ptr_ = NULL;
}
vectorErrno = VEC_EOK;
return target;
}
void *vectorAt( vector_t v, size_t idx)
{
if ( idx >= v->size_ )
{
vectorErrno = VEC_EINDEX;
return NULL;
}
vectorErrno = VEC_EOK;
return v->ptr_ + idx*v->esize_;
}
void vectorPushBack( vector_t v, void *srcptr)
{
void *tgtptr;
if ( v->size_ == v->capacity_ )
{
if ( ! vectorGrowBuffer(v) )
return;
}
tgtptr = v->ptr_ + v->esize_*v->size_;
v->cpyfun_( tgtptr, srcptr);
++v->size_;
vectorErrno = VEC_EOK;
return;
}
void vectorPopBack( vector_t v)
{
if ( v->size_ == 0 )
{
vectorErrno = VEC_EEMPTY;
return;
}
--v->size_;
vectorErrno = VEC_EOK;
return;
}
Fordítás, szerkesztés, futtatás:
1
2
3
4
5
6
7
8
9
10
11
12
13
$ gcc -ansi -pedantic -Wall -W vecmain.c vector.c
$ ./a.out
vec1 cap. = 0
vec1 size = 0
vec1 cap. = 128
vec1 size = 100
vec1[42] = 1764.000000
vec1[42] = 1764.000000
vec2[42] = 99.990000
vec2 cap. = 100
vec2 size = 99
vec3 size = 100
vec1 size = 0
Ellenőrizzük a megoldásunk helyességét a memória-elszivárgás szempontjából:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
==492== Memcheck, a memory error detector
==492== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==492== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==492== Command: ./a.out
==492==
vec1 cap. = 0
vec1 size = 0
vec1 cap. = 128
vec1 size = 100
vec1[42] = 1764.000000
vec1[42] = 1764.000000
vec2[42] = 99.990000
vec2 cap. = 100
vec2 size = 99
vec3 size = 100
vec1 size = 0
==492==
==492== HEAP SUMMARY:
==492== in use at exit: 0 bytes in 0 blocks
==492== total heap usage: 11 allocs, 11 frees, 3,448 bytes allocated
==492==
==492== All heap blocks were freed -- no leaks are possible
==492==
==492== For counts of detected and suppressed errors, rerun with: -v
==492== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)