Skip to content

Commit 46ee63c

Browse files
attractivechaosattractivechaos
committed
added code comments
1 parent b8bcd62 commit 46ee63c

File tree

9 files changed

+66
-30
lines changed

9 files changed

+66
-30
lines changed

‎Makefile‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
EXE=test-intru1 test-intru2 test-macro test-void
1+
EXE=test-intru1 test-intru2 test-macro1 test-void
22

33
.PHONY:all clean
44

@@ -10,7 +10,7 @@ test-intru1:test-intru1.c dl-intru1.h
1010
test-intru2:test-intru2.c dl-intru2.c dl-intru2.h
1111
$(CC) -Wall -g -O2 -o $@ test-intru2.c dl-intru2.c
1212

13-
test-macro:test-macro.c dl-macro.h
13+
test-macro1:test-macro1.c dl-macro1.h
1414
$(CC) -Wall -g -O2 -o $@ $<
1515

1616
test-void:test-void.c dl-void.c dl-void.h

‎dl-intru1.h‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
#ifndef DL_INTRU1_H
22
#define DL_INTRU1_H
33

4+
// see dl-intru2.* for description of the APIs and the implementation
5+
46
#define DL_HEAD(_type) struct { _type *p[2]; }
57

6-
#define DL_IMPL(suf, _type, _head) \
7-
static inline void dl_push_##suf(_type *head[2], _type *p, int dir) { \
8+
#define DL_IMPL(suf, _type, _head) /* suf creates a name space for a specific type to avoid naming clash */ \
9+
static inline void dl_push_##suf(_type *head[2], _type *p, int dir) { /* ##suf for token concatenation */ \
810
dir = !!dir; /* 0 or 1 */ \
911
p->_head.p[0] = p->_head.p[1] = 0; \
1012
if (head[0] == 0 && head[1] == 0) head[0] = head[1] = p; \
@@ -19,6 +21,7 @@
1921
return p; \
2022
}
2123

24+
// more convenient macro APIs
2225
#define dl_push(suf, head, p, dir) dl_push_##suf(head, p, dir)
2326
#define dl_pop(suf, head, dir) dl_pop_##suf(head, dir)
2427

‎dl-intru2.c‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2,18 +2,18 @@
22

33
void dl_push(dl_head_t *head[2], dl_head_t *p, int dir)
44
{
5-
dir = !!dir;
5+
dir = !!dir; // make sure dir is either 0 or 1
66
p->p[0] = p->p[1] = 0;
7-
if (head[0] == 0 && head[1] == 0) head[0] = head[1] = p;
8-
else head[dir]->p[dir] = p, p->p[!dir] = head[dir], head[dir] = p;
7+
if (head[0] == 0 && head[1] == 0) head[0] = head[1] = p; // an empty list; then just add
8+
else head[dir]->p[dir] = p, p->p[!dir] = head[dir], head[dir] = p; // push
99
}
1010

1111
dl_head_t *dl_pop(dl_head_t *head[2], int dir)
1212
{
1313
dl_head_t *p;
1414
dir = !!dir;
15-
if (head[0] == 0 && head[1] == 0) return 0;
16-
else if (head[0] == head[1]) p = head[0], head[0] = head[1] = 0;
17-
else p = head[dir], head[dir] = p->p[!dir], head[dir]->p[dir] = 0;
15+
if (head[0] == 0 && head[1] == 0) return 0; // an empty list; return a NULL pointer
16+
else if (head[0] == head[1]) p = head[0], head[0] = head[1] = 0; // only one element; clear the list
17+
else p = head[dir], head[dir] = p->p[!dir], head[dir]->p[dir] = 0; // more than one elements
1818
return p;
1919
}

‎dl-intru2.h‎

Lines changed: 37 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,51 @@
11
#ifndef DL_INTRU2_H
22
#define DL_INTRU2_H
33

4-
#include <stddef.h>
4+
#include <stddef.h> // for offsetof()
55

