X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Fdlist.h;h=af633e2d877eed8bd989842f78fb8e2c54cae1dd;hb=5450f5e38d6dd94600c7c35fedf7f9ccea3e7adb;hp=49403d966ca8dcddea7e9b5f1ecc8944c9dfe1d0;hpb=067183227472a9aadc841d14589c7ae79cea4506;p=bacula%2Fbacula diff --git a/bacula/src/lib/dlist.h b/bacula/src/lib/dlist.h index 49403d966c..af633e2d87 100644 --- a/bacula/src/lib/dlist.h +++ b/bacula/src/lib/dlist.h @@ -1,48 +1,65 @@ /* - * 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 * */ +#define M_ABORT 1 + /* In case you want to specifically specify the offset to the link */ -#define OFFSET(item, link) ((char *)(link) - (char *)(item)) -/* +#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))=(void*)((list)->next(var))); ) - -#ifdef the_old_way + for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); ) +#else #define foreach_dlist(var, list) \ - for((var)=NULL; (((void *)(var))=(list)->next(var)); ) + for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); ) #endif struct dlink { @@ -50,87 +67,150 @@ struct dlink { void *prev; }; - -class dlist { +class dlist : public SMARTALLOC { void *head; void *tail; - uint16_t loffset; + int16_t loffset; uint32_t num_items; public: - dlist(void *item, void *link); + dlist(void *item, dlink *link); dlist(void); ~dlist() { destroy(); } - void init(void *item, void *link); + 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 *unique_binary_insert(void *item, int compare(void *item1, void *item2)); - void binary_insert(void *item, int compare(void *item1, void *item2)); + 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 dlist::dlist(void) + +/* + * 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) { - memset(this, 0, sizeof(dlist)); + init(item, link); } -inline bool dlist::empty() +/* Constructor with link at head of item */ +inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0) { - return head == NULL; } -inline int dlist::size() +inline void dlist::set_prev(void *item, void *prev) { - return num_items; + ((dlink *)(((char *)item)+loffset))->prev = prev; } - -inline void * dlist::operator new(size_t) +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);