w_list.h

Go to the documentation of this file.

/* -*- mode:C++; c-basic-offset:4 -*-
     Shore-MT -- Multi-threaded port of the SHORE storage manager
   
                       Copyright (c) 2007-2009
      Data Intensive Applications and Systems Labaratory (DIAS)
               Ecole Polytechnique Federale de Lausanne
   
                         All Rights Reserved.
   
   Permission to use, copy, modify and distribute this software and
   its documentation is hereby granted, provided that both the
   copyright notice and this permission notice appear in all copies of
   the software, derivative works or modified versions, and any
   portions thereof, and that both notices appear in supporting
   documentation.
   
   This code is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS
   DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER
   RESULTING FROM THE USE OF THIS SOFTWARE.
*/

/*<std-header orig-src='shore' incl-file-exclusion='W_LIST_H'>

 $Id: w_list.h,v 1.56 2010/07/26 23:37:09 nhall Exp $

SHORE -- Scalable Heterogeneous Object REpository

Copyright (c) 1994-99 Computer Sciences Department, University of
                      Wisconsin -- Madison
All Rights Reserved.

Permission to use, copy, modify and distribute this software and its
documentation is hereby granted, provided that both the copyright
notice and this permission notice appear in all copies of the
software, derivative works or modified versions, and any portions
thereof, and that both notices appear in supporting documentation.

THE AUTHORS AND THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY
OF WISCONSIN - MADISON ALLOW FREE USE OF THIS SOFTWARE IN ITS
"AS IS" CONDITION, AND THEY DISCLAIM ANY LIABILITY OF ANY KIND
FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.

This software was developed with support by the Advanced Research
Project Agency, ARPA order number 018 (formerly 8230), monitored by
the U.S. Army Research Laboratory under contract DAAB07-91-C-Q518.
Further funding for this work was provided by DARPA through
Rome Research Laboratory Contract No. F30602-97-2-0247.

*/

#ifndef __W_LIST_H
#define __W_LIST_H

#include "w_defines.h"

/*  -- do not edit anything above this line --   </std-header>*/

#ifndef __W_BASE_H
#include "w_base.h"
#endif // __W_BASE_H

#include <iostream>

class w_list_base_t;

template<class T, class LOCK> class w_list_t;

template<class T, class LOCK> class w_list_i;

template<class T, class LOCK, class K> class w_hash_t;

class unsafe_list_dummy_lock_t {};

unsafe_list_dummy_lock_t* const unsafe_nolock = nullptr; // instantiate with this


class w_link_t {
public:
    w_link_t();

    ~w_link_t();

    w_link_t(const w_link_t&);

    w_link_t& operator=(const w_link_t&);

    void attach(w_link_t* prev_link);

    void check() {
        w_assert9(_prev == this && _next == this); // not in a list
    }

    w_link_t* detach();

    w_list_base_t* member_of() const;

    w_link_t* next() const;

    w_link_t* prev() const;

private:
    w_list_base_t* _list;

    w_link_t* _next;

    w_link_t* _prev;

    friend class w_list_base_t;
};

class w_list_base_t : public w_vbase_t {

public:
    bool is_empty() const;

    uint32_t num_members() const;

    void dump();

protected:
    w_list_base_t();

    w_list_base_t(uint32_t offset);

    ~w_list_base_t();

    void set_offset(uint32_t offset);

    w_link_t _tail;

    uint32_t _cnt;

    uint32_t _adj;

private:
    w_list_base_t(w_list_base_t&); // disabled

    w_list_base_t& operator=(w_list_base_t&);

    friend class w_link_t;
};

inline w_link_t::w_link_t() :
        _list(0) {
    _next = this;
    _prev = this;
    /* empty body */
}

inline w_link_t::~w_link_t() {
    w_assert1(_next == this && _prev == this && _list == 0);
}

inline w_link_t::w_link_t(const w_link_t&) :
        _list(0) {
    _next = _prev = this;
}

inline w_link_t& w_link_t::operator=(const w_link_t&) {
    _list = 0;
    return *(_next = _prev = this);
}

inline w_list_base_t* w_link_t::member_of() const {
    return _list;
}

inline w_link_t* w_link_t::prev() const {
    return _prev;
}

inline w_link_t* w_link_t::next() const {
    return _next;
}

inline w_list_base_t::w_list_base_t() :
        _cnt(0),
        _adj(uint4_max) { // _adj must be set by a later call
// to set_offset().  We init _adj with a large number to detect
// errors
    _tail._list = 0;
    w_assert9(_tail._next == &_tail && _tail._prev == &_tail);
}

