source: src/libcfa/bits/containers.h @ 1dbc8590

//
// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// bits/containers.h -- Intrusive generic containers.h
//
// Author           : Thierry Delisle
// Created On       : Tue Oct 31 16:38:50 2017
// Last Modified By : --
// Last Modified On : --
// Update Count     : 0

#pragma once

#include "bits/align.h"
#include "bits/defs.h"

//-----------------------------------------------------------------------------
// Array
//-----------------------------------------------------------------------------

#ifdef __cforall
        forall(dtype T)
#else
        #define T void
#endif
struct __small_array {
        T *           data;
        __lock_size_t size;
};
#undef T

#ifdef __cforall
        #define __small_array_t(T) __small_array(T)
#else
        #define __small_array_t(T) struct __small_array
#endif

#ifdef __cforall
        // forall(otype T | sized(T))
        // static inline void ?{}(__small_array(T) & this) {}

        forall(dtype T | sized(T))
        static inline T& ?[?]( __small_array(T) & this, __lock_size_t idx) {
                return ((typeof(this.data))this.data)[idx];
        }

        forall(dtype T | sized(T))
        static inline T& ?[?]( const __small_array(T) & this, __lock_size_t idx) {
                return ((typeof(this.data))this.data)[idx];
        }

        forall(dtype T | sized(T))
        static inline T* begin( const __small_array(T) & this ) {
                return ((typeof(this.data))this.data);
        }

        forall(dtype T | sized(T))
        static inline T* end( const __small_array(T) & this ) {
                return ((typeof(this.data))this.data) + this.size;
        }
#endif

//-----------------------------------------------------------------------------
// Node Base
//-----------------------------------------------------------------------------

#ifdef __cforall
        trait is_node(dtype T) {
                T*& get_next( T& );
        };
#endif

//-----------------------------------------------------------------------------
// Stack
//-----------------------------------------------------------------------------
#ifdef __cforall
        forall(dtype TYPE | is_node(TYPE))
        #define T TYPE
#else
        #define T void
#endif
struct __stack {
        T * top;
};
#undef T

#ifdef __cforall
#define __stack_t(T) __stack(T)
#else
#define __stack_t(T) struct __stack
#endif

#ifdef __cforall
        forall(dtype T | is_node(T))
        static inline void ?{}( __stack(T) & this ) {
                (this.top){ NULL };
        }

        forall(dtype T | is_node(T) | sized(T))
        static inline void push( __stack(T) & this, T * val ) {
                verify( !get_next( *val ) );
                get_next( *val ) = this.top;
                this.top = val;
        }

        forall(dtype T | is_node(T) | sized(T))
        static inline T * pop( __stack(T) & this ) {
                T * top = this.top;
                if( top ) {
                        this.top = get_next( *top );
                        get_next( *top ) = NULL;
                }
                return top;
        }
#endif

//-----------------------------------------------------------------------------
// Queue
//-----------------------------------------------------------------------------
#ifdef __cforall
        forall(dtype TYPE | is_node(TYPE))
        #define T TYPE
#else
        #define T void
#endif
struct __queue {
        T * head;
        T ** tail;
};
#undef T

#ifdef __cforall
#define __queue_t(T) __queue(T)
#else
#define __queue_t(T) struct __queue
#endif

#ifdef __cforall

        forall(dtype T | is_node(T))
        static inline void ?{}( __queue(T) & this ) with( this ) {
                head{ NULL };
                tail{ &head };
        }

        forall(dtype T | is_node(T) | sized(T))
        static inline void append( __queue(T) & this, T * val ) with( this ) {
                verify(tail != NULL);
                *tail = val;
                tail = &get_next( *val );
        }

        forall(dtype T | is_node(T) | sized(T))
        static inline T * pop_head( __queue(T) & this ) {
                T * head = this.head;
                if( head ) {
                        this.head = get_next( *head );
                        if( !get_next( *head ) ) {
                                this.tail = &this.head;
                        }
                        get_next( *head ) = NULL;
                }
                return head;
        }

        forall(dtype T | is_node(T) | sized(T))
        static inline T * remove( __queue(T) & this, T ** it ) with( this ) {
                T * val = *it;
                verify( val );

                (*it) = get_next( *val );

                if( tail == &get_next( *val ) ) {
                        tail = it;
                }

                get_next( *val ) = NULL;

                verify( (head == NULL) == (&head == tail) );
                verify( *tail == NULL );
                return val;
        }
#endif


//-----------------------------------------------------------------------------
// Doubly Linked List
//-----------------------------------------------------------------------------
#ifdef __cforall
        trait is_db_node(dtype T) {
                T*& get_next( T& );
                T*& get_prev( T& );
        };
#endif

#ifdef __cforall
        forall(dtype TYPE | is_db_node(TYPE))
        #define T TYPE
#else
        #define T void
#endif
struct __dllist {
        T * head;
};
#undef T

#ifdef __cforall
#define __dllist_t(T) __dllist(T)
#else
#define __dllist_t(T) struct __dllist
#endif

#ifdef __cforall

        forall(dtype T | is_db_node(T))
        static inline void ?{}( __dllist(T) & this ) with( this ) {
                head{ NULL };
        }

        // forall(dtype T | is_db_node(T) | sized(T))
        // static inline void push_front( __dllist(T) & this, T & node ) with( this ) {
        //      if ( head ) {
        //              get_next( node ) = head;
        //              get_prev( node ) = get_prev( *head );
        //              // inserted node must be consistent before it is seen
        //              // prevent code movement across barrier
        //              asm( "" : : : "memory" );
        //              get_prev( *head ) = node;
        //              T & prev = *get_prev( node );
        //              get_next( prev ) = node;
        //      }
        //      else {
        //              get_next( node ) = &node;
        //              get_prev( node ) = &node;
        //      }

        //      // prevent code movement across barrier
        //      asm( "" : : : "memory" );
        //      head = val;
        // }

        // forall(dtype T | is_db_node(T) | sized(T))
        // static inline T * remove( __dllist(T) & this, T & node ) with( this ) {
        //      if ( &node == head ) {
        //              if ( get_next( *head ) == head ) {
        //                      head = NULL;
        //              }
        //              else {
        //                      head = get_next( *head );
        //              }
        //      }
        //      get_prev( *get_next( node ) ) = get_prev( node );
        //      get_next( *get_prev( node ) ) = get_next( node );
        //      get_next( node ) = NULL;
        //      get_prev( node ) = NULL;
        // }
#endif

//-----------------------------------------------------------------------------
// Tools
//-----------------------------------------------------------------------------
#ifdef __cforall

#endif