X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Fdlist.h;h=af633e2d877eed8bd989842f78fb8e2c54cae1dd;hb=5450f5e38d6dd94600c7c35fedf7f9ccea3e7adb;hp=d50178a1868d0e6d153a84bd460df7f85f02b887;hpb=59ceb7bda26d458975db740607423080a4443b74;p=bacula%2Fbacula diff --git a/bacula/src/lib/dlist.h b/bacula/src/lib/dlist.h index d50178a186..af633e2d87 100644 --- a/bacula/src/lib/dlist.h +++ b/bacula/src/lib/dlist.h @@ -1,118 +1,216 @@ /* - * Version $Id$ - */ + Bacula® - The Network Backup Solution -/* - Copyright (C) 2000-2003 Kern Sibbald and John Walker + Copyright (C) 2004-2008 Free Software Foundation Europe e.V. - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of - the License, or (at your option) any later version. + The main author of Bacula is Kern Sibbald, with contributions from + many others, a complete list can be found in the file AUTHORS. + This program is Free Software; you can redistribute it and/or + modify it under the terms of version two of the GNU General Public + License as published by the Free Software Foundation and included + in the file LICENSE. - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of + This program 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. See the GNU General Public License for more details. - You should have received a copy of the GNU General Public - License along with this program; if not, write to the Free - Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, - MA 02111-1307, USA. + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. + Bacula® is a registered trademark of Kern Sibbald. + The licensor of Bacula is the Free Software Foundation Europe + (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich, + Switzerland, email:ftf@fsfeurope.org. +*/ +/* + * Written by Kern Sibbald MMIV + * + * Version $Id$ */ + /* ======================================================================== - * + * * Doubly linked list -- dlist + * + * See the end of the file for the dlistString class which + * facilitates storing strings in a dlist. + * + * Kern Sibbald, MMIV and MMVII * */ -/* In case you want to specifically specify the offset to the link */ -#define OFFSET(item, link) ((char *)(link) - (char *)(item)) +#define M_ABORT 1 +/* In case you want to specifically specify the offset to the link */ +#define OFFSET(item, link) (int)((char *)(link) - (char *)(item)) /* + * There is a lot of extra casting here to work around the fact + * that some compilers (Sun and Visual C++) do not accept + * (void *) as an lvalue on the left side of an equal. + * * Loop var through each member of list */ +#ifdef HAVE_TYPEOF #define foreach_dlist(var, list) \ - for((var)=NULL; ((void *)(var))=(list)->next((var)); ) + for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); ) +#else +#define foreach_dlist(var, list) \ + for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); ) +#endif struct dlink { void *next; void *prev; }; -class dlist { +class dlist : public SMARTALLOC { void *head; void *tail; - int loffset; - int num_items; + int16_t loffset; + uint32_t num_items; public: - dlist(void *item, void *link); - void init(void *item, void *link); + dlist(void *item, dlink *link); + dlist(void); + ~dlist() { destroy(); } + void init(void *item, dlink *link); + void init(); void prepend(void *item); void append(void *item); + void set_prev(void *item, void *prev); + void set_next(void *item, void *next); + void *get_prev(void *item); + void *get_next(void *item); + dlink *get_link(void *item); void insert_before(void *item, void *where); void insert_after(void *item, void *where); + void *binary_insert(void *item, int compare(void *item1, void *item2)); + void *binary_search(void *item, int compare(void *item1, void *item2)); + void binary_insert_multiple(void *item, int compare(void *item1, void *item2)); void remove(void *item); - bool empty(); - int size(); - void *next(void *item); + bool empty() const; + int size() const; + void *next(void *item); void *prev(void *item); void destroy(); - void *first(); - void *last(); - void * operator new(size_t); - void operator delete(void *); + void *first() const; + void *last() const; }; -/* + +/* * This allows us to do explicit initialization, * allowing us to mix C++ classes inside malloc'ed * C structures. Define before called in constructor. */ -inline void dlist::init(void *item, void *link) +inline void dlist::init(void *item, dlink *link) { head = tail = NULL; - loffset = (char *)link - (char *)item; + loffset = (int)((char *)link - (char *)item); + if (loffset < 0 || loffset > 5000) { + Emsg0(M_ABORT, 0, "Improper dlist initialization.\n"); + } num_items = 0; } -/* Constructor */ -inline dlist::dlist(void *item, void *link) +inline void dlist::init() { - this->init(item, link); + head = tail = NULL; + loffset = 0; + num_items = 0; } -inline bool dlist::empty() + +/* + * Constructor called with the address of a + * member of the list (not the list head), and + * the address of the link within that member. + * If the link is at the beginning of the list member, + * then there is no need to specify the link address + * since the offset is zero. + */ +inline dlist::dlist(void *item, dlink *link) { - return head == NULL; + init(item, link); } -inline int dlist::size() +/* Constructor with link at head of item */ +inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0) { - return num_items; } - -inline void * dlist::operator new(size_t) +inline void dlist::set_prev(void *item, void *prev) +{ + ((dlink *)(((char *)item)+loffset))->prev = prev; +} + +inline void dlist::set_next(void *item, void *next) { - return malloc(sizeof(dlist)); + ((dlink *)(((char *)item)+loffset))->next = next; } -inline void dlist::operator delete(void *item) +inline void *dlist::get_prev(void *item) { - ((dlist *)item)->destroy(); - free(item); + return ((dlink *)(((char *)item)+loffset))->prev; } - -inline void * dlist::first() +inline void *dlist::get_next(void *item) +{ + return ((dlink *)(((char *)item)+loffset))->next; +} + + +inline dlink *dlist::get_link(void *item) +{ + return (dlink *)(((char *)item)+loffset); +} + + + +inline bool dlist::empty() const +{ + return head == NULL; +} + +inline int dlist::size() const +{ + return num_items; +} + + + +inline void * dlist::first() const { return head; } -inline void * dlist::last() +inline void * dlist::last() const { return tail; } + +/* + * C string helper routines for dlist + * The string (char *) is kept in the node + * + * Kern Sibbald, February 2007 + * + */ +class dlistString +{ +public: + char *c_str() { return m_str; }; + +private: + dlink m_link; + char m_str[1]; + /* !!! Don't put anything after this as this space is used + * to hold the string in inline + */ +}; + +extern dlistString *new_dlistString(const char *str, int len); +extern dlistString *new_dlistString(const char *str);