 | |
This article gives an overview of the following C-language extensions (part of the GNU C-implementation) introduced in the Sun Studio 12 C compiler. Although these extensions are not part of the latest ISO C99 standard, they are supported by the popular gcc compilers.
The article also demonstrates how to use the new C compiler features for creating generic macros on example of linked-list manipulation-routines. Such macros semantically mimic C++ Standard Template Library, support arbitrary data types and provide strict compile-time type-checking. This article is organized into the following sections:
The typeof keyword is a new extension to the C language. The Sun Studio C compiler accepts constructs with typeof wherever a typedef name is accepted, including the following syntactic categories:
The compiler accepts this keyword in combination with double underscores: __typeof, __typeof__. The examples in this article do not make use of the double underscore convention. Syntactically, the typeof keyword is followed by parentheses which contain either the name of a type or an expression. This is similar to the possible operands which are accepted by the sizeof keyword (unlike sizeof, bit-fields are allowed as typeof argument what is interpreted as corresponding integer type). Semantically, the typeof keyword acts like the name of a type (typedef name) and specifies a type. Example Declarations That Use typeofThe following are two equivalent declarations for the variable a of type int. typeof(int) a; /* Specifies variable a which is of the type int */
typeof('b') a; /* The same. typeof argument is an expression consisting of
character constant which has the type int */The following example shows declarations of pointers and arrays. To compare, equivalent declarations without typeof are also given. typeof(int *) p1, p2; /* Declares two int pointers p1, p2 */ int *p1, *p2; typeof(int) * p3, p4;/* Declares int pointer p3 and int p4 */ int * p3, p4; typeof(int [10]) a1, a2;/* Declares two arrays of integers */ int a1[10], a2[10]; If you use an expression with typeof, the expression is not evaluated. Only the type of that expression is derived. The following example declares the variable var of type int because the expression foo() is of type int. The function foo is not invoked because the expression is not evaluated. extern int foo(); typeof(foo()) var; Restrictions of Declarations That Use typeofNote that the type name in a typeof construct cannot contain storage-class specifiers such as extern or static. However, type qualifiers such as const or volatile are allowed. For example, the following code is invalid because it declares extern in the typeof construct: typeof(extern int) a; The following declaration of the identifier b with external linkage denotes an object of type int and is valid. The next declaration is also valid and declares a const qualified pointer of type char which means the pointer p cannot be modified. extern typeof(int) b; typeof(char * const) p = "a"; Using typeof in Macro DefinitionsThe main application of typeof constructs is probably in macro definitions. You can use the typeof keyword to refer to the type of a macro parameter. Consequently, it is possible to construct objects with necessary types without specifying the type names explicitly as macro arguments. The FINDMAX MacroThe FINDMAX macro finds the largest value in an array. The types of the elements can be int, float or double. #define FINDMAX(m, x, n)\
{\
typeof(n) _n = n; /* _n is local copy of the number of elements*/\
if (_n > 0) { /* in case the array is empty */\
int _i;\
typeof((x)[0]) * _x = x; /* _x is local copy of pointer to the elements */\
typeof(m) _m = _x[0]; /* _m is maximum value found */\
for (_i=1; _i<_n; _i++) /* Iterate through all elements */\
if (_x[_i] > _m)\
_m = _x[_i];\
(m) = _m; /* returns the result */\
}\
}
The FINDMAX macro requires three arguments:
Note that after argument substitution, the expressions which are specified as macro parameters are evaluated only once. That is achieved by employing two local variables: _x, _n. Consider the following macro invocation: FINDMAX(m, ++p, --n); After macro substitution, the for loop looks like this: typeof(--n) _n = --n;
...
typeof((++p)[0]) * _x = ++p;
...
for (_i=1; _i<_n; _i++)
if (_x[_i] > _m)
...Without local copies of macro parameters, they would be evaluated in every iteration of the for loop which is wrong: for (_i=1; _i<--n; _i++)
if ((++p)[_i] > _m)
...An implementation of the FINDMAX macro which does not use the typeof keyword somehow needs to specify the types of the local variables. For example, the types could be specified by adding another macro parameter for the name of a type or by providing three versions of that macro, each for a different type. For creating generalized macros both of these solutions are not as flexible as a solution using typeof. Note the declaration of _x : typeof((x)[0]) * _x = x; Assuming x is either a pointer to the initial element of an array or an array, this instruction declares _x as a pointer to the elements of the array. Here typeof argument is an expression, which is not evaluated, that designates an element of the array to refer to its type. A declaration such as typeof(x) _x = x; would work only for pointers because typeof(x), in this instance x is an array, is still an array type. No implicit conversion of "array of type" to "pointer to type" is performed for a typeof argument and an array cannot be initialized with another array. Running Code That Uses FINDMAXThe following is a sample application which incorporates the FINDMAX macro: int main()
{
int i[] = {69891, 71660, 71451, 71434, 72317}, im;
float f[] = {69891., 71660., 71451., 71434., 72317.}, fm;
double d[] = {69891., 71660., 71451., 71434., 72317.}, dm, * dp = d;
int n = 5;
FINDMAX(im, i, n--);
FINDMAX(fm, f, n--);
FINDMAX(dm, dp+=2, n--);
printf("%d\t%f\t%f\n", im, fm, dm);
}This program produces 72317 71660.000000 72317.000000 Notice the confusing way in which the FINDMAX macro returns the results. Using FINDMAX looks like a function call but the results are returned through one of the arguments of the function macro and that argument is not a pointer (a function cannot change the value of its argument by changing the value of the parameter). A compound statement, which we use in the macro definition to limit the scope of the local variables, can not return a value. However, statement expressions can. That is the second language extension to be discussed in this article.
A compound statement enclosed in parentheses represents statement expression. The simplest statement expression is just empty statement expression which has type void ({})On one hand, statement expressions, like compound statements, can contain other statements as well as nested statement expressions, declarations and, again like compound statements, open a new scope. For example, the following expression contains declarations of two automatic int variables, not visible outside the scope of the expression, and two expression statements that assign value 1 to both a and b: ({
int a;
a = 1;
int b;
b = a;
})On the other hand, statement expressions, like expressions, have a type, compute a value and can be used wherever expressions are accepted:
One exception to this is that statement expressions have to be in scope within a function or a block, no file scope statement expressions are allowed. The following program is incorrect because statement expression {( 1; )}is used outside a function. int a = {( 1; )};
int foo(void)
{
return a;
}If a statement expression ends with an expression, the type and value are determined by the latter. In other cases, the type of the expression is void and there is no value. A statement expression has type void if the last statement is not an expression that returns a value. The first statement expression in the next example is of type void because it ends with the declaration. ({int a = 1;});
({int a; a=1;});It is a valid expression unless it is used as an rvalue. The second expression is of type int and evaluated to the value 1 because it ends with expression statement a=1; where a is int. With the help of statement expressions our generalized FINDMAX macro can be rewritten in the following manner:
#define FINDMAX(x, n)\
({\
typeof(n) _n = n;\
typeof((x)[0]) _m;\
if (_n > 0) {\
int _i;\
typeof((x)[0]) * _x = x;\
_m = _x[0];\
for (_i=1; _i<_n; _i++)\
if (_x[_i] > _m)\
_m = _x[_i];\
}\
_m;\
})
Now the macro does not require parameter m to return the result because the last statement of the statement expression is used to do this and after macro substitution FINDMAX becomes an expression and its usage syntactically looks like calling a function: im = FINDMAX(i, n--); fm = FINDMAX(f, n--); dm = FINDMAX(dp+=2, n--);
Another language extension that is useful for writing macros is local labels support. According to the C standard a label identifier has function scope. It is impossible to define two labels with the same name within one function despite of block scopes they may be defined. Using regular function-scope labels in macros is restricted, as multiple invocations of the same macro in one function will result in multiple definitions of the same label. The new keyword __label__ limits visibility of labels within a block scope. Such a declaration begins with __label__ keyword followed by one or more label identifiers separated by commas. For example: __label__ a, b; __label__ c; Local labels must be declared at the beginning of a block (a statement expression also opens a block) or a function prior to any statements. Local labels are defined in the usual way. In the following example two local labels are defined with the same name in different blocks within function foo. void foo(void)
{
{
__label__ a;
goto a;
a: ;
}
{
__label__ a;
goto a;
a: ;
}
}Local labels may be convenient for complex macros where using goto is reasonable. Although FINDMAX macro is not complex enough to require goto's it is rewritten to demonstrate how local labels can be used. In the following version of FINDMAX a local label is declared and defined in a statement expression: #define FINDMAX(x, n)\
({\
__label__ l;\
typeof(n) _n = n;\
typeof((x)[0]) _m;\
typeof((x)[0]) * _x = x;\
int i;\
if (!_n) goto l;\
_m = _x[0];\
for (i=1; i<_n; i++)\
if (_x[i] > _m)\
_m = _x[i];\
l: _m;\
})Using local label avoids possible conflicts with label names because label l is local to the enclosing statement expression and is not visible outside the expression.
List DeclarationLet us implement a set of macros for working with a list data structure. As a requirement assume we need some sort of type generic macros that allow constructing different types of lists so that the same macros can be used with lists of ints, floats or any arbitrary types. Let us first write a macro for a list declaration. #define TLIST(T,L) \
struct _List##L { \
struct _List##L * _next; \
struct _List##L * _prev; \
T _data; \
} L = {&(L), &(L)}The TLIST declares a trivial double linked list named L. The list is strictly typed because every element of the list has type T and compiler will check type compatibility during references to node element _data. Moreover, the nodes of different lists have different types so they cannot be used together in one macro. Structure _List##L represents a node of the list. The list itself is a single node that is used to mark the end of the list and it is circularly linked. The other nodes will be allocated dynamically. Initializer in the declaration ensures that the list is initially empty. For example: TLIST(int, l1);
TLIST(struct { int a; char *s; }, l2);This example declares list l1 of integer numbers and a list l2 of structures. The other advantage of declaring such a macro (instead of a typeless declaration), is the ease of debugging. We can inspect the elements of the list without using type casts. There are two limitations of the TLIST macro definition. Firstly, it does not allow us to declare a list of pointers to functions although this is easily overcome by replacing T with typeof(T) in the macro definition (for a pointer to void function returning void , the declaration would look like TLIST(void (*)(void), l)). Secondly, although we can declare a list of arrays (in the same way , using typeof(T), the macro TLISTINSERT shown below would not be valid. This is because in C we cannot assign one array to another array or to initialize array with another array. It could be done using memcpy function, but then we will lose type checking because parameters of memcpy are void pointers. The workaround for arrays is to wrap them in a structure. Insertion/Removal Elements of ListTwo main operations on a list are implemented here: insertion of an element and removal of an element. #define TLISTINSERT(I, V)\
({\
typeof(I) __tmp, __n, __p;\
__tmp = (typeof(I)) malloc(sizeof(*(I)));\
__n = (I);\
__p = __n->_prev;\
if (__tmp != 0) {\
__tmp->_data = V;\
__tmp->_next = __n;\
__tmp->_prev = __p;\
__p->_next = __tmp;\
__n->_prev = __tmp;\
};\
__tmp;\
})
#define TLISTERASE(I)\
({\
typeof(I) __pos, __n, __p;\
__pos = (I);\
__n = __pos->_next;\
__p = __pos->_prev;\
__p->_next = __n;\
__n->_prev = __p;\
free(__pos);\
__n;\
})
#define TLISTBEGIN(L) ((L)._next)
#define TLISTEND(L) (&(L))
#define TLISTPUSHFRONT(L,V) TLISTINSERT(TLISTBEGIN(L), V)
#define TLISTPUSHBACK(L,V) TLISTINSERT(TLISTEND(L), V)The macro TLISTINSERT inserts a copy of object V into the list before the node I. The macro allocates memory for new node dynamically using malloc and copies object V into the new node. Pointer to that node is returned. The type of object V has to match the type specified during list declaration. TLISTERASE removes node I from the list and frees previously allocated memory for the node. The macro TLISTERASE returns pointer to the node following removed node. Necessary macros TLISTBEGIN and TLISTEND return pointers to the first and the next after the last node in the list L respectively. If a list L is empty then TLISTBEGIN(L) == TLISTEND(L). Two macros TLISTPUSHFRONT and TLISTPUSHBACK are shorter notation for insertion of a new element before the first and after the last elements of list correspondingly. Now it is possible to fill a list as shown below: TLIST(int, l1); TLISTPUSHBACK(l1, 69891); TLISTPUSHBACK(l1, 71660); TLISTPUSHBACK(l1, 71451); TLISTERASE(TLISTBEGIN(l1)); List l1 will contain two elements in order 71660 and 71451. An example, which also uses C99 compound literals, of filling a list of structures: TLIST(struct s { int a; char *s; }, l2);
TLISTPUSHBACK(l2, ((struct s){69891, "Feb"}) );
TLISTPUSHBACK(l2, ((struct s){71660, "Mar"}) );
TLISTPUSHBACK(l2, ((struct s){71451, "Apr"}) );
TLISTERASE(TLISTBEGIN(l2));List l2 will contain two elements {71660, "Mar"} and {71451, "Apr"}. And if we try to insert an element of one type into the list declared to contain elements of other incompatible type, compiler will detect an error, as for the next code fragment: TLIST(struct s { int a; char *s; }, l2);
TLISTPUSHBACK(l2, 69891);Moreover it is a compile-time check so there is no run-time penalty in our implementation of a strictly typed list. Again to note, the arguments of TLISTINSERT and TLISTERASE macros are evaluated only once what enables writing nested constructs (without typeof and statement expressions it would be quite difficult and cumbersome): TLIST(char *, l3); TLISTINSERT(TLISTINSERT(TLISTPUSHBACK(l3,"Mar"), "Feb"), "Jan"); The list l3 will contain three elements in order "Jan", "Feb" and "Mar". List IterationsThe next important step is to define means to traverse the lists. An idea of pointers to nodes as iterators fits well. #define TLISTITER(L) typeof((L)._next) #define TLISTINC(I) ((I)->_next) #define TLISTREF(I) ((I)->_data) The TLISTITER allows declare pointers to the nodes (iterators) of list L. TLISTINC returns pointer to the next node after the node I and TLISTREF is used to dereference a pointer to the node to access the corresponding element of the list. Now we can define an utility macro for emptying the whole list: #define TLISTCLEAR(L)\
({\
TLISTITER(L) __c = TLISTBEGIN(L);\
while (__c != TLISTEND(L))\
{\
TLISTITER(L) __tmp = __c;\
__c = TLISTINC(__c);\
free(__tmp);\
}\
(L)._next = (L)._prev = &(L);\
})Macro TLISTCLEAR frees memory allocated for nodes of the list L, which becomes empty. As you can see, macros TLISTITER, TLISTINC and TLISTREF allow to use the following syntax to traverse lists for (TLISTITER(l1) i = TLISTBEGIN(l1); i != TLISTEND(l1); i = TLISTINC(i))
printf("%d\n", TLISTREF(i));
for (TLISTITER(l2) i = TLISTBEGIN(l2); i != TLISTEND(l2); i = TLISTINC(i))
printf("%d %s\n",TLISTREF(i).a, TLISTREF(i).s);Although lists l1 and l2 are of different types, the same macros are used here. And if we confuse pointers to nodes of different lists, as in the next example, compiler will emit a warning about different pointer types: for (TLISTITER(l1) i = TLISTBEGIN(l1); i != TLISTEND(l2); i = TLISTINC(i))
printf("%d\n", TLISTREF(i));Logically, we can provide shorter notation of enumerating elements of a list by defining macro TLISTFOREACH #define FOR_EACH(I, first, last, inc, blk)\
({\
typeof(first) I;\
for (I=first; I != last; I=inc(I))\
blk;\
I;\
})
#define TLISTFOREACH(I, L, blk)\
FOR_EACH(I, TLISTBEGIN(L), TLISTEND(L), TLISTINC, blk)It requires three arguments. I is the name of pointer to current node in the list L so list items could be referenced in the blk. L is name of the list and blk is a block to be executed for every list element. Now printing content of lists l1 and l2 can be rewritten: TLISTFOREACH(i, l1, ({
printf("%d\n", TLISTREF(i));
}) );
TLISTFOREACH(i, l2, ({
printf("%d %s\n",TLISTREF(i).a, TLISTREF(i).s);
}) );It looks shorter that the original version with for loops. Also using TLISTFOREACH we can easily define a macro to determine size of a list as follow #define TLISTSIZE(L)\
({\
int __n = 0;\
TLISTFOREACH(i, L, ({++__n;}));\
__n;\
})TLISTSIZE returns number of elements in the list L. Some more words about parameter blk of the TLISTFOREACH macro. It is intended to be a statement expression and determines operations performed for every list item. It might be a compound statement, but in the following case C preprocessor will detect an error: int n = 0;
TLISTFOREACH(i, l1, {
printf("%d\n", TLISTREF(i)), ++n;
} );There is a problem here because comma operator will be treated as a separator of parameters of macro. To avoid this, the comma operator should be screened inside matched pairs of parenthesis . And a statement expression has a natural pair of them. Going further, we define another generic algorithm on lists -- finding a list element: #define TLISTFIND(I, L, blk)\
TLISTFOREACH(I, L, ({if (blk) break;}))where I - is the name of pointer to current node in the list L. Parameter blk should be an statement expression or just expression that is evaluated to non zero when required element has been found in the list. Iteration stops when blk is evaluated to nonzero value and macro TLISTFIND returns pointer to the current node. If there is no such an element in the list, TLISTFIND returns a pointer to the end of list. The next code demonstrates how TLISTFIND macro can be used: if ( TLISTFIND(i, l2, ({ strcmp(TLISTREF(i).s, "Mar") == 0; }) ) != TLISTEND(l2) )
{
printf("Mar found\n");
}Analogous to definition of macro TLISTFIND other generic algorithms can be defined on the lists. Three example programs are shown below that demonstrate the usage of macros defined thus far. Example 1Basic operations on a list of int's #include <stdio.h>
#include "tlist.h"
int main()
{
TLIST(int, l1);
TLISTPUSHBACK(l1, 69891);
TLISTPUSHBACK(l1, 71660);
TLISTPUSHBACK(l1, 71451);
TLISTPUSHBACK(l1, 71434);
TLISTPUSHBACK(l1, 72317);
TLISTPUSHFRONT(l1, 68233);
printf("size of l1=%d\n", TLISTSIZE(l1));
TLISTFOREACH(i, l1, ({ printf("%d\n", TLISTREF(i)); }));
printf("Removing first element\n");
TLISTERASE(TLISTBEGIN(l1));
printf("size of l1=%d\n", TLISTSIZE(l1));
TLISTFOREACH(i, l1, ({ printf("%d\n", TLISTREF(i)); }));
printf("Removing 71660\n");
TLISTERASE(TLISTFIND(i, l1, ({ TLISTREF(i) == 71660; })));
printf("size of l1=%d\n", TLISTSIZE(l1));
TLISTFOREACH(i, l1, ({ printf("%d\n", TLISTREF(i)); }));
printf("Emptying the list\n");
TLISTCLEAR(l1);
printf("size of l1=%d\n", TLISTSIZE(l1));
TLISTFOREACH(i, l1, ({ printf("%d\n", TLISTREF(i)); }));
return 0;
}Expected output : size of l1=6 68233 69891 71660 71451 71434 72317 Removing first element size of l1=5 69891 71660 71451 71434 72317 Removing 71660 size of l1=4 69891 71451 71434 72317 Emptying the list size of l1=0 Example 2An example of a list of structures: #include <stdio.h>
#include <string.h>
#include "tlist.h"
int main()
{
TLIST(struct s { int a; char *s; }, l2);
TLISTINSERT(TLISTINSERT(TLISTPUSHBACK(l2, ((struct s){71451, "Apr"})),
((struct s){0, "Mar"}) ),
((struct s){69891, "Feb"}) );
TLISTFOREACH(i, l2, ({ printf("%s %d\n", TLISTREF(i).s, TLISTREF(i).a); }));
printf("Updating Mar\n");
TLISTREF(TLISTFIND(i, l2, ({ strcmp(TLISTREF(i).s, "Mar") == 0; }))).a += 71660;
TLISTFOREACH(i, l2, ({ printf("%s %d\n", TLISTREF(i).s, TLISTREF(i).a); }));
TLISTCLEAR(l2);
return 0;
}Expected output : Feb 69891 Mar 0 Apr 71451 Updating Mar Feb 69891 Mar 71660 Apr 71451 Example 3And the final example shows how a list of lists can be constructed: #include <stdio.h>
#include "tlist.h"
int main()
{
int i, j;
TLISTDEF(int, tintlist);
TLIST(tintlist, l5);
for (i=1; i<10; i++)
{
TLISTITER(l5) li = TLISTPUSHBACK(l5, (tintlist){0});
TLISTINIT(TLISTREF(li));
for (j=1; j<10; j++)
TLISTPUSHBACK(TLISTREF(li), i*j);
}
TLISTFOREACH(i, l5, ({
TLISTFOREACH(j, TLISTREF(i), ({
printf("%d\t", TLISTREF(j));
}));
printf("\n");
}));
TLISTFOREACH(i, l5, ({ TLISTCLEAR(TLISTREF(i));}));
TLISTCLEAR(l5);
return 0;
}The example uses two new macros TLISTDEF and TLISTINIT. For details of their definitions please refer Appendix. The output of the above program should be 1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81
/*
* File: tlist.h
*
* Created on July 23, 2006, 8:10 PM
*/
#ifndef _tlist_H
#define _tlist_H
#include <stdlib.h>
#define TLIST(T,L) \
struct _List##L { \
struct _List##L * _next; \
struct _List##L * _prev; \
T _data; \
} L = {&(L), &(L)}
#define TLISTDEF(T, TL) \
typedef struct _List##TL { \
struct _List##TL * _next; \
struct _List##TL * _prev; \
T _data; \
} TL
#define TLISTINIT(L)\
(L) = (typeof(L)){&(L), &(L)}
#define TLISTBEGIN(L) ((L)._next)
#define TLISTEND(L) (&(L))
#define TLISTITER(L) typeof((L)._next)
#define TLISTINC(I) ((I)->_next)
#define TLISTDEC(I) ((I)->_prev)
#define TLISTREF(I) ((I)->_data)
#define TLISTINSERT(I, V)\
({\
typeof(I) __tmp, __n, __p;\
__tmp = (typeof(I)) malloc(sizeof(*(I)));\
__n = (I);\
__p = __n->_prev;\
if (__tmp != 0) {\
__tmp->_data = V;\
__tmp->_next = __n;\
__tmp->_prev = __p;\
__p->_next = __tmp;\
__n->_prev = __tmp;\
};\
__tmp;\
})
#define TLISTPUSHFRONT(L,V) TLISTINSERT(TLISTBEGIN(L), V)
#define TLISTPUSHBACK(L,V) TLISTINSERT(TLISTEND(L), V)
#define TLISTERASE(I)\
({\
typeof(I) __pos, __n, __p;\
__pos = (I);\
__n = __pos->_next;\
__p = __pos->_prev;\
__p->_next = __n;\
__n->_prev = __p;\
free(__pos);\
__n;\
})
#define TLISTCLEAR(L)\
({\
TLISTITER(L) __c = TLISTBEGIN(L);\
while (__c != TLISTEND(L))\
{\
TLISTITER(L) __tmp = __c;\
__c = TLISTINC(__c);\
free(__tmp);\
}\
(L)._next = (L)._prev = &(L);\
})
#define FOR_EACH(I, first, last, inc, blk)\
({\
typeof(first) I;\
for (I=first; I != last; I=inc(I))\
blk;\
I;\
})
#define TLISTFOREACH(I, L, blk)\
FOR_EACH(I, TLISTBEGIN(L), TLISTEND(L), TLISTINC, blk)
#define TLISTSIZE(L)\
({\
int __n = 0;\
TLISTFOREACH(i, L, ({++__n;}));\
__n;\
})
#define TLISTFIND(I, L, blk)\
TLISTFOREACH(I, L, ({if (blk) break;}))
#endif /* _tlist_H */
|
| ||||||||||||||
| |
| ||||||||||||
Print-friendly Version
