From 0b806ee0fc9097fa7bda7ac0109191c9c5e0a1ac Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Sun, 9 Feb 2014 22:10:30 -0300 Subject: GODOT IS OPEN SOURCE --- core/vector.h | 401 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 401 insertions(+) create mode 100644 core/vector.h (limited to 'core/vector.h') diff --git a/core/vector.h b/core/vector.h new file mode 100644 index 0000000000..90a9bf715b --- /dev/null +++ b/core/vector.h @@ -0,0 +1,401 @@ +/*************************************************************************/ +/* vector.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* http://www.godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ +#ifndef VECTOR_H +#define VECTOR_H + +/** + * @class Vector + * @author Juan Linietsky + * Vector container. Regular Vector Container. Use with care and for smaller arrays when possible. Use DVector for large arrays. +*/ +#include "os/memory.h" +#include "error_macros.h" +#include "safe_refcount.h" +#include "sort.h" + +template +class Vector { + + mutable void* _ptr; + + // internal helpers + + _FORCE_INLINE_ SafeRefCount* _get_refcount() const { + + if (!_ptr) + return NULL; + + return reinterpret_cast(_ptr); + } + + _FORCE_INLINE_ int* _get_size() const { + + if (!_ptr) + return NULL; + return reinterpret_cast(((uint8_t*)(_ptr))+sizeof(SafeRefCount)); + + } + _FORCE_INLINE_ T* _get_data() const { + + if (!_ptr) + return NULL; + return reinterpret_cast(((uint8_t*)(_ptr))+sizeof(SafeRefCount)+sizeof(int)); + + } + + _FORCE_INLINE_ int _get_alloc_size(int p_elements) const { + + return nearest_power_of_2(p_elements*sizeof(T)+sizeof(SafeRefCount)+sizeof(int)); + } + + void _unref(void *p_data); + + void _copy_from(const Vector& p_from); + void _copy_on_write(); +public: + + + _FORCE_INLINE_ T *ptr() { if (!_ptr) return NULL; _copy_on_write(); return (T*)_get_data(); } + _FORCE_INLINE_ const T *ptr() const { if (!_ptr) return NULL; return _get_data(); } + + + _FORCE_INLINE_ void clear() { resize(0); } + + _FORCE_INLINE_ int size() const { + + if (!_ptr) + return 0; + else + return *reinterpret_cast(((uint8_t*)(_ptr))+sizeof(SafeRefCount)); + } + _FORCE_INLINE_ bool empty() const { return _ptr == 0; } + Error resize(int p_size); + bool push_back(T p_elem); + + void remove(int p_index); + void erase(const T& p_val) { int idx = find(p_val); if (idx>=0) remove(idx); }; + void invert(); + + + template + int find(T_val& p_val) const; + + void set(int p_index,T p_elem); + T get(int p_index) const; + + inline T& operator[](int p_index) { + + if (p_index<0 || p_index>=size()) { + T& aux=*((T*)0); //nullreturn + ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux); + } + + _copy_on_write(); // wants to write, so copy on write. + + return _get_data()[p_index]; + } + + inline const T& operator[](int p_index) const { + + if (p_index<0 || p_index>=size()) { + const T& aux=*((T*)0); //nullreturn + ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux); + } + // no cow needed, since it's reading + return _get_data()[p_index]; + } + + Error insert(int p_pos,const T& p_val); + + template + void sort_custom() { + + int len = size(); + if (len==0) + return; + T *data = &operator[](0); + SortArray sorter; + sorter.sort(data,len); + } + + void sort() { + + sort_custom<_DefaultComparator >(); + } + + + + void operator=(const Vector& p_from); + Vector(const Vector& p_from); + + _FORCE_INLINE_ Vector(); + _FORCE_INLINE_ ~Vector(); + +}; + +template +void Vector::_unref(void *p_data) { + + if (!p_data) + return; + + SafeRefCount *src = reinterpret_cast(p_data); + + if (!src->unref()) + return; // still in use + // clean up + + int *count = (int*)(src+1); + T *data = (T*)(count+1); + + for (int i=0;i<*count;i++) { + // call destructors + data[i].~T(); + } + + // free mem + memfree(p_data); + +} + +template +void Vector::_copy_on_write() { + + if (!_ptr) + return; + + if (_get_refcount()->get() > 1 ) { + /* in use by more than me */ + SafeRefCount *src_new=(SafeRefCount *)memalloc(_get_alloc_size(*_get_size())); + src_new->init(); + int * _size = (int*)(src_new+1); + *_size=*_get_size(); + + T*_data=(T*)(_size+1); + + // initialize new elements + for (int i=0;i<*_size;i++) { + + memnew_placement(&_data[i], T( _get_data()[i] ) ); + } + + _unref(_ptr); + _ptr=src_new; + } + +} + +template template +int Vector::find(T_val& p_val) const { + + int ret = -1; + if (size() == 0) + return ret; + + for (int i=0; i +Error Vector::resize(int p_size) { + + ERR_FAIL_COND_V(p_size<0,ERR_INVALID_PARAMETER); + + if (p_size==size()) + return OK; + + if (p_size==0) { + // wants to clean up + _unref(_ptr); + _ptr=NULL; + return OK; + } + + // possibly changing size, copy on write + _copy_on_write(); + + if (p_size>size()) { + + if (size()==0) { + // alloc from scratch + _ptr = (T*)memalloc(_get_alloc_size(p_size)); + ERR_FAIL_COND_V( !_ptr ,ERR_OUT_OF_MEMORY); + _get_refcount()->init(); // init refcount + *_get_size()=0; // init size (currently, none) + + } else { + + void *_ptrnew = (T*)memrealloc(_ptr,_get_alloc_size(p_size)); + ERR_FAIL_COND_V( !_ptrnew ,ERR_OUT_OF_MEMORY); + _ptr=_ptrnew; + } + + // construct the newly created elements + T*elems = _get_data(); + + for (int i=*_get_size();i~T(); + } + + void *_ptrnew = (T*)memrealloc(_ptr,_get_alloc_size(p_size)); + ERR_FAIL_COND_V( !_ptrnew ,ERR_OUT_OF_MEMORY); + + _ptr=_ptrnew; + + *_get_size()=p_size; + + } + + return OK; +} + + +template +void Vector::invert() { + + for(int i=0;i +void Vector::set(int p_index,T p_elem) { + + operator[](p_index)=p_elem; +} + +template +T Vector::get(int p_index) const { + + return operator[](p_index); +} + +template +bool Vector::push_back(T p_elem) { + + Error err = resize(size()+1); + ERR_FAIL_COND_V( err, true ) + set(size()-1,p_elem); + + return false; +} + + +template +void Vector::remove(int p_index) { + + ERR_FAIL_INDEX(p_index, size()); + for (int i=p_index; i +void Vector::_copy_from(const Vector& p_from) { + + if (_ptr == p_from._ptr) + return; // self assign, do nothing. + + _unref(_ptr); + _ptr=NULL; + + if (!p_from._ptr) + return; //nothing to do + + if (p_from._get_refcount()->ref()) // could reference + _ptr=p_from._ptr; + +} + +template +void Vector::operator=(const Vector& p_from) { + + _copy_from(p_from); +} + + +template +Error Vector::insert(int p_pos,const T& p_val) { + + ERR_FAIL_INDEX_V(p_pos,size()+1,ERR_INVALID_PARAMETER); + resize(size()+1); + for (int i=(size()-1);i>p_pos;i--) + set( i, get(i-1) ); + set( p_pos, p_val ); + + return OK; +} + +template +Vector::Vector(const Vector& p_from) { + + _ptr=NULL; + _copy_from( p_from ); + +} + +template +Vector::Vector() { + + _ptr=NULL; +} + + +template +Vector::~Vector() { + + _unref(_ptr); + +} + + +#endif -- cgit v1.2.3