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
|
/***************************************************************************//**
* @file array.h
* @author Dorian Weber
* @brief Generischer Array-Typ.
*
* @details
* Diese Datei enthält die Schnittstelle eines generischen Array-Typs. Um den
* Element-Typ des Arrays festzulegen, deklariert man eine Variable als Zeiger
* auf den Element-Typ. Diese kann danach initialisiert und so benutzt werden,
* als wäre sie ein Zeiger auf ein Array variabler Länge.
*
* Hier ist ein Nutzungsbeispiel:
* @code
* int *array;
*
* arrayInit(array);
* arrayPush(array) = 1;
* arrayPush(array) = 2;
* arrayPush(array) = 3;
*
* while (!arrayIsEmpty(array))
* printf("%i\n", arrayPop(array));
*
* arrayRelease(array);
* @endcode
*
* Viele der genutzten Funktionen sind in Form von Makros implementiert, die die
* Variable, die den Zeiger auf das Array hält, aktualisieren, obwohl es so
* aussieht, als würde sich dieser Wert niemals ändern. Das macht es riskant
* mehr als einen Zeiger auf das Array zu halten, da jede Vergrößerung des
* Arrays alle Zeiger auf und in das Array potentiell invalidiert. Obwohl diese
* Fehlerquelle subtil und äußerst schwer diagnostizierbar ist - es ist eine
* extrem einfache Abstraktion - führt diese Datenstruktur meiner Meinung nach
* trotzdem zu einem massiven Produktivitätsgewinn; man sollte sich nur in etwa
* im Klaren über die unterliegende Implementation sein, um genau die Untermenge
* von Programmiertechniken auszuwählen, die korrekt funktioniert.
******************************************************************************/
#ifndef ARRAY_H_INCLUDED
#define ARRAY_H_INCLUDED
/* *** includes ************************************************************* */
#include <stddef.h>
/* *** structures *********************************************************** */
/**@brief Arrayheader.
*
* Diese Struktur wird jedem Array im Speicher vorangestellt und beinhaltet
* Informationen über Kapazität und aktuelle Auslastung des Arrays. Die
* Arrayelemente schließen sich dieser Struktur unmittelbar an, so dass der
* Nutzer von dieser versteckten Information nichts bemerkt.
*/
typedef struct ArrayHdr
{
size_t len; /**<@brief Anzahl der Array-Elemente. */
size_t cap; /**<@brief Kapazität des reservierten Speichers. */
} ArrayHdr;
/* *** interface ************************************************************ */
/**@internal
* @brief Initialisiert und gibt einen Zeiger auf den Start des Arrays zurück.
* @param capacity initiale Kapazität
* @param size Größe der Arrayelemente
* @return ein Zeiger auf den Start des Arrays, falls erfolgreich,\n
* \c NULL im Falle eines Speicherfehlers
*/
extern void* arrayInit(size_t capacity, size_t size);
/**@brief Initialisiert ein neues Array.
* @param self das Array
* @return 0, falls keine Fehler bei der Initialisierung aufgetreten sind,\n
* -1 ansonsten
*/
#define arrayInit(self) \
((self = arrayInit(8, sizeof((self)[0]))) == NULL ? -1 : 0)
/**@brief Gibt das Array und alle assoziierten Strukturen frei.
* @param self das Array
*/
extern void arrayRelease(void* self);
/**@internal
* @brief Reserviert Platz für einen neuen Wert im Array.
* @param self das Array
* @param size Größe der Arrayelemente
* @return der neue Zeiger auf den Start des Arrays
*/
extern void* arrayPush(void* self, size_t size);
/**@brief Legt einen Wert auf das Array.
* @param self das Array
*/
#define arrayPush(self) \
(self = arrayPush(self, sizeof((self)[0])), (self)+arrayLen(self)-1)[0]
/**@brief Entfernt das oberste Element des Arrays.
* @param self das Array
*/
extern void arrayPop(void* self);
/**@brief Entfernt und liefert das oberste Element des Arrays.
* @param self das Array
* @return das oberste Element von \p self
*/
#define arrayPop(self) \
(arrayPop(self), (self)+arrayLen(self))[0]
/**@brief Gibt das oberste Element des Arrays zurück.
* @param self das Array
* @return das oberste Element von \p self
*/
#define arrayTop(self) \
(self)[arrayLen(self) - 1]
/**@brief Setzt die Länge des Arrays auf 0 zurück.
* @param self das Array
*/
inline void arrayClear(void* self) {
((ArrayHdr*) self)[-1].len = 0;
}
/**@brief Gibt zurück, ob das Array leer ist.
* @param self das Array
* @return 0, falls nicht leer\n
1, falls leer
*/
inline int arrayIsEmpty(const void* self) {
return ((ArrayHdr*) self)[-1].len == 0;
}
/**@brief Gibt die Anzahl der Array-Elemente zurück.
* @param self das Array
* @return Anzahl der Elemente des Arrays
*/
inline size_t arrayLen(const void* self) {
return ((ArrayHdr*) self)[-1].len;
}
#endif /* ARRAY_H_INCLUDED */
|
