source: src/libcfa/bits/containers.h @ ea7d2b0

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since ea7d2b0 was ea7d2b0, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Moved spinlocks to bits/locks.h

  • Property mode set to 100644
File size: 2.8 KB
Line 
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
40struct __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
83struct __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
Note: See TracBrowser for help on using the repository browser.