6-
#define dl_container_of(ptr, type, member) ((type *)((char *)(ptr) - offsetof(type, member)))
7-
8-
typedef struct dl_head_s {
9-
struct dl_head_s *p[2];
6+
typedef struct dl_head_s { // this struct can't be hidden
7+
struct dl_head_s *p[2]; // p[0] points the previous record; p[1] points to the next
108
} dl_head_t;
119

10+
/**
11+
* Given a pointer to a struct member, get the pointer to the struct
12+
*
13+
* @param ptr pointer to a struct member
14+
* @param type type of the struct
15+
* @param member name of the member in the struct
16+
*
17+
* @return pointer to the struct
18+
*/
19+
#define dl_container_of(ptr, type, member) ((type *)((char *)(ptr) - offsetof(type, member)))
20+
1221
#ifdef __cplusplus
1322
extern "C" {
1423
#endif
1524

25+
/**
26+
* Push a record to the list
27+
*
28+
* A double-linked list is represented by two pointers: a head and a tail. For
29+
* an empty list, both of them are set to NULL pointers. As such, head[0] and
30+
* head[1] shall be set to NULL on the first call to this function. dl_push()
31+
* implements C++'s push_back() and push_front() at the same time.
32+
*
33+
* @param head head and tail of the list
34+
* @param p pointer to the element to add
35+
* @param dir direction: 0 for pushing from the front; 1 from the back
36+
*/
1637
void dl_push(dl_head_t *head[2], dl_head_t *p, int dir);
38+
39+
/**
40+
* Pop a record from the list
41+
*
42+
* @param head head and tail of the list
43+
* @param dir direction
44+
*
45+
* @return pointer to the record, which is removed from the list. If the list
46+
* is empty, NULL is returned. If the list only has one record, head[0] and
47+
* head[1] are set to NULL, indicating an empty list.
48+
*/
1749
dl_head_t *dl_pop(dl_head_t *head[2], int dir);
1850

1951
#ifdef __cplusplus

dl-macro.h renamed to dl-macro1.h

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
#ifndef DL_MACRO_H
22
#define DL_MACRO_H
33

4+
// see dl-intru2.* for details on the methodology
5+
46
#define DL_CALLOC(type, len) (type*)calloc((len), sizeof(type))
57

6-
#define DL_IMPL(name, _type) \
7-
typedef struct dl_node_##name##_s { \
8+
#define DL_IMPL(name, _type) /* name creates a name space for a specific data type to avoid naming clash */ \
9+
typedef struct dl_node_##name##_s { /* ##name## for token concatenation */ \
810
_type data; \
911
struct dl_node_##name##_s *p[2]; \
1012
} dl_node_##name##_t; \
@@ -17,7 +19,7 @@
1719
if (list->head[0] == 0 && list->head[1] == 0) list->head[0] = list->head[1] = p; \
1820
else list->head[dir]->p[dir] = p, p->p[!dir] = list->head[dir], list->head[dir] = p; \
1921
} \
20-
static inline int dl_pop_##name(dl_list_##name##_t *list, _type *data, int dir) { \
22+
static inline int dl_pop_##name(dl_list_##name##_t *list, _type *data, int dir) { /* *data is only set if 1 is returned */ \
2123
dl_node_##name##_t *p; \
2224
dir = !!dir; \
2325
if (list->head[0] == 0 && list->head[1] == 0) return 0; \

‎dl-void.c‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
#include <stdlib.h>
22
#include "dl-void.h"
33

4+
// see dl-intru2.* for the algorithm
5+
46
#define CALLOC(type, len) (type*)calloc((len), sizeof(type))
57

68
typedef struct dl_node_s {
@@ -12,10 +14,7 @@ struct dl_list_s {
1214
dl_node_t *head[2];
1315
};
1416

15-
dl_list_t *dl_init(void)
16-
{
17-
return (dl_list_t*)calloc(1, sizeof(dl_list_t));
18-
}
17+
dl_list_t *dl_init(void) { return CALLOC(dl_list_t, 1); }
1918

2019
void dl_push(dl_list_t *list, void *data, int dir)
2120
{

‎dl-void.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
#ifndef DL_VOID_H
22
#define DL_VOID_H
33

4-
struct dl_list_s;
4+
struct dl_list_s; // opaque struct
55
typedef struct dl_list_s dl_list_t;
66

77
#ifdef __cplusplus

‎test-intru2.c‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -6,23 +6,23 @@
66

77
typedef struct {
88
int x;
9-
dl_head_t head;
9+
dl_head_t head; // this field forms a double-linked list
1010
} my_elem_t;
1111

1212
int main(void)
1313
{
1414
int i, N = 5;
1515
dl_head_t *head[2] = {0, 0};
1616
for (i = 0; i < N; ++i) {
17-
my_elem_t *p = MALLOC(my_elem_t, 1);
17+
my_elem_t *p = MALLOC(my_elem_t, 1); // caller controls all memory allocations
1818
p->x = i;
19-
dl_push(head, &p->head, 1);
19+
dl_push(head, &p->head, 1); // push_back()
2020
}
2121
while (head[0]) {
22-
dl_head_t *p = dl_pop(head, 0);
23-
my_elem_t *q = dl_container_of(p, my_elem_t, head);
22+
dl_head_t *p = dl_pop(head, 0); // pop_front()
23+
my_elem_t *q = dl_container_of(p, my_elem_t, head); // pointer to the parent struct
2424
printf("out: %d\n", q->x);
25-
free(q);
25+
free(q); // again, caller controls memory
2626
}
2727
return 0;
2828
}

test-macro.c renamed to test-macro1.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
#include <stdlib.h>
22
#include <stdio.h>
3-
#include "dl-macro.h"
3+
#include "dl-macro1.h"
44
DL_IMPL(my, int)
55

66
int main(void)

0 commit comments

Comments
 (0)