cs_set.hpp

Go to the documentation of this file.

/*
 *      Copyright (c) 2023, an unpublished work by CodeSecure, Inc.
 *                      ALL RIGHTS RESERVED
 *
 *      Copyright (c) 2013-2023, an unpublished work by GrammaTech, Inc.
 *                      ALL RIGHTS RESERVED
 *
 *      This software is furnished under a license and may be used and
 *      copied only in accordance with the terms of such license and the
 *      inclusion of the above copyright notice.  This software or any
 *      other copies thereof may not be provided or otherwise made
 *      available to any other person.  Title to and ownership of the
 *      software is retained by CodeSecure, Inc.
 */

#ifndef CS_SET_HPP
#define CS_SET_HPP

#include "cs_utility.h"
/* Provide an STL-set-compatible interface to the various set types. */
#include "cs_iterator_adapter.hpp"

namespace cs{
    template<typename elt> class set_impl;
    template<typename elt> class set_iterator_policy;
    template<typename elt> class mutable_set;
    template<typename elt> class immutable_set;
    template<typename derived> class set_mixin;
    /* Do not define a default instantiation for set_mixin... SWIG has
     * a tendency to silently use it when it should not. 
     */

    class set_kind{
        typedef std::pair<csuint32, csuint32> int_pair_t;
        CS_ENUM_BOILERPLATE_UB(set_kind, cs_set_kind,
                               check(cs_set_kind_name(
                                         inner, &rv)),
                               cs_set_kind_count);
#include "cs_set_kind_decls.hpp"
    };
    CS_ENUM_BOILERPLATE_FRIENDS(set_kind,
                                friend class mutable_set<symbol>;
                                friend class mutable_set<point>;
                                friend class mutable_set<basic_block>;
                                friend class mutable_set<set_kind::int_pair_t>;,
                                cs
        )
#include "cs_set_kind_defs.hpp"
  
  // Don't hide from doxygen

    template<typename T>
    class intrusive
    {
        T *p;
    public:
        intrusive()
            : p(0){}
        intrusive(T *_p)
            : p(_p)
        { p->incref(); }
        intrusive(const intrusive &other)
            : p(other.p)
        { p->incref(); }
        ~intrusive()
        { if( p ) p->decref(); }
        void
        swap(intrusive& other)
        { std::swap(p, other.p); }
        T &operator*() const
        { return *p; }
        T *operator->() const
        { return p; }
        intrusive&
        operator=(intrusive other)
        {
            swap(other);
            return *this;
        }
    };
}

#ifndef SWIG
namespace std{
  template<typename T>
  inline void
  swap(cs::intrusive<T>& __x, cs::intrusive<T>& __y)
    { __x.swap(__y); }
}
#endif

namespace cs{

    template<typename elt> 
    class immutable_set
    {
        friend class cglue< immutable_set<elt> >;
        immutable_set();
        typedef set_impl<elt> impl;
        intrusive<impl> inner;
    public:
        typedef elt              key_type;

        typedef elt              value_type;
 
        typedef elt             *pointer;
 
       typedef const elt       *const_pointer;

        typedef elt             &reference;

        typedef const elt       &const_reference;

        typedef iterator_adapter<set_iterator_policy<elt> > iterator;

        typedef iterator         const_iterator;

        typedef size_t           size_type;
        
    private:
        typedef typename impl::ctype ctype;

        immutable_set(ctype s, bool _frozen): 
            inner(new impl(s, _frozen)){}

        ctype unwrap() const
        { return inner->unwrap(); }

    public:

        immutable_set(const immutable_set& other): inner(other.inner) { }
        
        immutable_set&
        operator=(immutable_set other)
        {
            swap(other);
            return *this;
        }

#if !defined(SWIGPYTHON) || !defined(SWIG)

        iterator
        begin() const
        { return iterator(inner); }

        iterator
        end() const
        { return iterator(); }

        iterator
        cbegin() const
        { return iterator(inner); }

        iterator
        cend() const
        { return iterator(); }
#endif

        bool
        empty() const
        { return inner->empty(); }


        size_type
        size() const
        { return inner->size(); }

        void
        swap(immutable_set& other)
        { std::swap(inner, other.inner); }

#if !defined(SWIGPYTHON) || !defined(SWIG)