inline w_list_base_t::w_list_base_t(uint32_t offset) :
        _cnt(0),
        _adj(offset) {
    _tail._list = this;
    w_assert9(_tail._next == &_tail && _tail._prev == &_tail);
}

inline void w_list_base_t::set_offset(uint32_t offset) {
    w_assert9(_cnt == 0 && _adj == uint4_max && _tail._list == 0);
    _tail._list = this;
    _adj = offset;
}

inline w_list_base_t::~w_list_base_t() {
    _tail._list = 0;
    w_assert9(_cnt == 0);
}

inline bool w_list_base_t::is_empty() const {
    return _cnt == 0;
}

inline uint32_t w_list_base_t::num_members() const {
    return _cnt;
}

template<class T, class L> class w_list_t;

BIND_FRIEND_OPERATOR_PART_1(T, L, w_list_t<T, L>)


template<class T, class LOCK>
class w_list_t : public w_list_base_t {
protected:
    w_link_t* link_of(T* t) {
        w_assert3(t);
        return CAST(w_link_t*, CAST(char * , t) + _adj);
    }

    const w_link_t* link_of(const T* t) const {
        w_assert3(t);
        return CAST(w_link_t*, CAST(char * , t) + _adj);
    }

    T* base_of(w_link_t* p) const {
        w_assert3(p);
        return CAST(T*, CAST(char * , p) - _adj);
    }

    const T* base_of(const w_link_t* p) const {
        w_assert3(p);
        return CAST(T*, CAST(char * , p) - _adj);
    }

private:
    LOCK* lock;

public:

    w_list_t(uint32_t link_offset, LOCK* l) :
            w_list_base_t(link_offset),
            lock(l) {
#ifdef __GNUC__
#else
        w_assert2(link_offset + sizeof(w_link_t) <= sizeof(T));
#endif
    }

public:
    // This is used by w_hash_t  and the lock manager's list of lock heads
    w_list_t() : lock(nullptr) {}

public:

    ~w_list_t() {}

    void set_offset(uint32_t link_offset) {
        w_list_base_t::set_offset(link_offset);
    }

    virtual void put_in_order(T* t) {
        w_list_t<T, LOCK>::push(t);
    }

    // a set of consistent and intuitive names
    // TODO: replace throughout the SM
    w_list_t<T, LOCK>& push_front(T* t) {
        return push(t);
    }

    w_list_t<T, LOCK>& push_back(T* t) {
        return append(t);
    }

    T* front() {
        return top();
    }

    T* back() {
        return bottom();
    }

    T* pop_front() {
        return pop();
    }

    T* pop_back() {
        return chop();
    }

    w_list_t<T, LOCK>& push(T* t) {
        link_of(t)->attach(&_tail);
        return *this;
    }

    w_list_t<T, LOCK>& append(T* t) {
        link_of(t)->attach(_tail.prev());
        return *this;
    }

    // Insert t after pos (for log buffer)
    void insert_after(T* t, T* pos) {
        link_of(t)->attach(link_of(pos));
    }

    // Insert t before pos (for log buffer)
    void insert_before(T* t, T* pos) {
        link_of(t)->attach(link_of(pos)->prev());
    }

    T* pop() {
        return _cnt ? base_of(_tail.next()->detach()) : 0;
    }

    T* chop() {
        return _cnt ? base_of(_tail.prev()->detach()) : 0;
    }

    // Remove t (for log buffer)
    void remove(T* t) {
        link_of(t)->detach();
    }

    T* top() {
        return _cnt ? base_of(_tail.next()) : 0;
    }

    T* bottom() {
        return _cnt ? base_of(_tail.prev()) : 0;
    }

    T* next(w_link_t* p) {
        w_assert1(p->member_of() == this);
        return base_of(p->next());
    }

    T* prev(w_link_t* p) {
        w_assert1(p->member_of() == this);
        return base_of(p->prev());
    }

    // Get next (for log buffer)
    T* next_of(T* t) {
        w_link_t* p = link_of(t);
        w_assert1(p->member_of() == this);
        if (p->next() != &_tail) {
            return base_of(p->next());
        } else {
            return nullptr;
        }
    }

    // Get prev (for log buffer)
    T* prev_of(T* t) {
        w_link_t* p = link_of(t);
        w_assert1(p->member_of() == this);
        if (p->prev() != &_tail) {
            return base_of(p->prev());
        } else {
            return nullptr;
        }
    }

