Blame src/xarray.h

Packit 8f70b4
/*
Packit 8f70b4
 * lftp - file transfer program
Packit 8f70b4
 *
Packit 8f70b4
 * Copyright (c) 1996-2017 by Alexander V. Lukyanov (lav@yars.free.net)
Packit 8f70b4
 *
Packit 8f70b4
 * This program is free software; you can redistribute it and/or modify
Packit 8f70b4
 * it under the terms of the GNU General Public License as published by
Packit 8f70b4
 * the Free Software Foundation; either version 3 of the License, or
Packit 8f70b4
 * (at your option) any later version.
Packit 8f70b4
 *
Packit 8f70b4
 * This program is distributed in the hope that it will be useful,
Packit 8f70b4
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
Packit 8f70b4
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Packit 8f70b4
 * GNU General Public License for more details.
Packit 8f70b4
 *
Packit 8f70b4
 * You should have received a copy of the GNU General Public License
Packit 8f70b4
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
Packit 8f70b4
 */
Packit 8f70b4
Packit 8f70b4
#ifndef XARRAY_H
Packit 8f70b4
#define XARRAY_H 1
Packit 8f70b4
Packit 8f70b4
#include <sys/types.h>
Packit 8f70b4
#include "xmalloc.h"
Packit 8f70b4
#include "Ref.h"
Packit 8f70b4
Packit 8f70b4
class xarray0
Packit 8f70b4
{
Packit 8f70b4
protected:
Packit 8f70b4
   void *buf;
Packit 8f70b4
   int len;
Packit 8f70b4
private:
Packit 8f70b4
   size_t size;
Packit 8f70b4
   const unsigned short element_size;
Packit 8f70b4
   const short keep_extra;
Packit 8f70b4
Packit 8f70b4
   void init() { buf=0; size=len=0; }
Packit 8f70b4
Packit 8f70b4
   xarray0& operator=(const xarray0&); // make assignment fail
Packit 8f70b4
   xarray0(const xarray0&);	       // disable cloning
Packit 8f70b4
Packit 8f70b4
protected:
Packit 8f70b4
   void *get_ptr(int n) const { return static_cast<char*>(buf)+n*element_size; }
Packit 8f70b4
Packit 8f70b4
public:
Packit 8f70b4
   xarray0(size_t e,int k=0) : element_size(e),keep_extra(k) { init(); }
Packit 8f70b4
   ~xarray0() { xfree(buf); }
Packit 8f70b4
Packit 8f70b4
   // allocates s slots, with preferred granularity g, may shrink
Packit 8f70b4
   void get_space_do(size_t s,size_t g=32);
Packit 8f70b4
   void get_space(size_t s,size_t g=32) {
Packit 8f70b4
      if(size<s+keep_extra || size/2>=s+keep_extra)
Packit 8f70b4
	 get_space_do(s,g);
Packit 8f70b4
   }
Packit 8f70b4
   // only grows, not shrinks
Packit 8f70b4
   void grow_space(size_t s,size_t g=32) {
Packit 8f70b4
      if(size
Packit 8f70b4
	 get_space_do(s,g);
Packit 8f70b4
   }
Packit 8f70b4
Packit 8f70b4
   size_t get_element_size() const { return element_size; }
Packit 8f70b4
Packit 8f70b4
   int length() const { return len; }
Packit 8f70b4
   int count()  const { return len; }
Packit 8f70b4
Packit 8f70b4
   void _set_length(size_t n) { len=n; }
Packit 8f70b4
   void _nset(const void *s,int len);
Packit 8f70b4
   void _unset() { _nset(0,0); }
Packit 8f70b4
   void *_insert(int before);
Packit 8f70b4
   void *_append() { grow_space(len+1); return get_ptr(len++); }
Packit 8f70b4
   void _remove(int i,int j);
Packit 8f70b4
   void _remove(int i) { _remove(i,i+1); }
Packit 8f70b4
   void _chop() { len--; }
Packit 8f70b4
   void *_last() { return get_ptr(len-1); }
Packit 8f70b4
   void *_borrow();
Packit 8f70b4
   void move_here(xarray0& o);
Packit 8f70b4
Packit 8f70b4
   operator bool() const { return buf!=0; }
Packit 8f70b4
Packit 8f70b4
   typedef int (*qsort_cmp_t)(const void*,const void*);
Packit 8f70b4
   void qsort(qsort_cmp_t cmp) {
Packit 8f70b4
      if(len>0)
Packit 8f70b4
	 ::qsort(buf,len,element_size,cmp);
Packit 8f70b4
   }
Packit 8f70b4
   bool _bsearch(const void*,qsort_cmp_t,int *);
Packit 8f70b4
   void *_insert_ordered(const void*,qsort_cmp_t);
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
template<typename T>
Packit 8f70b4
class xarray : public xarray0
Packit 8f70b4
{
Packit 8f70b4
   xarray& operator=(const xarray&); // make assignment fail
Packit 8f70b4
   xarray(const xarray&);	       // disable cloning
Packit 8f70b4
public:
Packit 8f70b4
   xarray() : xarray0(sizeof(T)) {}
Packit 8f70b4
   T *get_non_const() { return static_cast<T*>(buf); }
Packit 8f70b4
   const T *get() const { return static_cast<const T*>(buf); }
Packit 8f70b4
   T& operator[](int i) { return get_non_const()[i]; }
Packit 8f70b4
   const T& operator[](int i) const { return get()[i]; }
Packit 8f70b4
   size_t get_element_size() const { return sizeof(T); }
Packit 8f70b4
/*   operator const T*() const { return get(); }*/
Packit 8f70b4
   void nset(const T *s,int len) { _nset(s,len); }
Packit 8f70b4
   void set(const xarray<T> &a) { nset(a.get(),a.count()); }
Packit 8f70b4
   void set_length(size_t n) { _set_length(n); }
Packit 8f70b4
   void unset() { _unset(); }
Packit 8f70b4
   void truncate() { set_length(0); }
Packit 8f70b4
   void insert(const T& n,int before) { *static_cast<T*>(_insert(before))=n; }
Packit 8f70b4
   void append(const T& n) { *static_cast<T*>(_append())=n; }
Packit 8f70b4
   void remove(int i) { _remove(i); }
Packit 8f70b4
   void remove(int i,int j) { _remove(i,j); }
Packit 8f70b4
   void chop() { _chop(); }
Packit 8f70b4
   T& last() { return (*this)[len-1]; }
Packit 8f70b4
   T *borrow() { return static_cast<T*>(_borrow()); }
Packit 8f70b4
   typedef int (*cmp_t)(const T*,const T*);
Packit 8f70b4
   void qsort(cmp_t cmp) {
Packit 8f70b4
      xarray0::qsort((qsort_cmp_t)cmp);
Packit 8f70b4
   }
Packit 8f70b4
   void insert_ordered(const T& n,cmp_t cmp) {
Packit 8f70b4
      *static_cast<T*>(_insert_ordered(&n,(qsort_cmp_t)cmp))=n;
Packit 8f70b4
   }
Packit 8f70b4
   int search(const T &x) const {
Packit 8f70b4
      for(int i=0; i
Packit 8f70b4
      {
Packit 8f70b4
	 if(get()[i]==x)
Packit 8f70b4
	    return i;
Packit 8f70b4
      }
Packit 8f70b4
      return -1;
Packit 8f70b4
   }
Packit 8f70b4
   bool bsearch(const T &x,cmp_t cmp,int *pos) {
Packit 8f70b4
      return _bsearch(&x,(qsort_cmp_t)cmp,pos);
Packit 8f70b4
   }
Packit 8f70b4
   int bsearch(const T &x,cmp_t cmp) {
Packit 8f70b4
      int pos;
Packit 8f70b4
      return bsearch(x,cmp,&pos) ? pos : -1;
Packit 8f70b4
   }
Packit 8f70b4
   void allocate(int c,const T& fill) {
Packit 8f70b4
      while(c-->0) {
Packit 8f70b4
	 append(fill);
Packit 8f70b4
      }
Packit 8f70b4
   }
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
template<typename T,typename RefT>
Packit 8f70b4
class _RefArray : public xarray0
Packit 8f70b4
{
Packit 8f70b4
   void dispose(int i) { get_non_const()[i].unset(); }
Packit 8f70b4
   void dispose(int i,int j) { while(i
Packit 8f70b4
   void clear(int i) { get_non_const()[i]._clear(); }
Packit 8f70b4
   void clear(int i,int j) { while(i
Packit 8f70b4
public:
Packit 8f70b4
   _RefArray() : xarray0(sizeof(RefT)) {}
Packit 8f70b4
   ~_RefArray() { dispose(0,len); }
Packit 8f70b4
   RefT *get_non_const() { return static_cast<RefT*>(buf); }
Packit 8f70b4
   const RefT *get() const { return static_cast<const RefT*>(buf); }
Packit 8f70b4
   RefT& operator[](int i) { return get_non_const()[i]; }
Packit 8f70b4
   const RefT& operator[](int i) const { return get()[i]; }
Packit 8f70b4
   size_t get_element_size() const { return sizeof(RefT); }
Packit 8f70b4
   void set_length(size_t n) { dispose(n,len); _set_length(n); }
Packit 8f70b4
   void unset() { dispose(0,len); _unset(); }
Packit 8f70b4
   void truncate() { set_length(0); }
Packit 8f70b4
   void insert(T *n,int before) { static_cast<RefT*>(_insert(before))->_set(n); }
Packit 8f70b4
   void append(T *n) { static_cast<RefT*>(_append())->_set(n); }
Packit 8f70b4
   void remove(int i) { dispose(i); _remove(i); }
Packit 8f70b4
   void remove(int i,int j) { dispose(i,j); _remove(i,j); }
Packit 8f70b4
   void chop() { dispose(len-1); _chop(); }
Packit 8f70b4
   RefT& last() { return (*this)[len-1]; }
Packit 8f70b4
   RefT *borrow() { return static_cast<RefT*>(_borrow()); }
Packit 8f70b4
   void allocate(int c) { while(c-->0) append((T*)0); }
Packit 8f70b4
   typedef int (*cmp_t)(const RefT*,const RefT*);
Packit 8f70b4
   void qsort(cmp_t cmp) {
Packit 8f70b4
      xarray0::qsort((qsort_cmp_t)cmp);
Packit 8f70b4
   }
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
template<typename T>
Packit 8f70b4
class RefArray : public _RefArray< T,Ref<T> > {
Packit 8f70b4
   RefArray& operator=(const RefArray&); // make assignment fail
Packit 8f70b4
   RefArray(const RefArray&);	       // disable cloning
Packit 8f70b4
public:
Packit 8f70b4
   RefArray() : _RefArray< T,Ref<T> >() {}
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
template<typename T>
Packit 8f70b4
class xarray_s : public _RefArray<const char,T> {
Packit 8f70b4
   xarray_s& operator=(const xarray_s&); // make assignment fail
Packit 8f70b4
   xarray_s(const xarray_s&);	       // disable cloning
Packit 8f70b4
public:
Packit 8f70b4
   xarray_s() : _RefArray<const char,T>() {}
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
// array of new'ed pointers
Packit 8f70b4
template<typename T>
Packit 8f70b4
class xarray_p : public xarray0
Packit 8f70b4
{
Packit 8f70b4
   xarray_p& operator=(const xarray_p&); // make assignment fail
Packit 8f70b4
   xarray_p(const xarray_p&);	       // disable cloning
Packit 8f70b4
Packit 8f70b4
   virtual void dispose(T *p) { delete p; }
Packit 8f70b4
   void dispose(int i) { dispose(get_non_const()[i]); }
Packit 8f70b4
   void dispose(int i,int j) { while(i
Packit 8f70b4
   void clear(int i) { get_non_const()[i]=0; }
Packit 8f70b4
   void clear(int i,int j) { while(i
Packit 8f70b4
   void z() { clear(len); }
Packit 8f70b4
public:
Packit 8f70b4
   xarray_p() : xarray0(sizeof(T*),1) {}
Packit 8f70b4
   virtual ~xarray_p() { dispose(0,len); }
Packit 8f70b4
   T **get_non_const() { return static_cast<T**>(buf); }
Packit 8f70b4
   T *const* get() const { return static_cast<T*const*>(buf); }
Packit 8f70b4
   T *&operator[](int i) { return get_non_const()[i]; }
Packit 8f70b4
   T *operator[](int i) const { return get()[i]; }
Packit 8f70b4
   size_t get_element_size() const { return sizeof(T*); }
Packit 8f70b4
   void nset(T *const*s,int s_len) { dispose(0,len); _nset(s,s_len); if(buf) z(); }
Packit 8f70b4
   void set(const xarray_p<T> &a) { nset(a.get(),a.count()); }
Packit 8f70b4
   void set_length(size_t n) { dispose(n,len); _set_length(n); if(buf) z(); }
Packit 8f70b4
   void unset() { dispose(0,len); _unset(); }
Packit 8f70b4
   void truncate() { set_length(0); }
Packit 8f70b4
   void insert(T *n,int before) { *static_cast<T**>(_insert(before))=n; z(); }
Packit 8f70b4
   void append(T *n) { *static_cast<T**>(_append())=n; z(); }
Packit 8f70b4
   void remove(int i) { dispose(i); _remove(i); z(); }
Packit 8f70b4
   void remove(int i,int j) { dispose(i,j); _remove(i,j); z(); }
Packit 8f70b4
   void chop() { dispose(len-1); _chop(); }
Packit 8f70b4
   T *last() { return (*this)[len-1]; }
Packit 8f70b4
   T **borrow() { return static_cast<T**>(_borrow()); }
Packit 8f70b4
   typedef int (*cmp_t)(const T**,const T**);
Packit 8f70b4
   void qsort(cmp_t cmp) {
Packit 8f70b4
      xarray0::qsort((qsort_cmp_t)cmp);
Packit 8f70b4
   }
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
// array of malloc'ed pointers
Packit 8f70b4
template<typename T>
Packit 8f70b4
class xarray_m : public xarray_p<T>
Packit 8f70b4
{
Packit 8f70b4
   void dispose(T *p) { xfree(p); }
Packit 8f70b4
public:
Packit 8f70b4
   ~xarray_m() { xarray_p<T>::truncate(); }
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
Packit 8f70b4
template<typename T,class A,typename P> class _xqueue
Packit 8f70b4
{
Packit 8f70b4
protected:
Packit 8f70b4
   A q;
Packit 8f70b4
   int ptr;
Packit 8f70b4
public:
Packit 8f70b4
   _xqueue() : ptr(0) {}
Packit 8f70b4
   int count() const { return q.count()-ptr; }
Packit 8f70b4
   void empty() { q.truncate(); ptr=0; }
Packit 8f70b4
   void push(P n) {
Packit 8f70b4
      if(ptr>count()) {
Packit 8f70b4
	 q.remove(0,ptr);
Packit 8f70b4
	 ptr=0;
Packit 8f70b4
      }
Packit 8f70b4
      q.append(n);
Packit 8f70b4
   }
Packit 8f70b4
   void remove(int i) {
Packit 8f70b4
      if(i==0)
Packit 8f70b4
	 ptr++;
Packit 8f70b4
      else
Packit 8f70b4
	 q.remove(ptr+i);
Packit 8f70b4
   }
Packit 8f70b4
   // returned pointer valid till the next push
Packit 8f70b4
   T& next() { return q[ptr++]; }
Packit 8f70b4
   T& operator[](int i) { return q[ptr+i]; }
Packit 8f70b4
   const T& operator[](int i) const { return q[ptr+i]; }
Packit 8f70b4
   void move_here(_xqueue& o) { q.move_here(o.q); ptr=o.ptr; o.ptr=0; }
Packit 8f70b4
};
Packit 8f70b4
Packit 8f70b4
template<typename T,class A> class xqueue : public _xqueue<T,A,const T&> {};
Packit 8f70b4
template<typename T> class xqueue_p : public _xqueue<T*,xarray_p<T>,T*> {};
Packit 8f70b4
template<typename T> class xqueue_m : public _xqueue<T*,xarray_m<T>,T*> {};
Packit 8f70b4
template<typename T> class RefQueue : public _xqueue<Ref<T>,RefArray<T>,T*> {};
Packit 8f70b4
Packit 8f70b4
#endif // XARRAY_H