        size_type
        count(const elt& e) const
        { return inner->member(cglue<elt>::unwrap(e))?1:0; }


        const_iterator
        find(const elt& e) const
        {
            return inner->member(cglue<elt>::unwrap(e))
                ? iterator(cglue<elt>::unwrap(e))
                : iterator(); 
        }
#endif

        CS_BOILERPLATE_HASH_TYPE hash() const
        { return inner->hash(); }

        std::vector<elt> to_vector() const
        { 
            std::vector<elt> v;
            v.reserve(size());
            for( const_iterator it = cbegin(); it != cend(); ++it )
                v.push_back(*it);
            return v;
        }

    private:
        void print(std::ostream &out) const
        {
            out << "{";
            size_t i = 0;
            for( const_iterator it = cbegin(); it != cend(); ++it )
            {
                switch( i )
                {
                case 3:
                    out << ", ";
                    out << (size() - i)
                        << " more...";
                    goto really_break;
                case 2:
                case 1:
                    out << ", ";
                case 0:
                    ostream_helper(*it, out);
                    break;
                }
                ++i;
            }
        really_break:
            out << "}";
        }

    public:
        std::string as_string() const
        {
            std::stringstream buf;
            print(buf);
            return buf.str();
        }
        
        std::string as_repr() const
        {
            std::stringstream buf;
            buf << CS_AS_REPR_PREFIX
                << impl::type_name()
                << " ";
            print(buf);
            buf <<  CS_AS_REPR_SUFFIX;
            return buf.str();
        }

        /* swig produces a nicer interface if all operators are member
         * functions.
         */
#ifdef SWIG_BUILD
#if defined(SWIGPYTHON) && defined(SWIG)
        %extend{
            bool __contains__(const elt& e) const
            { return $self->count(e) != 0; }

            iterator __iter__() const
            { return $self->cbegin(); }
        };
#endif
        
        bool operator==(const immutable_set &other) const
        { return inner->equals(*other.inner); }
        
        bool operator!=(const immutable_set &other) const
        { return !(*this == other); }
#else

        template<typename _impl1>
        friend bool
        operator==(const immutable_set<_impl1>&, const immutable_set<_impl1>&);
#endif
    };

    /* swig doesn't do what we want with friend functions */
#ifndef SWIG

  template<typename _Impl>
    inline bool
    operator==(const immutable_set<_Impl>& __x,
               const immutable_set<_Impl>& __y)
  { return __x.inner->equals(__y.inner); }

  template<typename _Impl>
    inline bool
    operator!=(const immutable_set<_Impl>& __x,
               const immutable_set<_Impl>& __y)
    { return !(__x == __y); }
}
namespace std{
    template<typename _Impl>
    inline void
    swap(cs::immutable_set<_Impl>& __x, cs::immutable_set<_Impl>& __y)
    { __x.swap(__y); }
}
namespace cs{
#endif

    template<typename elt> 
    class mutable_set: public set_mixin<mutable_set<elt> >
    {
        friend class cglue< mutable_set<elt> >;
        typedef set_impl<elt> impl;
        typedef set_iterator_policy<elt> iterator_policy;
        intrusive<impl> inner;
    public:
        typedef elt              key_type;   

        typedef elt              value_type;

        typedef elt             *pointer;

        typedef const elt       *const_pointer;

        typedef elt             &reference;

        typedef const elt       &const_reference;

        typedef iterator_adapter<iterator_policy> iterator;

        typedef iterator         const_iterator;

        typedef size_t           size_type;

        typedef typename impl::ctype ctype;
        /* fork() will take care of doing an actual deep copy, if it
         * becomes necessary. 
         */
        mutable_set(const mutable_set& other): inner(other.inner) { }
        
        mutable_set&
        operator=(mutable_set other)
        {
            swap(other);
            return *this;
        }

    private:
        ctype unwrap() const
        {
            return inner->unwrap();
        }

    public:
        set_kind kind() const
        {
            return cglue<set_kind>::wrap(inner->kind());
        }

#if !defined(SWIGPYTHON) || !defined(SWIG)

        iterator
        begin() const
        { return iterator(inner); }