    // Get count
    uint32_t count() {
        return this->_cnt;
    }

    friend ostream& operator<<BIND_FRIEND_OPERATOR_PART_2(T, LOCK)(
            ostream& o,
            const w_list_t<T, LOCK>& l);

private:
    // disabled
    w_list_t(const w_list_t<T, LOCK>& x);

    w_list_t<T, LOCK>& operator=(const w_list_t<T, LOCK>&);

    friend class w_list_i<T, LOCK>;
};

#define    W_LIST_ARG(class, member)    w_offsetof(class,member)

template<class T, class LOCK>
class w_list_i : public w_base_t {
public:
    w_list_i()
            : _list(0),
              _next(0),
              _curr(0),
              _backwards(false) {};

    w_list_i(const w_list_t<T, LOCK>& l, bool backwards = false)
            : _list(&l),
              _curr(0),
              _backwards(backwards) {
        _next = (backwards ? l._tail.prev() : l._tail.next());
    }

    virtual ~w_list_i() {};

    void reset(const w_list_t<T, LOCK>& l, bool backwards = false) {
        _list = &l;
        _curr = 0;
        _backwards = backwards;
        _next = (_backwards ? l._tail.prev() : l._tail.next());
    }

    T* next() {
        if (_next) {
            _curr = (_next == &(_list->_tail)) ? 0 : _list->base_of(_next);
            _next = (_backwards ? _next->prev() : _next->next());
            // Note: once we ever had anything in the list, next() will
            // be non-null. We will return NULL when _curr hits the tail.
            // _next can be null only if we started with an empty list.
            w_assert1(_next != nullptr);
        }
        return _curr;
    }

    T* curr() const {
        return _curr;
    }

protected:
    const w_list_t<T, LOCK>* _list;

private:
    w_link_t* _next;

    T* _curr;

    bool _backwards;

    // disabled
    w_list_i(w_list_i<T, LOCK>&);

    w_list_i<T, LOCK>& operator=(w_list_i<T, LOCK>&);
};

template<class T, class LOCK>
class w_list_const_i : public w_list_i<T, LOCK> {
public:
    w_list_const_i() {};

    w_list_const_i(const w_list_t<T, LOCK>& l) :
            w_list_i<T, LOCK>(*(w_list_t<T, LOCK>*)(&l)) {};

    ~w_list_const_i() {};

    void reset(const w_list_t<T, LOCK>& l) {
        w_list_i<T, LOCK>::reset(*(w_list_t<T, LOCK>*)(&l));
    }

    const T* next() {
        return w_list_i<T, LOCK>::next();
    }

    const T* curr() const {
        return w_list_i<T, LOCK>::curr();
    }

private:
    // disabled
    w_list_const_i(w_list_const_i<T, LOCK>&);

    w_list_const_i<T, LOCK>& operator=(w_list_const_i<T, LOCK>&);
};

template<class T, class LOCK, class K>
class w_keyed_list_t : public w_list_t<T, LOCK> {
public:
    T* first() {
        return w_list_t<T, LOCK>::top();
    }

    T* last() {
        return w_list_t<T, LOCK>::bottom();
    }

    virtual T* search(const K& k);

    w_keyed_list_t(LOCK* lock);

    w_keyed_list_t(uint32_t key_offset, uint32_t link_offset,
                   LOCK* lock);

    ~w_keyed_list_t() {};

    void set_offset(uint32_t key_offset, uint32_t link_offset);

protected:
    const K& key_of(const T& t) {
        return *(K*)(((const char*)&t) + _key_offset);
    }

    using w_list_t<T, LOCK>::_tail;
    using w_list_t<T, LOCK>::base_of;

private:
    // disabled
    w_keyed_list_t(const w_keyed_list_t<T, LOCK, K>&);

    uint32_t _key_offset;

    // disabled
    w_list_t<T, LOCK>& push(T* t);

    w_list_t<T, LOCK>& append(T* t);

    T* chop();

    T* top();

    T* bottom();
};

#define    W_KEYED_ARG(class, key, link)    \
    W_LIST_ARG(class,key), W_LIST_ARG(class,link)

template<class T, class LOCK, class K>
class w_ascend_list_t : public w_keyed_list_t<T, LOCK, K> {
    using w_keyed_list_t<T, LOCK, K>::_tail;
    using w_keyed_list_t<T, LOCK, K>::base_of;

public:
    w_ascend_list_t(uint32_t key_offset, uint32_t link_offset,
                    LOCK* lock) :
            w_keyed_list_t<T, LOCK, K>(key_offset, link_offset, lock) {};

