1 | // |
---|
2 | // Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo |
---|
3 | // |
---|
4 | // The contents of this file are covered under the licence agreement in the |
---|
5 | // file "LICENCE" distributed with Cforall. |
---|
6 | // |
---|
7 | // bits/containers.h -- Intrusive generic containers.h |
---|
8 | // |
---|
9 | // Author : Thierry Delisle |
---|
10 | // Created On : Tue Oct 31 16:38:50 2017 |
---|
11 | // Last Modified By : -- |
---|
12 | // Last Modified On : -- |
---|
13 | // Update Count : 0 |
---|
14 | |
---|
15 | #pragma once |
---|
16 | |
---|
17 | #include <stddef.h> |
---|
18 | |
---|
19 | #include "libhdr.h" |
---|
20 | |
---|
21 | //----------------------------------------------------------------------------- |
---|
22 | // Node Base |
---|
23 | //----------------------------------------------------------------------------- |
---|
24 | |
---|
25 | #ifdef __CFORALL__ |
---|
26 | trait is_node(dtype T) { |
---|
27 | T*& get_next( T& ); |
---|
28 | }; |
---|
29 | #endif |
---|
30 | |
---|
31 | //----------------------------------------------------------------------------- |
---|
32 | // Stack |
---|
33 | //----------------------------------------------------------------------------- |
---|
34 | #ifdef __CFORALL__ |
---|
35 | forall(dtype TYPE | is_node(TYPE)) |
---|
36 | #define T TYPE |
---|
37 | #else |
---|
38 | #define T void |
---|
39 | #endif |
---|
40 | struct __stack { |
---|
41 | T * top; |
---|
42 | }; |
---|
43 | |
---|
44 | #ifdef __CFORALL__ |
---|
45 | #define __stack_t(T) __stack(T) |
---|
46 | #else |
---|
47 | #define __stack_t(T) struct __stack |
---|
48 | #endif |
---|
49 | |
---|
50 | #ifdef __CFORALL__ |
---|
51 | forall(dtype T | is_node(T)) |
---|
52 | void ?{}( __stack(T) & this ) { |
---|
53 | this.top = NULL; |
---|
54 | } |
---|
55 | |
---|
56 | forall(dtype T | is_node(T) | sized(T)) |
---|
57 | void push( __stack(T) & this, T * val ) { |
---|
58 | verify( !get_next( *val ) ); |
---|
59 | get_next( *val ) = this.top; |
---|
60 | this.top = val; |
---|
61 | } |
---|
62 | |
---|
63 | forall(dtype T | is_node(T) | sized(T)) |
---|
64 | T * pop( __stack(T) & this ) { |
---|
65 | T * top = this.top; |
---|
66 | if( top ) { |
---|
67 | this.top = get_next( *top ); |
---|
68 | get_next( *top ) = NULL; |
---|
69 | } |
---|
70 | return top; |
---|
71 | } |
---|
72 | #endif |
---|
73 | |
---|
74 | //----------------------------------------------------------------------------- |
---|
75 | // Queue |
---|
76 | //----------------------------------------------------------------------------- |
---|
77 | #ifdef __CFORALL__ |
---|
78 | forall(dtype T | is_node(T)) |
---|
79 | #define T TYPE |
---|
80 | #else |
---|
81 | #define T void |
---|
82 | #endif |
---|
83 | struct __queue { |
---|
84 | T * head; |
---|
85 | T ** tail; |
---|
86 | }; |
---|
87 | |
---|
88 | #ifdef __CFORALL__ |
---|
89 | forall(dtype T | is_node(T)) |
---|
90 | void ?{}( __queue(T) & this ) { |
---|
91 | this.head = NULL; |
---|
92 | this.tail = &this.head; |
---|
93 | } |
---|
94 | |
---|
95 | forall(dtype T | is_node(T) | sized(T)) |
---|
96 | void append( __queue(T) & this, T * val ) { |
---|
97 | verify(this.tail != NULL); |
---|
98 | *this.tail = val; |
---|
99 | this.tail = &get_next( *val ); |
---|
100 | } |
---|
101 | |
---|
102 | forall(dtype T | is_node(T) | sized(T)) |
---|
103 | T * pop_head( __queue(T) & this ) { |
---|
104 | T * head = this.head; |
---|
105 | if( head ) { |
---|
106 | this.head = get_next( *head ); |
---|
107 | if( !get_next( *head ) ) { |
---|
108 | this.tail = &this.head; |
---|
109 | } |
---|
110 | get_next( *head ) = NULL; |
---|
111 | } |
---|
112 | return head; |
---|
113 | } |
---|
114 | |
---|
115 | forall(dtype T | is_node(T) | sized(T)) |
---|
116 | T * remove( __queue(T) & this, T ** it ) { |
---|
117 | T * val = *it; |
---|
118 | verify( val ); |
---|
119 | |
---|
120 | (*it) = get_next( *val ); |
---|
121 | |
---|
122 | if( this.tail == &get_next( *val ) ) { |
---|
123 | this.tail = it; |
---|
124 | } |
---|
125 | |
---|
126 | get_next( *val ) = NULL; |
---|
127 | |
---|
128 | verify( (this.head == NULL) == (&this.head == this.tail) ); |
---|
129 | verify( *this.tail == NULL ); |
---|
130 | return val; |
---|
131 | } |
---|
132 | #endif |
---|