        iterator
        end() const
        { return iterator(); }

        iterator
        cbegin() const
        { return iterator(inner); }

        iterator
        cend() const
        { return iterator(); }
#endif


        bool
        empty() const
        { return inner->empty(); }


        size_type
        size() const
        { return inner->size(); }

        void
        swap(mutable_set& other)
        { std::swap(inner, other.inner); }

#if !defined(SWIGPYTHON) || !defined(SWIG)

        size_type
        count(const elt& e) const
        { return inner->member(cglue<elt>::unwrap(e))?1:0; }

        const_iterator
        find(const elt& e) const
        {
            return inner->member(cglue<elt>::unwrap(e))
                ? iterator(cglue<elt>::unwrap(e))
                : iterator();
        }
#endif

        CS_BOILERPLATE_HASH_TYPE hash() const
        { return inner->hash(); }

        /* Alternate, slower implementation:
        std::vector<elt> to_vector() const
        { return std::vector<elt>(cbegin(), cend()); }
        */
        
        std::vector<elt> to_vector() const
        { 
            std::vector<elt> v;
            v.reserve(size());
            for( const_iterator it = cbegin(); !it.at_end(); ++it )
                v.push_back(*it);
            return v;
        }

        mutable_set(): inner(new impl()){}

        mutable_set(set_kind k): inner(new impl(cglue<set_kind>::unwrap(k))){}

    private:
        mutable_set(ctype s, 
                    bool frozen)
            : inner(new impl(s, frozen)){}
        
        ctype multi_union(const std::vector<mutable_set<impl> > &v)
        {
            ctype *csets = new ctype[v.size()];
            size_t i;
            ctype rv;
            cs_result r;
            memset( &rv, 0, sizeof(rv) );
            for( i = 0; i < v.size(); i++ )
                csets[i] = v[i].unwrap();
            r = impl::multi_union(csets, v.size(), rv);
            delete[] csets;
            check(r);
            return rv;
        }
    public:
#ifndef SWIG
        /* SWIG chokes on this vector type, so swig users will have to
         * live without it. 
         */
        mutable_set(const std::vector<mutable_set<impl> > &v)
            : inner(new impl(multi_union(v), false)){}
#endif
        
        mutable_set(const std::vector<elt> &v)
            : inner(new impl())
        {
            size_t i;
            for( i = 0; i < v.size(); i++ )
                add(v[i]);
        }
        
    private:
        void fork()
        {
            if( inner->shared() )
            {
                /* An iterator is using it... We can't mutate it, but
                 * we can create a copy and mutate that.
                 */
                inner = new impl(*inner);
            }
        }
    public:
        
        /* Like insert, but doesn't return the iterator. */
        bool
        add(const elt& v)
        { 
            fork();
            cs_result r = inner->put(cglue<elt>::unwrap(v));
            /* The order of this container isn't really well-defined,
             * so return an iterator that just iterates over the one
             * value. 
             */
            if( r == CS_ELEMENT_ALREADY_PRESENT )
                return false;
            check(r);
            return true;
        }

#ifndef SWIG

        std::pair<iterator, bool>
        insert(const elt& v)
        { 
            /* The order of this container isn't really well-defined,
             * so return an iterator that just iterates over the one
             * value. 
             */
            return std::pair<iterator, bool>(
                iterator(cglue<elt>::unwrap(v)), 
                add(v));
        }
#endif

        /* python prefers remove/discard naming convention */
#if defined(SWIG) && defined(SWIGPYTHON)
        %rename(_erase) erase;
#endif

        size_type
        erase(const elt& v)
        { 
            fork();
            cs_result r = inner->del(cglue<elt>::unwrap(v));
            if( r == CS_ELEMENT_NOT_PRESENT )
                return 0;
            check(r);
            return 1;
        }

        void
        clear()
        { inner = new impl(); }

#if defined(SWIG) && defined(SWIGPYTHON)
        %rename(_union) union_;
#endif

        mutable_set union_(const mutable_set& b) const
        { return mutable_set(inner->union_(*b.inner), false); }


        void union_p(const mutable_set& b)
        {
            fork();
            inner->union_p(*b.inner);
        }


        mutable_set intersect(const mutable_set& b) const
        { return mutable_set(inner->intersect(*b.inner), false); }