    ~w_ascend_list_t() {};

    virtual T* search(const K& k);

    virtual void put_in_order(T* t);

private:
    w_ascend_list_t(const w_ascend_list_t<T, LOCK, K>&); // disabled
};

template<class T, class LOCK, class K>
class w_descend_list_t : public w_keyed_list_t<T, LOCK, K> {
    using w_keyed_list_t<T, LOCK, K>::_tail;
    using w_keyed_list_t<T, LOCK, K>::base_of;

public:
    w_descend_list_t(uint32_t key_offset, uint32_t link_offset,
                     LOCK* l) :
        w_keyed_list_t<T, LOCK, K>(key_offset, link_offset, l) {};

    ~w_descend_list_t() {};

    virtual T* search(const K& k);

    virtual void put_in_order(T* t);

private:
    w_descend_list_t(const w_descend_list_t<T, LOCK, K>&); // disabled
};

template<class T, class LOCK>
ostream& operator<<(ostream& o, const w_list_t<T, LOCK>& l) {
    const w_link_t* p = l._tail.next();

    cout << "cnt = " << l.num_members();

    while (p != &l._tail) {
        const T* t = l.base_of(p);
        if (!(o << endl << '\t' << *t)) {
            break;
        }
        p = p->next();
    }
    return o;
}

template<class T, class LOCK, class K>
w_keyed_list_t<T, LOCK, K>::w_keyed_list_t(
        uint32_t key_offset,
        uint32_t link_offset,
        LOCK* lock
                                          )
        : w_list_t<T, LOCK>(link_offset, lock),
          _key_offset(key_offset) {
#ifdef __GNUC__
#else
    w_assert9(key_offset + sizeof(K) <= sizeof(T));
#endif
}

template<class T, class LOCK, class K>
w_keyed_list_t<T, LOCK, K>::w_keyed_list_t(LOCK* l) :
        w_list_t<T, LOCK>(0, l),
        _key_offset(0) {}

template<class T, class LOCK, class K>
void
w_keyed_list_t<T, LOCK, K>::set_offset(uint32_t key_offset,
                                       uint32_t link_offset) {
    w_assert3(_key_offset == 0);
    w_list_t<T, LOCK>::set_offset(link_offset);
    _key_offset = key_offset;
}

template<class T, class LOCK, class K>
T*
w_keyed_list_t<T, LOCK, K>::search(const K& k) {
    w_link_t* p;
    for (p = _tail.next();
         p != &_tail && (key_of(*base_of(p)) != k);
         p = p->next()) {}
    return (p && (p != &_tail)) ? base_of(p) : 0;
}

template<class T, class LOCK, class K>
T*
w_ascend_list_t<T, LOCK, K>::search(const K& k) {
    w_link_t* p;
    for (p = _tail.next();
         p != &_tail && (this->key_of(*base_of(p)) < k);
         p = p->next()) {}

    return p ? base_of(p) : 0;
}

template<class T, class LOCK, class K>
void
w_ascend_list_t<T, LOCK, K>::put_in_order(T* t) {
    w_link_t* p;
    for (p = _tail.next();
         p != &_tail && (this->key_of(*base_of(p)) <= this->key_of(*t));
         p = p->next()) {}

    if (p) {
        this->link_of(t)->attach(p->prev());
    } else {
        this->link_of(t)->attach(_tail.prev());
    }
}

template<class T, class LOCK, class K>
T*
w_descend_list_t<T, LOCK, K>::search(const K& k) {
    w_link_t* p;
    for (p = _tail.next();
         p != &_tail && (this->key_of(*base_of(p)) > k);
         p = p->next()) {}

    return p ? base_of(p) : 0;
}

template<class T, class LOCK, class K>
void
w_descend_list_t<T, LOCK, K>::put_in_order(T* t) {
    w_link_t* p;
    for (p = _tail.next();
         p != &_tail && (this->key_of(*base_of(p)) >= this->key_of(*t));
         p = p->next()) {}

    if (p) {
        this->link_of(t)->attach(p->prev());
    } else {
        this->link_of(t)->attach(_tail.prev());
    }
}
/*<std-footer incl-file-exclusion='W_LIST_H'>  -- do not edit anything below this line -- */

#endif // __W_LIST_H /*</std-footer>*/