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

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since a5b7905 was ea7d2b0, checked in by Thierry Delisle <tdelisle@…>, 8 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.