        mutable_set difference(const mutable_set& b) const
        { return mutable_set(inner->difference(*b.inner), false); }
        
    private:
        void print(std::ostream &out) const
        {
            out << "{";
            size_t i = 0;
            for( const_iterator it = cbegin(); it != cend(); ++it )
            {
                switch( i )
                {
                case 3:
                    out << ", ";
                    out << (size() - i)
                        << " more...";
                    goto really_break;
                case 2:
                case 1:
                    out << ", ";
                case 0:
                    ostream_helper(*it, out);
                    break;
                }
                ++i;
            }
        really_break:
            out << "}";
        }

    public:
        std::string as_string() const
        {
            std::stringstream buf;
            print(buf);
            return buf.str();
        }
        
        std::string as_repr() const
        {
            std::stringstream buf;
            buf << CS_AS_REPR_PREFIX
                << impl::type_name()
                << " ";
            print(buf);
            buf <<  CS_AS_REPR_SUFFIX;
            return buf.str();
        }

        /* swig produces a nicer interface if all operators are member
         * functions.
         */
#ifdef SWIG_BUILD
#if defined(SWIGPYTHON) && defined(SWIG)
        %extend{
            bool __contains__(const elt& e) const
            { return $self->count(e) != 0; }
            
            iterator __iter__() const
            { return $self->cbegin(); }

            %pythoncode{
                 def remove(self, v): 
                     if not self._erase(v):
                         raise KeyError(v)
                 def discard(self, v): self._erase(v)
                 def union(self, other):
                     return self._union(other)}
        };
#endif

        bool operator==(const mutable_set &other) const
        { return inner->equals(*other.inner); }
        
        bool operator!=(const mutable_set &other) const
        { return !(*this == other); }
#else

        template<typename _impl1>
        friend bool
        operator==(const mutable_set<_impl1>&, const mutable_set<_impl1>&);
#endif
    };

    template<typename elt>
    inline std::ostream &operator<<( 
        std::ostream &out, 
        const mutable_set<elt> &a )
    { 
        a.print(out);
        return out; 
    }

    template<typename elt>
    class cglue< immutable_set<elt> >
    {
        cglue();
    public:
        typedef typename set_impl<elt>::ctype ctype;
        typedef immutable_set<elt> type;
    CS_CXX_API_CGLUE_ACCESS_MODIFIER:
        /* Since we have no friends, no point in defining these.
         * Instantiations can specialize cglue to make friends. 
         */
#if 0
        static type wrap(const ctype &c, bool frozen)
        { return type(c, frozen); }
        static ctype unwrap(const type &c)
        { return c.unwrap(); }
#endif
    };

    template<typename elt>
    inline std::ostream &operator<<( 
        std::ostream &out, 
        const immutable_set<elt> &a )
    {
        a.print(out);
        return out; 
    }

    template<typename elt>
    class cglue< mutable_set<elt> >
    {
        cglue();
    public:
        typedef typename set_impl<elt>::ctype ctype;
        typedef mutable_set<elt> type;
    CS_CXX_API_CGLUE_ACCESS_MODIFIER:
        /* Since we have no friends, no point in defining these.
         * Instantiations can specialize cglue to make friends. 
         */
#if 0
        static type wrap(const ctype &c, bool frozen)
        { return type(c, frozen); }
        static ctype unwrap(const type &c)
        { return c.unwrap(); }
#endif
    };

    /* swig doesn't do what we want with friend functions */
#ifndef SWIG
  template<typename _Elt>
    inline bool
    operator==(const mutable_set<_Elt>& __x,
               const mutable_set<_Elt>& __y)
  { return __x.inner->equals(__y.inner); }

  //  Returns !(x == y).
  template<typename _Elt>
    inline bool
    operator!=(const mutable_set<_Elt>& __x,
               const mutable_set<_Elt>& __y)
    { return !(__x == __y); }
#endif
}
#ifndef SWIG
namespace std{
  template<typename _Elt>
  inline void
  swap(cs::mutable_set<_Elt>& __x, cs::mutable_set<_Elt>& __y)
    { __x.swap(__y); }
}
#endif

#endif /* CS_SET_HPP */