From 3a4838bed13b767132cbdf06364b2658da6cc356 Mon Sep 17 00:00:00 2001 From: chatty Date: Tue, 15 Dec 1992 10:55:33 +0000 Subject: Initial revision --- utils/Allocator.cc | 147 ++++++++++ utils/Allocator.h | 46 ++++ utils/Array.cc | 228 ++++++++++++++++ utils/Array.h | 59 ++++ utils/BitField.cc | 52 ++++ utils/BitField.h | 45 ++++ utils/Chain.cc | 426 +++++++++++++++++++++++++++++ utils/Chain.h | 111 ++++++++ utils/DList.cc | 573 +++++++++++++++++++++++++++++++++++++++ utils/DList.h | 159 +++++++++++ utils/DirPath.cc | 214 +++++++++++++++ utils/DirPath.h | 44 +++ utils/HashTable.cc | 635 +++++++++++++++++++++++++++++++++++++++++++ utils/HashTable.h | 212 +++++++++++++++ utils/IdTable.cc | 319 ++++++++++++++++++++++ utils/IdTable.h | 79 ++++++ utils/Initializer.h | 29 ++ utils/List.cc | 724 ++++++++++++++++++++++++++++++++++++++++++++++++++ utils/List.h | 192 +++++++++++++ utils/RegExp.cc | 163 ++++++++++++ utils/RegExp.h | 81 ++++++ utils/Signal.cc | 312 ++++++++++++++++++++++ utils/Signal.h | 79 ++++++ utils/SmartPointer.cc | 245 +++++++++++++++++ utils/SmartPointer.h | 117 ++++++++ utils/String.cc | 240 +++++++++++++++++ utils/String.h | 61 +++++ utils/Time.cc | 90 +++++++ utils/Time.h | 41 +++ utils/Timer.cc | 402 ++++++++++++++++++++++++++++ utils/Timer.h | 83 ++++++ 31 files changed, 6208 insertions(+) create mode 100644 utils/Allocator.cc create mode 100644 utils/Allocator.h create mode 100644 utils/Array.cc create mode 100644 utils/Array.h create mode 100644 utils/BitField.cc create mode 100644 utils/BitField.h create mode 100644 utils/Chain.cc create mode 100644 utils/Chain.h create mode 100644 utils/DList.cc create mode 100644 utils/DList.h create mode 100644 utils/DirPath.cc create mode 100644 utils/DirPath.h create mode 100644 utils/HashTable.cc create mode 100644 utils/HashTable.h create mode 100644 utils/IdTable.cc create mode 100644 utils/IdTable.h create mode 100644 utils/Initializer.h create mode 100644 utils/List.cc create mode 100644 utils/List.h create mode 100644 utils/RegExp.cc create mode 100644 utils/RegExp.h create mode 100644 utils/Signal.cc create mode 100644 utils/Signal.h create mode 100644 utils/SmartPointer.cc create mode 100644 utils/SmartPointer.h create mode 100644 utils/String.cc create mode 100644 utils/String.h create mode 100644 utils/Time.cc create mode 100644 utils/Time.h create mode 100644 utils/Timer.cc create mode 100644 utils/Timer.h (limited to 'utils') diff --git a/utils/Allocator.cc b/utils/Allocator.cc new file mode 100644 index 0000000..d89ebf6 --- /dev/null +++ b/utils/Allocator.cc @@ -0,0 +1,147 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Memory allocation (original C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + +#include "Allocator.h" +#include +#include +#include "Signal.h" + +/*?class CcuAllocator +The memory manager is implemented through a C++ class called \typ{CcuAllocator}. +Each instance of this class is a memory allocator, which delivers memory blocks of +a given size. + +Allocators work as follow: each allocator obtains pages of memory through \fun{malloc}. +It then splits that memory in blocks in order to deliver them. When a block is freed, it +is stored in a list of free blocks so as to be reused. In the current implementation, +memory pages are never released. +?*/ + + +#define CHUNKSIZE 1024 + +/* + * Supposing that memory blocks must always be aligned on + * word boundaries, we allocate chunks as arrays of words, + * and express all sizes in words. + * + */ +#ifndef WORD_TYPE +#define WORD_TYPE int +#endif + +typedef WORD_TYPE Word; + +inline unsigned int +SizeInWords (unsigned int size) +{ + return (size + sizeof (Word) -1) / sizeof (Word); +} + +/*? +This function is called when there is no more memory. It issues an error message to +the standard error output, then calls \fun{exit}. +?*/ +void +CcuAllocator :: MemoryOverflow () +{ + static char msg [] = "Memory overflow. Bye ...\n"; + + write (2, msg, sizeof (msg)); + exit (99); +} + +/*? +Constructor for \typ{CcuAllocator}s. It initializes an allocator for structures of size \var{size}. +For implementation reasons, allocated blocks will be at least the size of a pointer. +?*/ +CcuAllocator :: CcuAllocator (unsigned int size) +: BlockSize (SizeInWords (size)), + ChunkSize (SizeInWords (CHUNKSIZE)), + FreeList (0), + AllocEnd (0), + AllocNext (0) +{ + /* if blocks are too small to hold a pointer, enlarge them */ + unsigned int ptr_size = SizeInWords (sizeof (Word*)); + if (BlockSize < ptr_size) + BlockSize = ptr_size; + + /* if chunks are too small to hold two blocks, enlarge them */ + if (ChunkSize < 2*BlockSize) + ChunkSize = 2*BlockSize; +} + +/*?nodoc?*/ +CcuAllocator :: ~CcuAllocator () +{ +} + +/*? +Allocate a block of memory with an \typ{CcuAllocator}. +This function returns the address of the allocated block, or 0 if the allocation failed +for some reason. +The allocated block is aligned on a word boundary, and it is {\em not} filled with zeroes. +?*/ +void* +CcuAllocator :: Alloc () +{ +#ifdef MEMORY_DEBUG + CcuSignalBlocker b (AllSigs); + void* w = new Word [BlockSize]; + return w; +#else + register Word* block; + + /* give memory from the free-list */ + if (FreeList) { + block = (Word*) FreeList; + FreeList = ((Word**) FreeList)[0]; + /* or from fresh memory */ + } else { + block = (Word*) AllocNext; + AllocNext = ((Word*) AllocNext) + BlockSize; + if (AllocNext > AllocEnd) { + /* here we have to get new chunk */ + CcuSignalBlocker b (AllSigs); + block = new Word [ChunkSize]; + if (block == 0) + MemoryOverflow (); + /* we suppose we can put at least 2 objects in a chunk */ + AllocNext = block + BlockSize; + AllocEnd = block + ChunkSize; + } + } + return block; +#endif +} + + +/*? +Free the memory allocated at \var{p} by this \typ{CcuAllocator}. +No check is performed, and you should take care that \var{p} +was allocated by this allocator. +?*/ +void +CcuAllocator :: Free (void* p) +{ +#ifdef MEMORY_DEBUG + CcuSignalBlocker b (AllSigs); + delete [] ((Word*) p); +#else + /* Prepend the block to the list of free blocks */ + ((Word**) p)[0] = (Word*) FreeList; + FreeList = p; +#endif +} diff --git a/utils/Allocator.h b/utils/Allocator.h new file mode 100644 index 0000000..33939f7 --- /dev/null +++ b/utils/Allocator.h @@ -0,0 +1,46 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Memory allocation (original C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + + +#ifndef Allocator_H_ +#define Allocator_H_ + +#include "cplus_bugs.h" + +class CcuAllocator { +private: +static void MemoryOverflow (); + + unsigned int BlockSize; + unsigned int ChunkSize; + void* FreeList; /* list of free blocks of memory */ + void* AllocEnd; /* end of the last chunk */ + void* AllocNext; /* room left in the last chunk */ + +public: + CcuAllocator (unsigned int); + ~CcuAllocator (); + void* Alloc (); + void Free (void*); +}; + +#ifndef CPLUS_BUG19 +template class CcuAllocatorOf : public CcuAllocator { +public: +inline CcuAllocatorOf () : CcuAllocator (sizeof (OBJECT)) {} +inline OBJECT* Alloc () { return (OBJECT*) CcuAllocator::Alloc (); } +}; +#endif + +#endif /* Allocator_H_ */ diff --git a/utils/Array.cc b/utils/Array.cc new file mode 100644 index 0000000..e51e7ae --- /dev/null +++ b/utils/Array.cc @@ -0,0 +1,228 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1990, 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic arrays (orginal C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + +#include "Array.h" +#include +#include + +/*?class CcuArray +\typ{CcuArray}s are dynamic arrays whose lower bound is 0. For a +\typ{CcuArray} with size \var{size}, the valid indices are \var{0, \ldots, size -- 1.} +Their elements are of type \typ{CcuArrayItem*}. Methods are provided for +initialization, data storage and retrieval, and a few other utilities. +?*/ + +CcuArrayItem* CcuArray::InvalidCell = 0; + +/*? +Initialize a \typ{CcuArray} with size \var{size}. +Entries are initialized to \var{value}. +?*/ +CcuArray :: CcuArray (int size, CcuArrayItem* value) +{ + if (size > 0) { + Data = new CcuArrayItem* [size]; + register CcuArrayItem** p = Data; + for (register int i = 0; i < size; ++i, ++p) + *p = value; + } else { + Data = 0; + size = 0; + } + + Length = size; + +} + +/*?nodoc?*/ +CcuArray :: CcuArray (const CcuArray& a) +: Length (a.Length) +{ + if (Length == 0) { + Data = 0; + } else { + Data = new CcuArrayItem* [Length]; + register CcuArrayItem** p; + register CcuArrayItem** q; + register int i; + for (p = Data, q = a.Data, i = Length ; i--; ++p, ++q) + *p = *q; + } +} + +/*?nodoc?*/ +CcuArray :: ~CcuArray () +{ + /* Free the data */ + Clean (); +} + +/* + * Empty the array. + */ +/*?hidden?*/ +void +CcuArray :: Clean () +{ + if (Data) +#ifndef CPLUS_BUG4 + delete [] Data; +#else + delete [Length] Data; +#endif + + Data = 0; + Length = 0; +} + + +/*? +Set all entries to \var{value}. +?*/ +void +CcuArray :: Reset (CcuArrayItem* value) +{ + register CcuArrayItem** p; + register int i; + for (p = Data, i = Length ; i--; ++p) + *p = value; +} + +/*? +Copy the contents of the array \var{from} into this array. +The old contents, if any, are freed, and new memory is allocated for the copy. +?*/ +CcuArray& +CcuArray :: operator = (const CcuArray& from) +{ + if (this != &from) { + Clean (); + Length = from.Length; + if (Length > 0 && from.Data) { + Data = new CcuArrayItem* [Length]; + memcpy (Data, from.Data, Length * sizeof (CcuArrayItem*)); + } else + Data = 0; + } + return *this; +} + +/*? +Change the size of the array to \var{size}. The new entries, if any, +are set to \var{value}. +This function reallocates the contents of the array. +?*/ +void +CcuArray :: Resize (int size, CcuArrayItem* value) +{ + if (size <= 0) { + Clean (); + return; + } + + CcuArrayItem** NewData = new CcuArrayItem* [size]; + + /* if the new sequence is longer, copy and fill end, else just copy */ + if (size > Length) { + if (Length) + memcpy (NewData, Data, Length * sizeof (CcuArrayItem*)); + + register CcuArrayItem** pfil = NewData + Length; + for (register int i = size - Length; i--; *pfil++ = value) + ; + } else + memcpy (NewData, Data, size * sizeof (CcuArrayItem*)); + + + /* free old data and set new array */ + Clean (); + Data = NewData; + Length = size; +} + + +/*? +Return the address of the \var{i}th element. +?*/ +CcuArrayItem** +CcuArray :: operator + (register int i) const +{ + if (Check (i)) + return Data+i; + else { + fprintf (stderr, "Index %d out of array bounds: size was %d\n", i, Length); + return &InvalidCell; + } +} + + +/*? +Get a reference to the \var{i}-th entry, so that this entry can be read or written. +If \var{i} is outside the bounds, +the operator returns a reference to a static variable which initially contains 0. +?*/ +CcuArrayItem*& +CcuArray :: operator [] (register int i) const +{ + if (Check (i)) + return Data [i]; + else { + fprintf (stderr, "Index %d out of array bounds: size was %d\n", i, Length); + return InvalidCell; + } +} + +#ifdef DOC +/*?class CcuArrayOf +The generic class \typ{CcuArrayOf} is a derived class of \typ{CcuArray} that provides +arrays of pointers to class objects. When parameterized by the class \typ{ITEM}, +the following functions are redefined: +?*/ + +/*?nextdoc?*/ +CcuArrayOf :: CcuArrayOf (int size, ITEM* value = 0) +{ +} + +/*?nextdoc?*/ +void +CcuArrayOf :: Reset (ITEM* value = 0) +{ +} + +/*?nextdoc?*/ +void +CcuArrayOf :: Resize (int size, ITEM* value = 0) +{ +} + +/*?nextdoc?*/ +ITEM*& +CcuArrayOf :: operator [] (int i) const +{ +} + +/*? +These functions are equivalent to their homonyms in the class \typ{CcuArray}, +except that they are customized in order to manipulate pointers to \typ{ITEM} +instead of \typ{void*}. +?*/ +ITEM** +CcuArrayOf :: operator + (int i) const +{ +} + +#endif /* DOC */ + diff --git a/utils/Array.h b/utils/Array.h new file mode 100644 index 0000000..f33656f --- /dev/null +++ b/utils/Array.h @@ -0,0 +1,59 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1990, 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic arrays (orginal C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + + +#ifndef Array_H_ +#define Array_H_ + +#include "cplus_bugs.h" + +typedef void CcuArrayItem; + +class CcuArray { + +protected: +static CcuArrayItem* InvalidCell; + int Length; + CcuArrayItem** Data; + void Clean (); + +public: + CcuArray (int size, CcuArrayItem* = 0); + CcuArray (const CcuArray&); + ~CcuArray (); + void Reset (CcuArrayItem* = 0); + CcuArrayItem*& operator [] (int i) const; + CcuArrayItem** operator + (int) const; + CcuArray& operator = (const CcuArray&); +inline int Check (int i) const { return (i >= 0 && i < Length); } +inline int GetSize () const { return Length; } + void Resize (int, CcuArrayItem* = 0); +}; + +#ifndef CPLUS_BUG19 +template class CcuArrayOf : public CcuArray { +public: +inline CcuArrayOf (int size, ITEM* value = 0) : CcuArray (size, value) {} +inline CcuArrayOf (const CcuArrayOf& a) : CcuArray (a) {} +inline ~CcuArrayOf () {} +inline void Reset (ITEM* value = 0) { CcuArray::Reset (value); } +inline void Resize (int size, ITEM* value = 0) { CcuArray::Resize (size, value); } +inline ITEM*& operator [] (int i) const { return (ITEM*&) ((* (CcuArray*) this)[i]); } +inline ITEM** operator + (int i) const { return (ITEM**) ((*(CcuArray*) this) + i); } +}; +#endif + +#endif /* Array_H_ */ + diff --git a/utils/BitField.cc b/utils/BitField.cc new file mode 100644 index 0000000..ad9532a --- /dev/null +++ b/utils/BitField.cc @@ -0,0 +1,52 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * bit fields + * + * $Id$ + * $CurLog$ + */ + + +#include "BitField.h" +#include +#include + +CcuBitField :: CcuBitField () +{ + memset ((char*) Chunks, 0, 8 * sizeof (long)); +} + +CcuBitRef +CcuBitField :: operator [] (int i) +{ + if (i < 0 || i >= 8 * sizeof (long)) { + fprintf (stderr, "Bad access to bitfield: index %d\n", i); + i = 0; + } + short q = i / sizeof (long); + short r = i - q * sizeof (long); + return CcuBitRef (*this, q, r); +} + +CcuBitRef :: operator bool () const +{ + return bool (Field.Chunks [Chunk] & (1L << Offset)); +} + +bool +CcuBitRef :: operator = (bool b) const +{ + long* l = Field.Chunks + Chunk; + long m = (1L << Offset); + if (b) + (*l) |= m; + else + (*l) &= ~m; + return b; +} diff --git a/utils/BitField.h b/utils/BitField.h new file mode 100644 index 0000000..cc7633c --- /dev/null +++ b/utils/BitField.h @@ -0,0 +1,45 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * bit fields + * + * $Id$ + * $CurLog$ + */ + +#ifndef BitField_H_ +#define BitField_H_ + +#include "bool.h" + +class CcuBitRef { +friend class CcuBitField; + +protected: + short Chunk; + short Offset; + CcuBitField& Field; +inline CcuBitRef (CcuBitField& f, short c, short o) : Field (f), Chunk (c), Offset (o) {} + +public: + operator bool () const; + bool operator = (bool) const; +}; + +class CcuBitField { +friend class CcuBitRef; + +protected: + long Chunks [8]; +public: + CcuBitField (); + CcuBitRef operator [] (int); +}; + + +#endif /* BitField_H_ */ diff --git a/utils/Chain.cc b/utils/Chain.cc new file mode 100644 index 0000000..e9cd14f --- /dev/null +++ b/utils/Chain.cc @@ -0,0 +1,426 @@ +/* + * CENA C++ Utilities + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * generic chains of objects - to be updated + * + * $Id$ + * $CurLog$ + */ + +#include "Chain.h" +#include +#include + +CcuChain :: ~CcuChain () +{ +} + +CcuChainItem* +CcuChain :: GetPrevious (CcuChainItem* i) +{ + register CcuChainItem* c = LastLink; + register CcuChainItem* n; + while ((n = GetNext (c)) != i) + c = n; + return c; +} + +/*? +Empty a list. +?*/ +void +CcuChain :: Clear () +{ + CcuChainItem* del = LastLink; + while (del) { + CcuChainItem* next = GetNext (del); + if (next == LastLink) + next = 0; + Delete (del); + del = next; + } + LastLink = 0; +} + + +/*?nextdoc?*/ +CcuChainItem* +CcuChain :: First () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return GetNext (LastLink); +} + +/*? +Return the first/last element in the list, or 0 if the list was empty. +The case of a null element can be distinguished from the case +when the list is empty with the function \fun{GetStatus}. +?*/ +CcuChainItem* +CcuChain :: Last () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return LastLink; +} + +/*? +Get the \var{n}-th element of a list. If \var{n} is greater than the length of the list +this function returns 0 and sets the status to \var{TooFar}. If \var{n} is negative, +this function returns 0 but sets the status to \var{NoError}. +?*/ +CcuChainItem* +CcuChain :: Nth (int n) +{ + StatusFlag = NoError; + if (n <= 0) + return 0; + CcuChainIter li (*this); + while (n > 0 && ++li) + --n; + if (n != 0) + StatusFlag = TooFar; + return *li; +} + +/*? +Compute the number of elements in a list. +?*/ +int +CcuChain :: Length () const +{ + int result = 0; + CcuChainIter li (*this); + while (++li) + ++result; + return result; +} + +/*? +Check whether an item is present in a list. +?*/ +int +CcuChain :: Find (CcuChainItem* e) const +{ + CcuChainIter li (*this); + while (++li) + if (*li == e) + return 1; + return 0; +} + +/*?nextdoc?*/ +void +CcuChain :: Prepend (CcuChainItem* e) +{ + if (LastLink) { + /* remember that LastLink->Next is the first */ + SetNext (e, GetNext (LastLink)); + SetNext (LastLink, e); + } else { + LastLink = e; + SetNext (e, e); + } +} + +/*? +Insert an element at the beginning/end of a list. +?*/ +void +CcuChain :: Append (CcuChainItem* e) +{ + if (LastLink) { + SetNext (e, GetNext (LastLink)); + SetNext (LastLink, e); + LastLink = e; + } else { + LastLink = e; + SetNext (e, e); + } +} + +/*? +Remove the first element of a list and return it. +?*/ +CcuChainItem* +CcuChain :: RemoveFirst () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + /* Get the first element */ + CcuChainItem* first = GetNext (LastLink); + + /* Remove it from the chain */ + if (LastLink == first) + LastLink = 0; + else + SetNext (LastLink, GetNext (first)); + return first; +} + + +/*? +Remove the last element of a list and return it. This function has to locate the last +element, and hence has a linear cost. +?*/ +CcuChainItem* +CcuChain :: RemoveLast () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + /* Find the element that will be the new LastLink */ + register CcuChainItem* newlast = GetPrevious (LastLink); + + /* Save the element to be deleted and its data */ + CcuChainItem* last = LastLink; + /* Remove it from the chain */ + if (newlast == LastLink) + LastLink = 0; + else { + SetNext (newlast, GetNext (LastLink)); + LastLink = newlast; + } + return last; +} + +/*? +Insert an element before the link \var{l}. This function has a linear cost. +?*/ +void +CcuChain :: InsertBefore (CcuChainItem* l, CcuChainItem* e) +{ + CcuChainItem* prev = GetPrevious (l); + SetNext (prev, e); + SetNext (e, l); +} + + +/*? +Insert an element after the link \var{l}. +?*/ +void +CcuChain :: InsertAfter (CcuChainItem* l, CcuChainItem* e) +{ + SetNext (e, GetNext (l)); + SetNext (l, e); + if (LastLink == l) + LastLink = e; +} + +/*? +Remove the link which is after \var{l} and return its entry. If \var{l} is the last link of +the list, the first one is removed. +?*/ +CcuChainItem* +CcuChain :: RemoveAfter (CcuChainItem* l) +{ + CcuChainItem* del = GetNext (l); + if (del == l) { + LastLink = 0; + } else { + SetNext (l, GetNext (l)); + if (LastLink == del) + LastLink = l; + } + return del; +} + +/*? +Remove an element from a list. This function iterates through the list until it deletes +\var{num} appearances of \var{entry}. The actual number of removals is returned. +If \var{num} is \var{All} or is negative, all appearances of \var{entry} are deleted. +?*/ +int +CcuChain :: Remove (CcuChainItem* entry) +{ + int removed = 0; + CcuChainIter li (*this); + CcuChainIter lj (*this); + while (++li) { + if (*li == entry) { + RemoveAfter (lj); + return 1; + } else + ++lj; + } + return 0; +} + +/*? +Remove elements from a list. This function iterates through the list until it deletes +\var{num} elements for which the function \var{p} returns a non-null value. +The actual number of removals is returned. +If \var{num} is \var{All} or is negative, all matching elements are deleted. +?*/ +int +CcuChain :: Remove (int (*p) (CcuChainItem*)) +{ + int removed = 0; + CcuChainIter li (*this); + CcuChainIter lj (*this); + while (++li) { + if ((*p) (*li)) { + RemoveAfter (lj); + return 1; + } else + ++lj; + } + return 0; +} + + +/*?nextdoc?*/ +void +CcuChain :: InsertAfter (const CcuChainIter& li, CcuChainItem* e) +{ + if (li.TheChain != this) { + StatusFlag = BadIterator; + return; + } + StatusFlag = NoError; + if (!li.CurLink) { + if (li.StatusFlag == CcuChainIter::StartOfChain) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuChain::InsertAfter\n"); + abort (); + } + } else if (li.StatusFlag == CcuChainIter::EndOfChain) { + Append (e); + } else { + InsertAfter (li.CurLink, e); + } +} + +/*? +Insert an element before (resp. after) the current position of the iterator \var{li}. +These functions are both equivalent to \fun{CcuChain::Prepend} if the iterator is at the +beginning of the list (ie. before the first element) +\fun{InsertAfter} is performed in a constant time, while \fun{InsertBefore} +has a linear cost. +?*/ +void +CcuChain :: InsertBefore (const CcuChainIter& li, CcuChainItem* e) +{ + if (li.TheChain != this) { + StatusFlag = BadIterator; + return; + } + StatusFlag = NoError; + if (!li.CurLink) { + if (li.StatusFlag == CcuChainIter::StartOfChain) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuChain::InsertBefore\n"); + abort (); + } + } else if (li.StatusFlag == CcuChainIter::EndOfChain) { + Append (e); + } else { + InsertBefore (li.CurLink, e); + } +} + +/*? +Remove the element after the current element of the iterator \var{li}. +If \var{li} points before the beginning of the list, the first element is returned. +If \var{li} points at the last element, the status flag is set to \var{TooFar}. +If the list is empty, the flag is set to \var{EmptyChain}. In both cases, the +return value is null. +This function may be used +when one wants to iterate through a list and remove some elements: + CcuChainIter li (l); + CcuChainIter lj (l); + while (++li) + if (do_remove (*li)) { + RemoveAfter (lj); + li = lj; + } else + ++lj; +?*/ +CcuChainItem* +CcuChain :: RemoveAfter (const CcuChainIter& li) +{ + if (li.TheChain != this) { + StatusFlag = BadIterator; + return 0; + } + if (li.CurLink == LastLink) { + StatusFlag = LastLink ? TooFar : WasEmpty; + return 0; + } + StatusFlag = NoError; + if (li.CurLink) { + return RemoveAfter (li.CurLink); + } else { + return RemoveAfter (LastLink); + } +} + + +/*? +Get the current entry pointed by an iterator. This operator returns 0 if the iterator is +at the beginning or the end of the list. To distinguish those cases from the +case when the entry is null, you can use the method \fun{GetStatus}. +?*/ +CcuChainItem* +CcuChainIter :: operator * () const +{ + return (CurLink && StatusFlag == Normal) ? CurLink : 0; +} + + +/*? +Take one step of iteration. +?*/ +CcuChainIter& +CcuChainIter :: operator ++ () +{ + /* This test covers all the cases : + - the iteration has already begun, and is at its end. + - the iteration has not begun, but the list is empty. + */ + if (CurLink == TheChain->LastLink) { + StatusFlag = EndOfChain; + } else { + CurLink = CurLink ? TheChain->GetNext (CurLink) : TheChain->GetNext (TheChain->LastLink); + StatusFlag = Normal; + } + return *this; +} + + +/*? +Try and find the element \var{e} in the list, starting from the +current position of the iterator (this position not included). +If \var{e} is present, the iterator will +be correctly positionned. If not, it will have reached the end of the list. +?*/ +int +CcuChainIter :: Find (CcuChainItem* e) +{ + while (++(*this)) + if (**this == e) + return 1; + return 0; +} diff --git a/utils/Chain.h b/utils/Chain.h new file mode 100644 index 0000000..b9ecf61 --- /dev/null +++ b/utils/Chain.h @@ -0,0 +1,111 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * generic chains of objects - to be updated + * + * $Id$ + * $CurLog$ + */ + +#ifndef Chain_H_ +#define Chain_H_ + +#include "cplus_bugs.h" + +typedef void CcuChainItem; + +class CcuChainIter; + + +class CcuChain { +friend class CcuChainIter; +public: + enum chain_status { NoError, WasEmpty, TooEarly, TooFar, BadIterator }; + +protected: + CcuChainItem* LastLink; + chain_status StatusFlag; +inline CcuChain () : LastLink (0), StatusFlag (NoError) { } +inline CcuChain (CcuChainItem* e) : LastLink (e), StatusFlag (NoError) { } +virtual ~CcuChain (); + +virtual CcuChainItem* GetNext (CcuChainItem*) const = 0; +virtual void SetNext (CcuChainItem*, CcuChainItem*) const = 0; +virtual void Delete (CcuChainItem*) const = 0; + CcuChainItem* GetPrevious (CcuChainItem*) ; + +public: +inline chain_status GetStatus () const { return StatusFlag; } +inline int IsEmpty () const { return !LastLink; } + CcuChainItem* First (); + CcuChainItem* Last (); + CcuChainItem* Nth (int n); + int Length () const; + int Find (CcuChainItem*) const; + + void Append (CcuChainItem*); + void Prepend (CcuChainItem*); +inline CcuChain& operator << (CcuChainItem* it) { Append (it); return *this; } + + CcuChainItem* RemoveFirst (); + CcuChainItem* RemoveLast (); + int Remove (CcuChainItem*); + int Remove (int (*) (CcuChainItem*)); + void Clear (); + + void InsertAfter (const CcuChainIter&, CcuChainItem*); + void InsertBefore (const CcuChainIter&, CcuChainItem*); + CcuChainItem* RemoveAfter (const CcuChainIter&); + void InsertAfter (CcuChainItem*, CcuChainItem*); + void InsertBefore (CcuChainItem*, CcuChainItem*); + CcuChainItem* RemoveAfter (CcuChainItem*); +}; + +class CcuChainIter { +friend class CcuChain; +public: + enum chainiter_status { Normal, StartOfChain, EndOfChain }; +private: + const CcuChain* TheChain; + CcuChainItem* CurLink; + chainiter_status StatusFlag; + +public: +inline CcuChainIter (const CcuChain& l) : TheChain (&l), CurLink (0), StatusFlag (StartOfChain) { } +inline void Reset () { CurLink = 0; StatusFlag = StartOfChain; } + CcuChainIter& operator ++ (); + CcuChainItem* operator * () const; + int Find (CcuChainItem*); +inline chainiter_status GetStatus () const { return StatusFlag; } +inline operator int () const { return StatusFlag == Normal; } +}; + +#ifndef CPLUS_BUG19 + +template class CcuChainOf : public CcuChain { +protected: + CcuChainItem* GetNext (CcuChainItem* i) const { return ((ITEM*) i)->GetNext (); } + void SetNext (CcuChainItem* i, CcuChainItem* j) const { ((ITEM*) i)->SetNext ((ITEM*) j); } + void Delete (CcuChainItem* i) const { delete (ITEM*) i; } + +public: +inline CcuChainOf () : CcuChain () { } +inline CcuChainOf (ITEM* e) : CcuChain (e) { } +inline ~CcuChainOf () {} +}; + +template class CcuChainIterOf : public CcuChainIter { +public: +inline CcuChainIterOf (const CcuChainOf & l) : CcuChainIter (l) { } +inline ITEM* operator * () const { return (ITEM*) CcuChainIter::operator * (); } +}; + +#endif /* CPLUS_BUG19 */ + +#endif /* Chain_H_ */ + diff --git a/utils/DList.cc b/utils/DList.cc new file mode 100644 index 0000000..5d34f7b --- /dev/null +++ b/utils/DList.cc @@ -0,0 +1,573 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic double-linked lists (original ideas by Yves Berteaud) + * + * $Id$ + * $CurLog$ + */ + +#include "DList.h" +#include "Allocator.h" +#include +#include + +/*?class CcuDList + +\dessin{CcuDList}{Internal structure of \typ{CcuDList}s} + +?*/ + +#ifdef CPLUS_BUG20 +class CcuDListLink { +static CcuAllocator* DListLinkMem; +static void ClassInit (); +public: + CcuDListItem* Entry; + CcuDListLink* Previous; + CcuDListLink* Next; +inline CcuDListLink (CcuDListItem* e, CcuDListLink* p) : Entry (e), Previous (p), Next (p->Next) { Previous->Next = Next->Previous = this; } +inline CcuDListLink (CcuDListItem* e) : Entry (e), Previous (this), Next (this) {} + void* operator new (unsigned int); + void operator delete (void*); +}; +#endif + + +#ifdef CPLUS_BUG20 +CcuAllocator* CcuDListLink::DListLinkMem = 0; +#else +CcuAllocator* CcuDList::CcuDListLink::DListLinkMem = 0; +#endif + +/*?nodoc?*/ +void* +#ifdef CPLUS_BUG20 +CcuDListLink :: operator new (unsigned int) +#else +CcuDList::CcuDListLink :: operator new (unsigned int) +#endif +{ + if (!DListLinkMem) +#ifdef CPLUS_BUG20 + DListLinkMem = new CcuAllocator (sizeof (CcuDListLink)); +#else + DListLinkMem = new CcuAllocator (sizeof (CcuDList::CcuDListLink)); +#endif + return DListLinkMem->Alloc (); +} + +/*?nodoc?*/ +void +#ifdef CPLUS_BUG20 +CcuDListLink :: operator delete (void* that) +#else +CcuDList::CcuDListLink :: operator delete (void* that) +#endif +{ + DListLinkMem->Free (that); +} + + + +#ifdef DOC +/*? +Create an empty list. +?*/ +CcuDList :: CcuDList () +{ +} +#endif + +/*? +Create a list with one element \var{e}. +?*/ +CcuDList :: CcuDList (CcuDListItem* e) +: LastLink (new CcuDListLink (e)), + StatusFlag (NoError) +{ +} + +/*?nodoc?*/ +CcuDList :: CcuDList (const CcuDList& l) +: LastLink (0), + StatusFlag (NoError) +{ + CcuDListIter li (l); + while (++li) + Append (*li); +} + + +/*? +Destructor for lists. No operation is performed on the elements. +?*/ +CcuDList :: ~CcuDList () +{ + Clear (); +} + +/*? +Empty a list. +?*/ +void +CcuDList :: Clear () +{ + CcuDListLink* del = LastLink; + while (del) { + CcuDListLink* next = del->Next; + if (next == LastLink) + next = 0; + delete del; + del = next; + } + LastLink = 0; +} + +/*?nodoc?*/ +CcuDList& +CcuDList :: operator = (const CcuDList& l) +{ + if (this != &l) { + Clear (); + CcuDListIter li (l); + while (++li) + Append (*li); + } + return *this; +} + + +/*?nextdoc?*/ +CcuDListItem* +CcuDList :: First () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return LastLink->Next->Entry; +} + +/*? +Return the first (resp. last) element in the list, or 0 if the list was empty. +The case of a null element can be distinguished from the case +when the list is empty with the function \fun{GetStatus}. +?*/ +CcuDListItem* +CcuDList :: Last () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return LastLink->Entry; +} + +/*? +Get the \var{n}-th element of a list. If \var{n} is greater than the length of the list +this function returns 0 and sets the status to \var{TooFar}. If \var{n} is negative, +this function returns 0 but sets the status to \var{NoError}. +?*/ +CcuDListItem* +CcuDList :: Nth (int n) +{ + StatusFlag = NoError; + if (n <= 0) + return 0; + CcuDListIter li (*this); + while (n > 0 && ++li) + --n; + if (n != 0) + StatusFlag = TooFar; + return *li; +} + +/*? +Compute the number of elements in a list. +?*/ +int +CcuDList :: Length () const +{ + int result = 0; + CcuDListIter li (*this); + while (++li) + ++result; + return result; +} + +/*? +Check whether an item is present in a list. +?*/ +int +CcuDList :: Find (CcuDListItem* e) const +{ + CcuDListIter li (*this); + while (++li) + if (*li == e) + return 1; + return 0; +} + +/*?nextdoc?*/ +void +CcuDList :: Prepend (CcuDListItem* e) +{ + if (LastLink) + new CcuDListLink (e, LastLink); + else + LastLink = new CcuDListLink (e); +} + +/*? +Add an element at the beginning (resp. end) of a list. +?*/ +void +CcuDList :: Append (CcuDListItem* e) +{ + if (LastLink) { + LastLink = new CcuDListLink (e, LastLink); + } else + LastLink = new CcuDListLink (e); +} + +/*? +Remove the first element of a list and return it. +?*/ +CcuDListItem* +CcuDList :: RemoveFirst () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + return RemoveLink (LastLink->Next); +} + + + +/*? +Remove the last element of a list and return it. +?*/ +CcuDListItem* +CcuDList :: RemoveLast () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + return RemoveLink (LastLink); +} + + +/*? +Insert an element after the link \var{l}. +?*/ +void +CcuDList :: InsertAfterLink (CcuDListLink* l, CcuDListItem* e) +{ + CcuDListLink* newlink = new CcuDListLink (e, l); + if (LastLink == l) + LastLink = newlink; +} + +/*? +Remove a link. +?*/ +CcuDListItem* +CcuDList :: RemoveLink (CcuDListLink* l) +{ + /* store its data */ + CcuDListItem* data = l->Entry; + if (l->Next == l) + LastLink = 0; + else { + l->Previous->Next = l->Next; + l->Next->Previous = l->Previous; + if (l == LastLink) + LastLink = l->Previous; + } + /* delete it */ + delete l; + /* return its data */ + return data; +} + + +/*? +Remove an element from a list. This function iterates through the list until it deletes +\var{num} appearances of \var{entry}. The actual number of removals is returned. +If \var{num} is \var{All} or is negative, all appearances of \var{entry} are deleted. +?*/ +int +CcuDList :: Remove (CcuDListItem* entry, int num) +{ + int removed = 0; + CcuDListIter li (*this); + while ((num < 0 || removed < num) && ++li) { + if (*li == entry) { + RemoveLink (li.CurLink); + removed++; + break; + } + } + return removed; +} + +/*? +Remove elements from a list. This function iterates through the list until it deletes +\var{num} elements for which the function \var{p} returns a non-null value. +The actual number of removals is returned. +If \var{num} is \var{All} or is negative, all matching elements are deleted. +?*/ +int +CcuDList :: Remove (int (*p) (CcuDListItem*), int num) +{ + int removed = 0; + CcuDListIter li (*this); + while ((num < 0 || removed < num) && ++li) { + if ((*p) (*li)) { + RemoveAt (li); + ++removed; + } + } + return removed; +} + +/*?nextdoc?*/ +void +CcuDList :: InsertAfter (const CcuDListIter& li, CcuDListItem* e) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return; + } + if (!li.CurLink) { + if (li.StatusFlag == CcuDListIter::StartOfList) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuDList::InsertAfter\n"); + abort (); + } + } else if (li.StatusFlag == CcuDListIter::EndOfList) { + Append (e); + } else { + InsertAfterLink (li.CurLink, e); + } +} + +/*? +Insert an element before (resp. after) the current position of the iterator \var{li}. +These functions are both equivalent to \fun{CcuDList::Prepend} if the iterator is at the +beginning of the list (ie. before the first element). +\fun{InsertAfter} and \fun{InsertAfter} are performed in a constant time. +?*/ +void +CcuDList :: InsertBefore (const CcuDListIter& li, CcuDListItem* e) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return; + } + if (!li.CurLink) { + if (li.StatusFlag == CcuDListIter::StartOfList) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuDList::InsertAfter\n"); + abort (); + } + } else if (li.StatusFlag == CcuDListIter::EndOfList) { + Append (e); + } else { + new CcuDListLink (e, li.CurLink->Previous); + } +} + +/*? +Remove the element after the current element of the iterator \var{li}. +If \var{li} points before the beginning of the list, the first element is returned. +If \var{li} points at the last element, the status flag is set to \var{TooFar}. +If the list is empty, the flag is set to \var{EmptyList}. In both cases, the +return value is null. +?*/ +CcuDListItem* +CcuDList :: RemoveAfter (const CcuDListIter& li) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return 0; + } + if (li.CurLink == LastLink) { + StatusFlag = LastLink ? TooFar : WasEmpty; + return 0; + } + StatusFlag = NoError; + if (li.CurLink) { + return RemoveLink (li.CurLink->Next); + } else { + return RemoveLink (LastLink->Next); + } +} + +/*? +Remove the element pointed at by the iterator \var{li}. +If \var{li} points before the beginning of the list, or has reached +its end, the return value is null, and the status flag is set to \var{TooEarly} +{resp. \var{TooFar}). In all other cases, \var{li} is rewinded by one step, +in order to allow such loops as: + CcuDListIter li (l); + while (++li) { + if (do_remove (*li)) + l.RemoveAt (l); + } +?*/ +CcuDListItem* +CcuDList :: RemoveAt (CcuDListIter& li) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return 0; + } + if (!li.CurLink) { + StatusFlag = TooEarly; + return 0; + } + if (li.StatusFlag == CcuDListIter::EndOfList) { + StatusFlag = TooFar; + return 0; + } + StatusFlag = NoError; + CcuDListLink* del = li.CurLink; + --li; + return RemoveLink (del); +} + + +#ifdef DOC +/*? +Initialize an iterator associated to the list \var{l}. That iterator will point at the beginning +of the list, {\em before} the first element. +?*/ +CcuDListIter :: CcuDListIter (CcuDList& l) +{ +} + +/*? +Get the status of an iterator. The status may be one of \var{Normal, StartOfList}, or +\var{EndOfList} +?*/ +dlistiter_status +CcuDListIter :: GetStatus () const +{ +} + +/*? +Reset an iterator to the beginning of the list. +?*/ +void +CcuDListIter :: Reset () +{ +} +#endif + + +/*? +Get the current entry pointed by an iterator. This operator returns 0 if the iterator is +at the beginning or the end of the list. To distinguish those cases from the +case when the entry is null, you can use the method \fun{GetStatus}. +?*/ +CcuDListItem* +CcuDListIter :: operator * () const +{ + return (CurLink && StatusFlag == Normal) ? CurLink->Entry : 0; +} + +#ifdef DOC + +/*? +Check whether the status of an iterator is \var{Normal}. +?*/ +CcuDListIter :: operator int () const +{ +} +#endif + + +/*? +Take one step of iteration. +?*/ +CcuDListIter& +CcuDListIter :: operator ++ () +{ + /* This test covers all the cases : + - the iteration has already begun, and is at its end. + - the iteration has not begun, but the list is empty. + */ + if (CurLink == TheList->LastLink) { + StatusFlag = EndOfList; + } else { + CurLink = CurLink ? CurLink->Next : TheList->LastLink->Next; + StatusFlag = Normal; + } + return *this; +} + +/*? +Rewind iteration by one step. +?*/ +CcuDListIter& +CcuDListIter :: operator -- () +{ + if (StatusFlag == Normal) { + CurLink = CurLink->Previous; + if (CurLink == TheList->LastLink) + Reset (); + } else if (StatusFlag == EndOfList) { + StatusFlag = Normal; + } + return *this; +} + +/*? +Try and find the element \var{e} in the list, starting from the +current position of the iterator (this position not included). +If \var{e} is present in the list, the iterator will +be correctly positionned. If not, it will have reached the end of the list. +?*/ +int +CcuDListIter :: Find (CcuDListItem* e) +{ + while (++(*this)) + if (**this == e) + return 1; + return 0; +} + +/*? +Try and find the element \var{e} in the list, searching backward from the +current position of the iterator (this position not included). +If \var{e} is present in the list, the iterator will +be correctly positionned. If not, it will have reached the end of the list. +?*/ +int +CcuDListIter :: FindBack (CcuDListItem* e) +{ + while (--(*this)) + if (**this == e) + return 1; + return 0; +} + diff --git a/utils/DList.h b/utils/DList.h new file mode 100644 index 0000000..9c978b3 --- /dev/null +++ b/utils/DList.h @@ -0,0 +1,159 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic double-linked lists (original ideas by Yves Berteaud) + * + * $Id$ + * $CurLog$ + */ + +#ifndef DList_H_ +#define DList_H_ + +#include "cplus_bugs.h" + +class CcuAllocator; + +typedef void CcuDListItem; + +#ifdef CPLUS_BUG20 +class CcuDListLink; +#endif + +class CcuDList { +friend class CcuDListIter; + +#ifndef CPLUS_BUG20 + class CcuDListLink { + static CcuAllocator* DListLinkMem; + public: + CcuDListItem* Entry; + CcuDListLink* Previous; + CcuDListLink* Next; + inline CcuDListLink (CcuDListItem* e, CcuDListLink* p) : Entry (e), Previous (p), Next (p->Next) { Previous->Next = Next->Previous = this; } + inline CcuDListLink (CcuDListItem* e) : Entry (e), Previous (this), Next (this) {} + void* operator new (unsigned int); + void operator delete (void*); + }; +#endif + +public: + enum dlist_status { NoError, WasEmpty, TooEarly, TooFar, BadIterator }; + enum dlist_remove { All = -1 }; + +private: + + CcuDListLink* LastLink; + dlist_status StatusFlag; + + void InsertAfterLink (CcuDListLink*, CcuDListItem*); + CcuDListItem* RemoveLink (CcuDListLink*); + +public: +inline CcuDList () : LastLink (0), StatusFlag (NoError) { } + CcuDList (CcuDListItem*); + CcuDList (const CcuDList&); + ~CcuDList (); + CcuDList& operator = (const CcuDList&); +inline dlist_status GetStatus () const { return StatusFlag; } + +inline int IsEmpty () const { return !LastLink; } + CcuDListItem* First (); + CcuDListItem* Last (); + CcuDListItem* Nth (int n); + int Length () const; + int Find (CcuDListItem*) const; + + void Append (CcuDListItem*); + void Prepend (CcuDListItem*); +inline CcuDList& operator << (CcuDListItem* it) { Append (it); return *this; } + + CcuDListItem* RemoveFirst (); + CcuDListItem* RemoveLast (); + int Remove (CcuDListItem*, int = 1); + int Remove (int (*) (CcuDListItem*), int = 1); + void Clear (); + + void InsertAfter (const CcuDListIter&, CcuDListItem*); + void InsertBefore (const CcuDListIter&, CcuDListItem*); + CcuDListItem* RemoveAfter (const CcuDListIter&); + CcuDListItem* RemoveAt (CcuDListIter&); +}; + +class CcuDListIter { +friend class CcuDList; + +public: + enum dlistiter_status { Normal, StartOfList, EndOfList }; + +private: + const CcuDList* TheList; +#ifdef CPLUS_BUG20 + CcuDListLink* CurLink; +#else + CcuDList::CcuDListLink* CurLink; +#endif + dlistiter_status StatusFlag; + +public: +inline CcuDListIter (const CcuDList& l) : TheList (&l), CurLink (0), StatusFlag (StartOfList) {} +inline void Reset () { CurLink = 0; StatusFlag = StartOfList; } +inline void GotoEnd () { CurLink = TheList->LastLink; StatusFlag = CurLink ? EndOfList : StartOfList; } +inline CcuDListIter& operator = (const CcuDList& l) { TheList = &l; CurLink = 0; StatusFlag = StartOfList; return *this; } +inline CcuDListIter& operator = (const CcuDListIter& li) { TheList = li.TheList; CurLink = li.CurLink; StatusFlag = li.StatusFlag; return *this; } + CcuDListIter& operator ++ (); + CcuDListIter& operator -- (); + int Find (CcuDListItem*); + int FindBack (CcuDListItem*); + CcuDListItem* operator * () const; +inline dlistiter_status GetStatus () const { return StatusFlag; } +inline operator int () const { return StatusFlag == Normal; } +}; + + +#ifndef CPLUS_BUG19 +template class CcuDListIterOf; + +template class CcuDListOf : public CcuDList { +public: +inline CcuDListOf () : CcuDList () {} +inline CcuDListOf (ITEM* it) : CcuDList (it) {} +inline ITEM* First () { return (ITEM*) (CcuDList::First ()); } +inline ITEM* Last () { return (ITEM*) (CcuDList::Last ()); } +inline ITEM* Nth (int n) { return (ITEM*) (CcuDList::Nth (n)); } +inline int Find (ITEM* it) const { return CcuDList::Find (it); } + +inline void Append (ITEM* it) { CcuDList::Append (it); } +inline void Prepend (ITEM* it) { CcuDList::Prepend (it); } +inline CcuDListOf& operator << (ITEM* it) { CcuDList::Append (it); return *this; } + +inline ITEM* RemoveFirst () { return (ITEM*) (CcuDList::RemoveFirst ()); } +inline ITEM* RemoveLast () { return (ITEM*) (CcuDList::RemoveLast ()); } +inline int Remove (ITEM* it, int nb = 1) { return CcuDList::Remove (it, nb); } +inline int Remove (int (*p) (ITEM*), int nb = 1) { return CcuDList::Remove ((int (*) (ITEM*)) p, nb); } + +inline void InsertAfter (const CcuDListIterOf & li, ITEM*it) { CcuDList::InsertAfter (li, it); } +inline void InsertBefore (const CcuDListIterOf & li, ITEM* it) { CcuDList::InsertBefore (li, it); } +inline ITEM* RemoveAfter (const CcuDListIterOf & li) { return (ITEM*) CcuDList::RemoveAfter (li); } +inline ITEM* RemoveAt (CcuDListIterOf & li) { return (ITEM*) CcuDList::RemoveAfter (li); } +}; + +template class CcuDListIterOf : public CcuDListIter { +public: +inline CcuDListIterOf (const CcuDListOf & l) : CcuDListIter (l) { } +inline CcuDListIterOf& operator = (const CcuDListOf & l) { return (CcuDListIterOf&) CcuDListIter::operator = (l); } +inline CcuDListIterOf& operator = (const CcuDListIterOf& li) { return (CcuDListIterOf&) CcuDListIter::operator = (li); } +inline ITEM* operator * () const { return (ITEM*) CcuDListIter::operator * (); } +inline int Find (ITEM* it) { return CcuDListIter::Find (it); } +inline int FindBack (ITEM* it) { return CcuDListIter::FindBack (it); } +}; +#endif /* CPLUS_BUG19 */ + + +#endif /* DList_H_ */ + diff --git a/utils/DirPath.cc b/utils/DirPath.cc new file mode 100644 index 0000000..0536eb2 --- /dev/null +++ b/utils/DirPath.cc @@ -0,0 +1,214 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * management of search paths + * + * $Id$ + * $CurLog$ + */ + +#include "DirPath.h" +#include "String.h" +#include +#include +#include +#include + +/*?class CcuDirPath +\typ{CcuDirPath}s generalize the idea contained in the \com{PATH} environment variable +of UNIX. +A \typ{CcuDirPath} is a list of strings, which are thought of as directory names. +When looking for a file, each directory in the list is scanned, until the file is found or the +end of the list is reached. +?*/ + + +/*? +Construct an empty directory path. +?*/ +CcuDirPath :: CcuDirPath () +: CcuList (), + Alloc (DontAllocNames) +{ +} + +/*? +Construct an empty directory path. +The default allocation mode is set to \var{alloc} (see function \fun{FindFile}). +All other constructors initialize it to 0. +?*/ +CcuDirPath :: CcuDirPath (alloc_mode alloc) +: CcuList (), + Alloc (alloc) +{ +} + +/*? +Construct a \typ{CcuDirPath} which has one element \var{name}. The string \var{name} +is copied. +?*/ +CcuDirPath :: CcuDirPath (const char* name) +: CcuList (NewString (name)), + Alloc (DontAllocNames) +{ +} + +/*? +Construct a \typ{CcuDirPath} with two or more elements (\var{first}, \var{second}, +and so on). All strings (\var{first} and the following ones) are copied. +{\bf The argument list must be null-terminated.} +?*/ +CcuDirPath :: CcuDirPath (const char* first, const char*, ...) +: CcuList (), + Alloc (DontAllocNames) +{ + + va_list ap; + va_start(ap, first); + + for (;;) { + const char* p = va_arg(ap,char*); + if (!p) + break; + Append (p); + } + + va_end(ap); +} + +/*?nodoc?*/ +CcuDirPath :: ~CcuDirPath () +{ + CcuListIter li (*this); + while (++li) + FreeString ((char*) (*li)); +} + +/*?nextdoc?*/ +void +CcuDirPath :: Append (const char* dir) +{ + CcuList::Append (NewString (dir)); +} + +/*? +Append (resp. prepend) a directory name to a search path. A copy of the +string \var{dir} is created. +?*/ +void +CcuDirPath :: Prepend (const char* dir) +{ + CcuList::Prepend (NewString (dir)); +} + +/*?nodoc?*/ +int +CcuDirPath :: Remove (const char* d) +{ + int removed = 0; + CcuListIter li (*this); + CcuListIter lj (*this); + while (++li) { + int remove = (strcmp (d, (const char*) *li) == 0); + if (remove) { + ++removed; + RemoveAfter (lj); + } else + ++lj; + } + return removed; +} + +/*? +Search a path for a readable file with name \var{fn}. The absolute path name +is returned, or 0 if the search fails. +If the search succeeds, \var{alloc} determines whether +the returned name should be a dynamically allocated string or not. +If \var{alloc} is not null, an allocation is performed. +If \var{alloc} is 0, and \var{fn} was already a full pathname, \var{fn} is returned. +If \var{alloc} is 0, and \var{fn} was a relative pathname found in the search path, +a named stored in a static buffer is returned. +A pathname is considered a full pathname (and hence is not looked up in +the search path) if it begins with ``\com{/}'', ``\com{./}'' or ``\com{../}''. +?*/ +const char* +CcuDirPath :: FindFile (const char* fn, alloc_mode alloc) +{ + if (!fn) + return 0; + + static char absfn[128]; + char *dir; + char* pathend; + + /* If fn begins with '/', './' or '../' it is considered absolute */ + + register const char* p = fn; + while (*p == '.') + ++p; + if ((p - fn) <= 2 && (! *p || *p == '/')) + return access (fn, R_OK) ? 0 : alloc ? NewString (fn) : fn; + + /* Else, look through search path */ + + CcuListIter it (*this) ; + while (++it) { + dir = (char*) (*it); + strcpy (absfn, dir); + pathend = absfn + strlen (dir); + if (*(pathend-1) != '/') { + *pathend++ = '/'; + *pathend = '\0'; + } + strcat (absfn, fn); + if (access (absfn, R_OK) == 0) + return (alloc != DontAllocNames) ? NewString (absfn) : absfn; + } + return 0; +} + +#ifdef DOC + +/*? +This function is similar to the previous one. +It uses the allocation mode of this \typ{CcuDirPath} to decide whether to allocate +the returned string or not. +?*/ +const char* +CcuDirPath :: FindFile (const char* fn) +{ +} + +/*? +Set the allocation mode of this dir path to \var{alloc}. +?*/ +void +CcuDirPath :: SetAlloc (alloc_mode alloc) +{ +} + +#endif /* DOC */ + +/*? +Add the directories contained in a string of the same form as the environment variable ``PATH'', +i.e. dir1:dir2:\ldots:dirN. \var{sep} is the character separating the different components. +Its default value is ``:''. +?*/ +void +CcuDirPath :: AppendEnvPath (const char* path, char sep) +{ + const char *dir, *next = path; + + for (dir = path; next; dir = next+1) { + next = strchr (dir, sep); + if (next != dir) + CcuList::Append (next ? NewString (dir, next-dir) : NewString (dir)); + } +} + diff --git a/utils/DirPath.h b/utils/DirPath.h new file mode 100644 index 0000000..3fe377e --- /dev/null +++ b/utils/DirPath.h @@ -0,0 +1,44 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * management of search paths + * + * $Id$ + * $CurLog$ + */ + + +#ifndef DirPath_H_ +#define DirPath_H_ + +#include "cplus_bugs.h" +#include "List.h" + +class CcuDirPath : public CcuList { +public: + enum alloc_mode { DontAllocNames, DoAllocNames }; +private: + alloc_mode Alloc; +public: + CcuDirPath (); + CcuDirPath (alloc_mode); + CcuDirPath (const char*); + CcuDirPath (const char*, const char*, ...); + ~CcuDirPath (); + void Append (const char*); + void Prepend (const char*); + void AppendEnvPath (const char*, char sep = ':'); + int Remove (const char*); +inline void SetAlloc (alloc_mode alloc) { Alloc = alloc; } + const char* FindFile (const char*, alloc_mode); +inline const char* FindFile (const char* fn) { return FindFile (fn, Alloc); } +}; + +#endif /* DirPath_H_ */ + diff --git a/utils/HashTable.cc b/utils/HashTable.cc new file mode 100644 index 0000000..03bfd9a --- /dev/null +++ b/utils/HashTable.cc @@ -0,0 +1,635 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic hash tables and dictionnaries + * (Original C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + +#include +#include "String.h" +#include "HashTable.h" +#include "Allocator.h" + +/*?class CcuHashTable +The class \typ{CcuHashTable} implements association tables based on a hashing algorithm. +Hash tables are useful to store information that needs to be retrieved +quickly, and which bears no efficient ordering. For instance, this is the +case for strings: +in a compiler, one may wish to maintain a hash table with identifiers +as hash keys and symbol table entries as information. + +A hash table is made of a set of hash entries (of class \typ{CcuHashCell}), +which can be modified during +the life of the table. An entry has two main fields: a hash key, and a user defined +information attached to that key. We will not give details about the structure of +a hash table, as they can be found in any book about algorithms. Figure~\ref{fig:hash} is only +here as a reminder. +\fig{hash}{Internals of a hash table} +The current implementation uses lists to store the synonyms so that entries can +be deleted efficiently. + +The class \typ{CcuHashTable} makes no assumption about the type of the keys, which it handles as +\typ{const void *}. + +The user can define several functions used when managing a hash table: the hash function, which +is determinant for the performances of the hash table, and the functions to copy, compare, and +destroy keys. Basic functions are provided by default. +?*/ + + + +CcuAllocator* CcuHashCell::HashCellMem = 0; + +/*?nodoc?*/ +void +CcuHashCell :: ClassInit () +{ + if (!HashCellMem) + HashCellMem = new CcuAllocator (sizeof (CcuHashCell)); +} + +/*?nodoc?*/ +void* +CcuHashCell :: operator new (unsigned int) +{ + return HashCellMem->Alloc (); +} + +/*?nodoc?*/ +void +CcuHashCell :: operator delete (void* that) +{ + HashCellMem->Free (that); +} + + + +/*? +Constructor for \typ{CcuHashTable}s. Build a hash table based on an array of +size \var{size}. +You can optionally provide your own functions for copying, destroying +and comparing keys, and the hashing function. If no hashing function is +provided, the identity function is used. +?*/ +CcuHashTable :: CcuHashTable (unsigned int size, HASH_F hash_fun, HCP_F cp_fun, HDEL_F del_fun, HCMP_F cmp_fun) +: Size (size), + Hash (hash_fun), + Copy (cp_fun), + Delete (del_fun), + Compare (cmp_fun) +{ + if (Size <= 0) + Size = 1; + Table = new CcuHashCell* [Size]; + memset (Table, 0, Size*sizeof (CcuHashCell*)); + + /* I know that HashCells can only be created from HashTables */ + if (!CcuHashCell::HashCellMem) + CcuHashCell::ClassInit (); +} + +/*? +Copy constructor for hash tables. The table and the cells are copied. The keys are +copied only if \var{ht} had a copy function. The new hash table will contain the +same informations as \var{ht}, but the synonyms will not necessarily be in the same order. +?*/ +CcuHashTable :: CcuHashTable (const CcuHashTable& ht) +: Size (ht.Size), + Hash (ht.Hash), + Copy (ht.Copy), + Delete (ht.Delete), + Compare (ht.Compare) +{ + Table = new CcuHashCell* [Size]; + register CcuHashCell** p = Table; + register CcuHashCell** q = ht.Table; + while (p < Table + Size) { + *p = 0; + register CcuHashCell* r = *q; + while (r) { + (*p) = new CcuHashCell (Copy ? (*Copy) (r->GetKey ()) : r->GetKey (), *p); + (*p)->SetInfo (r->Info); + r = r->Next; + } + ++p; + ++q; + } +} + +/*? +Destructor for hash tables. All keys are destroyed if a destruction function was provided. +?*/ +CcuHashTable :: ~CcuHashTable () +{ + Clear (); + +#ifdef CPLUS_BUG4 + delete [Size] Table; +#else + delete [] Table; +#endif +} + + +/*? +Remove all data from the hash table. All keys are destroyed if a destruction function was provided. +?*/ +void +CcuHashTable :: Clear () +{ + /* destroy keys */ + if (Delete) { + CcuHashCellIter hi (*this); + while (++hi) + (*Delete) ((*hi)->Key); + } + + /* destroy cells */ + int s = Size; + CcuHashCell** entry = Table; + + /* for each slot of the array ... */ + for ( ; s--; ++entry ) { + if (! *entry) + continue; + + /* ... destroy all cells linked from that slot ...*/ + for (CcuHashCell* h = *entry; h;) { + CcuHashCell* del = h; + h = h->Next; + delete del; + } + + /* ... and clear it */ + *entry = 0; + } +} + + +/*?hidden?*/ +CcuHashCell** +CcuHashTable :: HashKey (const void* key) const +{ + register unsigned int h = (unsigned int) key; + + if (Hash) + h = (*Hash) (key, Size); + + if (h >= Size) + h %= Size; + + return (Table + h); +} + +/*?hidden?*/ +CcuHashCell* +CcuHashTable :: FindCell (CcuHashCell** entry, const void* key) const +{ + CcuHashCell* h; + for (h = *entry; h; h = h -> Next) + if (Compare ? (*Compare) (key, h->Key) : (key == h->Key)) + break; + return h; +} + + +/*?hidden?*/ +CcuHashCell* +CcuHashTable :: AddCell (CcuHashCell** entry, const void* key) const +{ + if (Copy) + key = (* Copy) (key); + + CcuHashCell* h = new CcuHashCell (key, *entry); + *entry = h; + return h; +} + +/*?class CcuHashCell +\typ{CcuHashCell}s hold the entries of an hash table. +A \typ{CcuHashCell} contains a key and a user defined information. +?*/ + + +#ifdef DOC + +/*?hidden?*/ +CcuHashCellOf :: CcuHashCell (const void*, CcuHashCell*) +{ +} + +/*?nextdoc?*/ +const void* +CcuHashCell :: GetKey () const +{ +} + +/*? +Retrieve the key, or the information from a \typ{CcuHashCell}. +?*/ +CcuHashItem* +CcuHashCell :: GetInfo () const +{ +} + +/*? +Set the cell information to \var{p}. +?*/ +void +CcuHashCell :: SetInfo (CcuHashItem* p) +{ +} + +#endif + +/*? +Add the key \var{key} into the table. If +\var{found} is not 0, it is a return parameter which contains TRUE if the +key was already in the table, or FALSE if it was new. In both cases, the +function returns the address of the hash entry corresponding to the key. +\fun{Add} uses the hash function of the table. +If the key is new and a copy function was provided, the key is copied. +?*/ +CcuHashCell* +CcuHashTable :: Add (const void* key, int* found) +{ + /* est-il dans la table ? */ + CcuHashCell** entry = HashKey (key); + CcuHashCell* h = FindCell (entry, key); + + if (found) + *found = (h != 0); + + if (h) + return h; + + return AddCell (entry, key); +} + +/*? +Retrieve the key \var{key} from the table. If it exists, return +the address of its hash entry, thus allowing to get its associated info. If the key +does not exist in the table, return 0. +?*/ +CcuHashCell* +CcuHashTable :: Get (const void* key) +{ + CcuHashCell **entry = HashKey (key); + return FindCell (entry, key); +} + +#if 0 +/*? +Get a reference to the data stored in the table for the key \var{key}. That +reference can be used for reading as for writing. If the key was not present +in the table, a new entry is created. +?*/ +CcuHashItem*& +CcuHashTable :: operator [] (const void* key) +{ + CcuHashCell **entry = HashKey (key); + CcuHashCell *h = FindCell (entry, key); + + if (!h) + h = AddCell (entry, key); + + return h->Info; +} +#else +CcuHashCellRef +CcuHashTable :: operator [] (const void* key) const +{ + return CcuHashCellRef (*this, key); +} +#endif + + +/*? +Remove the key \var{key} from the table. If it exists, return its +associated data. If the key does not exist, return 0. \var{found} may +be used to test whether the key was found. +?*/ +CcuHashItem* +CcuHashTable :: Remove (const void* key, int* found) +{ + CcuHashCell **entry; + register CcuHashCell *h, *hp = 0; + CcuHashItem* info = 0; + + entry = HashKey (key); + + for (h = *entry; h; h = h->Next) { + if (Compare ? (*Compare) (key, h->Key) : (key == h->Key)) { + /* remove it from the list */ + if (hp) + hp->Next = h->Next; + else + *entry = h->Next; + + /* free it, sparing its info */ + if (Delete) + (*Delete) (h->Key); + info = h->Info; + delete h; + break; + } + hp = h; + } + if (found) + *found = (h != 0); + return info; +} + + +/*? +Change the size of the table, which is re-hashed. +?*/ +void +CcuHashTable :: Resize (int size) +{ + int s = Size; + if (size <= 0) + size = 1; + Size = size; + + CcuHashCell** entry = Table; + CcuHashCell** old_table = Table; + Table = new CcuHashCell* [size]; + memset (Table, 0, size*sizeof (CcuHashCell*)); + + /* rehash */ + for (; s--; ++entry) { + + /* scan the list */ + register CcuHashCell *cur, *next; + for (cur = *entry; cur; cur = next) { + next = cur->Next; + + register CcuHashCell** slot = HashKey (cur->Key); + + /* prepend the cell to the corresponding list */ + cur->Next = *slot; + *slot = cur; + } + } +#ifdef CPLUS_BUG4 + delete [Size] old_table; +#else + delete [] old_table; +#endif +} + + +#ifdef TUNE +/*?nextdoc?*/ +void +CcuHashTable :: HashStats (int fd) +{ + CcuHashCell * h; + CcuHashCell **entry; + char msg[80]; + int s, coll = 0, empty = 0; + + for (s = Size, entry = Table; s--; entry++) { + if (h = *entry) { + sprintf (msg, "%s(%d)", h->Key, h->Info); + write (fd, msg, strlen (msg)); + while (h = h->Next) { + sprintf (msg, "\t%s(%d)", h->Key, h->Info); + write (fd, msg, strlen (msg)); + coll++; + } + write (fd, "\n", 1); + } else { + write (fd, "\n", 8); + empty++; + } + } + sprintf (msg, "size : %d; %d empty; %d collisions\n", Size, empty, coll); + write (fd, msg, strlen (msg)); +} + +/*? +Print some statistics about this hash table on file descriptor \var{fd} +(default is standard error). +?*/ +void +CcuHashTable :: CollStats (int fd) +{ + CcuHashCell * h; + CcuHashCell **entry; + char msg[80]; + int s, lcoll, coll = 0, empty = 0; + int min = 999999, max = 0, moy = 0, moy2 = 0; + float fmoy, fvar; + + for (s = Size, entry = (CcuHashCell**) Data; s--; entry++) { + lcoll = 0; + if (h = *entry) { + while (h = h->Next) { + coll++, lcoll++; + } +/* sprintf (msg, "%d colls\n", lcoll); + write (fd, msg, strlen (msg)); +*/ moy += lcoll; + moy2 += lcoll * lcoll; + if (lcoll < min) + min = lcoll; + if (lcoll > max) + max = lcoll; + } else { +/* write (fd, "\n", 8); +*/ empty++; + } + } + fmoy = ((float) moy) / ((float) Size); + fvar = fmoy * fmoy - (((float) moy2) / ((float) Size)); + sprintf (msg, "size : %d; %d empty; %d collisions\n", Size, empty, coll); + write (fd, msg, strlen (msg)); + sprintf (msg, "min : %d; max %d; moy %f; variance %f\n----\n\n", min, max, fmoy, fvar); + write (fd, msg, strlen (msg)); +} + +#endif /* TUNE */ + +CcuHashItem* +CcuHashCellRef :: operator = (CcuHashItem* info) +{ + CcuHashCell **entry = Table.HashKey (Key); + CcuHashCell *h = Table.FindCell (entry, Key); + + if (!h) + h = Table.AddCell (entry, Key); + + h->SetInfo (info); + + return info; +} + +CcuHashCellRef :: operator CcuHashItem* () +{ + CcuHashCell **entry = Table.HashKey (Key); + CcuHashCell *h = Table.FindCell (entry, Key); + return h ? h->GetInfo () : 0; +} + + +/*?class CcuDictionnary +For the common case when character strings are used as keys, +the class \typ{CcuDictionnary} was derived from the class \typ{CcuHashTable}. +It is the class that should be used for dictionaries, symbol tables,~\ldots\, +For this special kind of hash tables, keys are compared as strings, and are copied with the +function \fun{NewString} (see page~\pageref{newstring}). If users do not provide a hash function, +a default one is used. + +All the functions of class \typ{CcuHashTable} are available in class \typ{CcuDictionnary}. +The iterator \typ{Hashiter} can be used on \typ{CcuDictionnary} as well. +?*/ + + +/*?hidden?*/ +int +CcuDictionnary :: HashKey (const void* key, int) +{ + register int h = 0; + register const char *p = (const char *) key; + while (*p) + h ^= *p++; + return h; +} + +/*?hidden?*/ +int +CcuDictionnary :: CompareKey (const void* a, const void* b) +{ + register const char *p, *q; + /* on fait le strcmp a la main : ca va + vite */ + for (p = (const char *) a, q = (const char *) b; *p == *q++; p++) + if (*p == '\0') + return 1; + return 0; +} + +/*?hidden?*/ +void* +CcuDictionnary :: CopyKey (const void* k) +{ + return NewString ((const char*) k); +} + +/*?hidden?*/ +void +CcuDictionnary :: DeleteKey (void* k) +{ + FreeString ((char*) k); +} + +/*? +Constructor for \typ{CcuDictionnary}s. Initialize a \typ{CcuDictionnary} with an array of size \var{size}, +and \var{hash\_fun} as the hash function. If \var{hash\_fun} is not provided, the default +function is used. +?*/ +CcuDictionnary :: CcuDictionnary (int size, HASH_F f) +: CcuHashTable (size, (f ? f : HashKey), (HCP_F) (CopyKey), (HDEL_F) (DeleteKey), (HCMP_F) (CompareKey)) +{ +} + +/*?nodoc?*/ +CcuDictionnary :: ~CcuDictionnary () +{ +} + +/*?nodoc?*/ +void +CcuDictionnary :: KeyCopy (int flag) +{ + if (flag) { + Copy = (HCP_F) (&CopyKey); + Delete = (HDEL_F) &DeleteKey; + } else { + Copy = 0; + Delete = 0; + } +} + +/*?class Hashiter +The class \typ{Hashiter} makes it possible to iterate through the entries of an hash table. +?*/ + +#ifdef DOC +/*? +Constructor for \typ{CcuHashCellIter}s. Initialize an iterator on the hash table \var{t}. +?*/ +CcuHashCellIterOf :: CcuHashCellIter (const CcuHashTable& t) +{ +} + +/*? +Get the current cell pointed by an interator. +?*/ +CcuHashCell* +CcuHashCellIter :: operator * () const +{ +} +#endif + +/*? +Take one step of iteration. This operator returns a pointer on the next +hash entry of the table it is iterating on. When it is finished, it returns 0. +?*/ +CcuHashCellIter& +CcuHashCellIter :: operator ++ () +{ + register CcuHashCell* h = 0; + register int size = TheTable.GetSize (); + + + if (!CurCell || !(h = CurCell->Next)) + while ((++CurIndex < size) && !(h = (TheTable.Table [CurIndex]))) + ; + + CurCell = h; + return *this; +} + +#ifndef CPLUS_BUG16 +/*? +Post-increment equivalent of the previous operator. +?*/ +CcuHashCellIter +CcuHashCellIter :: operator ++ (int) +{ + CcuHashCellIter result = *this; + ++(*this); + return result; +} +#endif + +#ifndef CPLUS_BUG13 +CcuHashCellIter:: +#endif +hashiter_status +CcuHashCellIter :: Status () const +{ + if (CurCell) + return Normal; + if (CurIndex < 0) + return StartOfTable; + return EndOfTable; +} + +#ifdef DOC +CcuHashCellIter :: operator int () const +{ +} +#endif + diff --git a/utils/HashTable.h b/utils/HashTable.h new file mode 100644 index 0000000..798d7c9 --- /dev/null +++ b/utils/HashTable.h @@ -0,0 +1,212 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic hash tables and dictionnaries + * (Original C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + +#ifndef HashTable_H_ +#define HashTable_H_ + + +#include "cplus_bugs.h" + +class CcuAllocator; + +typedef void CcuHashItem; + +class CcuHashCell { +protected: +friend class CcuHashTable; +friend class CcuHashCellIter; +static CcuAllocator* HashCellMem; +static void ClassInit (); + + const void* Key; /* hash key */ + CcuHashItem* Info; /* data */ + CcuHashCell* Next; /* synonyms */ + +inline CcuHashCell (const void* k, CcuHashCell* n) : Key (k), Info (0), Next (n) {} + +public: +inline void SetInfo (CcuHashItem* p) { Info = p; } +inline CcuHashItem* GetInfo () const { return Info; } +inline const void* GetKey () const { return Key; } + + void* operator new (unsigned int); + void operator delete (void*); +}; + +class CcuHashCellRef { +friend class CcuHashTable; +protected: + const CcuHashTable& Table; + const void* Key; +inline CcuHashCellRef (const CcuHashTable& t, const void* key) : Table (t), Key (key) {} +#ifdef CPLUS_BUG1 +inline CcuHashCellRef (const CcuHashCellRef& t) : Table (t.Table), Key (t.Key) {} +#endif +public: + CcuHashItem* operator = (CcuHashItem*); + operator CcuHashItem* (); +}; + + +typedef int (*HASH_F) (const void*, int); +typedef int (*HCMP_F) (const void*, const void*); +typedef void* (*HCP_F) (const void*); +typedef void (*HDEL_F) (const void*); + +class CcuHashTable { +private: +friend class CcuHashCellIter; +friend class CcuHashCellRef; + +protected : + CcuHashCell** Table; + unsigned int Size; + HASH_F Hash; + HCP_F Copy; + HDEL_F Delete; + HCMP_F Compare; + + CcuHashCell** HashKey (const void*) const; + CcuHashCell* FindCell (CcuHashCell**, const void*) const; + CcuHashCell* AddCell (CcuHashCell**, const void*) const; + +public: + CcuHashTable (unsigned int, HASH_F = 0, HCP_F = 0, HDEL_F = 0, HCMP_F = 0); + CcuHashTable (const CcuHashTable&); + ~CcuHashTable (); + CcuHashCell* Add (const void*, int* = 0); + CcuHashCell* Get (const void*); + CcuHashItem* Remove (const void*, int* = 0); + void Clear (); + void Resize (int); +inline int GetSize () const { return Size; } + CcuHashCellRef operator [] (const void*) const; + +#ifdef TUNE + void HashStats (int fd = 2); + void CollStats (int fd = 2); +#endif +}; + +class CcuDictionnary : public CcuHashTable { +protected: +static void* CopyKey (const void*); +static void DeleteKey (void*); +static int CompareKey (const void*, const void*); +static int HashKey (const void*, int); + +public: + CcuDictionnary (int size, HASH_F = 0); + ~CcuDictionnary (); + + void KeyCopy (int); +}; + + +class CcuHashCellIter { +public: + enum hashiter_status { Normal, StartOfTable, EndOfTable, BadTable }; + +protected: + const CcuHashTable& TheTable; + int CurIndex; + CcuHashCell* CurCell; + +public: +inline CcuHashCellIter (const CcuHashTable& t) : TheTable (t) { CurIndex = -1; CurCell = 0; } +inline ~CcuHashCellIter () {} + +inline void Reset () { CurCell = 0; CurIndex = -1; } + CcuHashCellIter& operator ++ (); +#ifndef CPLUS_BUG16 + CcuHashCellIter operator ++ (int); +#endif +inline CcuHashCell* operator * () const { return CurCell; } + hashiter_status Status () const; +inline operator int () const { return CurCell != 0; } +}; + +class CcuHashIter : public CcuHashCellIter { +public: +inline CcuHashIter (const CcuHashTable& t) : CcuHashCellIter (t) { } +inline ~CcuHashIter () {} + +inline CcuHashIter& operator ++ () { ++((CcuHashCellIter) (*this)); return *this; } +inline CcuHashItem* operator * () const { return CurCell ? CurCell->GetInfo () : 0; } +}; + +#ifndef CPLUS_BUG19 + +template class CcuHashTableOf; +template class CcuDictionnaryOf; + +template class CcuHashCellOf : public CcuHashCell { +protected: +inline CcuHashCellOf (const void* k, CcuHashCellOf* n) : CcuHashCell (k, n) {} +public: +inline void SetInfo (ITEM* p) { CcuHashCell::SetInfo (p); } +inline ITEM* GetInfo () const { return (ITEM*) CcuHashCell::GetInfo (); } +}; + +template class CcuHashCellRefOf : public CcuHashCellRef { +friend class CcuHashTableOf; +friend class CcuDictionnaryOf; +protected: +inline CcuHashCellRefOf (const CcuHashTableOf& t, const void* key) : CcuHashCellRef (t, key) {} +#ifdef CPLUS_BUG1 +inline CcuHashCellRefOf (const CcuHashCellRefOf& t) : CcuHashCellRef (t) {} +#endif +public: +inline ITEM* operator = (ITEM* it) { return (ITEM*) (CcuHashCellRef::operator = (it)); } +inline operator ITEM* () { return (ITEM*) (CcuHashCellRef::operator CcuHashItem* ()); } +}; + + +template class CcuHashTableOf : public CcuHashTable { +public: +inline CcuHashTableOf (unsigned int size, HASH_F hash = 0, HCP_F cp = 0, HDEL_F del = 0, HCMP_F cmp= 0) + : CcuHashTable (size, hash, cp, del, cmp) {} +inline ~CcuHashTableOf () {} +inline CcuHashCellOf* Add (const void* key, int* found = 0) { return (CcuHashCellOf*) CcuHashTable::Add (key, found); } +inline CcuHashCellOf* Get (const void* key) { return (CcuHashCellOf*) CcuHashTable::Get (key); } +inline ITEM* Remove (const void* key, int* found = 0) { return (ITEM*) CcuHashTable::Remove (key, found); } +inline CcuHashCellRefOf operator [] (const void* key) const { return CcuHashCellRefOf (*this, key); } +}; + +template class CcuDictionnaryOf : public CcuDictionnary { +public: +inline CcuDictionnaryOf (unsigned int size, HASH_F hash = 0) : CcuDictionnary (size, hash) {} +inline ~CcuDictionnaryOf () {} +inline CcuHashCellOf* Add (const void* key, int* found = 0) { return (CcuHashCellOf*) CcuDictionnary::Add (key, found); } +inline CcuHashCellOf* Get (const void* key) { return (CcuHashCellOf*) CcuDictionnary::Get (key); } +inline ITEM* Remove (const void* key, int* found = 0) { return (ITEM*) CcuDictionnary::Remove (key, found); } +inline operator const CcuHashTableOf& () const { return *(const CcuHashTableOf*) this; } +inline CcuHashCellRefOf operator [] (const char* key) const { return CcuHashCellRefOf (*(const CcuHashTableOf*)this, key); } +}; + + +template class CcuHashIterOf : public CcuHashIter { +public: +inline CcuHashIterOf (const CcuHashTableOf& t) : CcuHashIter (t) { } +inline ~CcuHashIterOf () {} +inline CcuHashIterOf& operator ++ () { ++((CcuHashIter) (*this)); return *this; } +inline ITEM* operator * () const { return (ITEM*) (CcuHashIter::operator * ()); } +}; + +#endif /* CPLUS_BUG19 */ + +#endif /* HashTable_H_ */ + diff --git a/utils/IdTable.cc b/utils/IdTable.cc new file mode 100644 index 0000000..bd18e0a --- /dev/null +++ b/utils/IdTable.cc @@ -0,0 +1,319 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1990, 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * tables for managing an ID scheme, originally by Michel Beaudouin-Lafon + * + * $Id$ + * $CurLog$ + */ + +#include "IdTable.h" +#include + +/*?class CcuIdTable +The class \typ{CcuIdTable} stores object pointers in a table, and assigns them a unique identifier. +Objects can be added, removed and retrieved in constant time (roughly, an index and a test). +This makes this class very useful for distributed applications that usually need +to communicate object identifiers instead of object pointers. In such applications, +mapping the identifier to an object must be a very fast operation. + +The following paragraphs details the implementation of the ident table. + +An identifier (id for short) is a 32 bits number made of an index in a table +in the lower 16 bits, and a check number in the higher 16 bits. +An entry of the table contains a check number, a 16 bits type (for use by the application), +and the object pointer. +Each entry in the table corresponds to a unique id made of the check of this +entry and its index. + +Free entries in the table are linked in a free list by using the type field. +They also have a nil object pointer. +Each time an entry is reused, its check number is incremented. +Thus, the id corresponding to this entry differs from the previous id. + +To retrieve an object from its id, we need only index in the table (by masking the check +part of the id), and check the check number of the id against the check number +in the table. If they are different, the id is no more in the table. + +With 16 bits indexes, we can have at most \begin{math}2^{16}\end{math} entries +in the table. This is the maximum number of objects at any one time. +With 16 bits check we can generate \begin{math}2^{32}\end{math} different ids. +The check number wraps around so as to reuse (very) old identifiers. +This happens when a given entry has been used \begin{math}2^{16}\end{math} times. + +The table automatically grows when it is full, until its maximum size. +Note that growing the table only involves linking the new free entries. +This is far less expensive than rehashing a hash table for instance. +?*/ + +/*? +Build an ident table with \var{nb} entries. +The table grows automatically (by a factor of 2) until 32768 entries (the maximum). +?*/ +CcuIdTable :: CcuIdTable (int nb) +{ + if (nb > TID_MAX) + nb = TID_MAX; + entries = new CcuIdCell [nb]; + memset (entries, 0, nb * sizeof (CcuIdCell)); + last = entries + nb; + + // link free entries with the 'typ' field + int i = 0; + for (CcuIdCell* p = entries; p < last; p++) + p->typ = ++i; + + (--p)->typ = 0; // end of free list + free = 0; + last_free = --i; + num_free = nb; +} + +/*?hidden?*/ +bool +CcuIdTable :: Grow (int newNb) +{ + int nb = last - entries; + if (nb >= TID_MAX) + return FALSE; + + if (newNb >= TID_MAX) + newNb = TID_MAX; + + CcuIdCell* newTbl = new CcuIdCell [newNb]; + int size = nb * sizeof (CcuIdCell); + memcpy (newTbl, entries, size); + memset (newTbl + nb, 0, newNb * sizeof (CcuIdCell) - size); +#ifdef CPLUS_BUG4 + delete [nb] entries; +#else + delete [] entries; +#endif + entries = newTbl; + last = newTbl + newNb; + + // link free entries with the 'typ' field + int i = nb; + for (CcuIdCell* p = entries + nb; p < last; p++) + p->typ = ++i; + // prepend to current free list (to use them first) + (--p)->typ = free; + free = nb; + last_free = --i; + num_free += newNb - nb; + + return TRUE; +} + +/*? +Store an object in the table and return its unique identifier. +If the table is full, return 0 (0 cannot be a valid identifier). +\var{typ} is an optional value that it stored in the table with the object. +It can be used to store the type of the object. +\var{obj} cannot be 0. +?*/ +lword +CcuIdTable :: Store (const void* obj, sword typ) +{ + if (num_free == 0) + if (! Grow ((last - entries) * 2)) + return 0; + // get entry out of free list + register CcuIdCell* p = entries + free; + free = p->typ; + --num_free; + + p->chk++; + p->obj = obj; + p->typ = typ; + + return (p->chk << TID_SHIFT) | (p - entries); +} + +/*? +Remove object with identifier \var{id} from table. +Return FALSE if it was not found. +?*/ +bool +CcuIdTable :: Remove (lword id) +{ + register sword i = sword (id & TID_MASK); + register CcuIdCell* p = entries + i; + + if (p->chk != id >> TID_SHIFT) + return FALSE; + + // link at end of free list (this avoids reusing the same ids too often) + p->obj = 0; // mark free + if (num_free) + entries [last_free].typ = i; + else + free = i; + last_free = i; + num_free++; + + return TRUE; +} + +/*? +Retrieve object with identifier \var{id} from table. +Return the object pointer, or 0 if it was not found. +if \var{typ} is not 0, it is filled with the type of the object. +?*/ +const void* +CcuIdTable :: Get (lword id, sword* typ) +{ + register CcuIdCell* p; + + p = entries + (id & TID_MASK); + if (p->chk != id >> TID_SHIFT) + return 0; + if (typ) + *typ = p->typ; + return p->obj; +} + +/*? +Change the object pointer and the type of the entry associated to \var{id}. +The validity of the identifier is {\em not} checked. +The table is grown if the identifier falls out if it. +This makes it possible to store entries in the table with identifiers allocated +elsewhere, for instance to maintain a local copy of a remote table. +?*/ +void +CcuIdTable :: Change (lword id, const void* obj, sword typ) +{ + register CcuIdCell* p; + + p = entries + (id & TID_MASK); + int ip = p - entries; + + if (p >= last) { + int size = last - entries; + while (size <= ip) + size *= 2; + if (! Grow (size)) + return; + p = entries + ip; + } + + if (! p->obj) { + // it's in the free list + if (ip == free) { + // if we maintain two tables in sync, this will always be the case + free = p->typ; + } else { + int i = free; + int j; + while ((j = entries [i].typ) != ip) + i = j; + entries [i].typ = p->typ; + if (ip == last_free) + last_free = i; + } + num_free--; + } + p->chk = sword (id >> TID_SHIFT); + p->typ = typ; + p->obj = obj; +} + +/*?class CcuIdIter +The class \typ{CcuIdIter} is an iterator over \typ{CcuIdTable}. +?*/ + +/*?hidden?*/ +void +CcuIdIter :: Step () +{ + if (! cur) + return; + + // if table changed, reassign current + if (entries != idt->entries) { + cur = idt->entries + (cur - entries); + entries = idt->entries; + } + + // find valid entry + while (cur < idt->last) { + if (cur->obj) + return; + cur++; + } + cur = 0; +} + +#ifdef DOC +// fake entries for documentation + +/*? +Build an iterator over the table \var{t}. +?*/ +CcuIdIter :: CcuIdIter (CcuIdTable& t) +{ +} + +/*? +This operator is similar to \fun{Current} below, except that it +advances the iterator to the next valid entry if the current entry has ben removed. +The iterator can be on an invalid entry if the current entry is removed from +the iterator itself. +?*/ +const void* +CcuIdIter :: operator () () +{ +} + +/*? +Advance the iterator to the next entry and return its associated data. +Return NIL if the whole table has been enumerated. +Note that this cannot be distinguished from an NIL data associated to +the current entry. +?*/ +const void* +CcuIdIter :: operator ++ () +{ +} + +/*?nextdoc?*/ +const void* +CcuIdIter :: Current () +{ +} + +/*?nextdoc?*/ +sword +CcuIdIter :: CurType () +{ +} + +/*? +Return the information of the current entry: +its associated data, its type, and its ident. +If the iterator is finished, these functions return 0. +\fun{CurId} is the only function for which 0 cannot be returned +for a valid entry. So this is the most secure way to identify that the whole +table has been ennumerated. +?*/ +lword +CcuIdIter :: CurId () +{ +} + +/*? +Reset the iterator to enumerate the whole table again. +?*/ +void +CcuIdIter :: Reset () +{ +} + +#endif /* DOC */ + diff --git a/utils/IdTable.h b/utils/IdTable.h new file mode 100644 index 0000000..0b64219 --- /dev/null +++ b/utils/IdTable.h @@ -0,0 +1,79 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1990, 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * tables for managing an ID scheme, originally by Michel Beaudouin-Lafon + * + * $Id$ + * $CurLog$ + */ + +#ifndef IdTable_H_ +#define IdTable_H_ + +#include "word.h" +#include "bool.h" + +/* + * TID_MASK = 2^TID_SHIFT = max table size + * TID_MASK = TID_SHIFT bits set to 1. + */ +#define TID_MAX (2 << 16) +#define TID_SHIFT 16 +#define TID_MASK 0xffff + +struct CcuIdCell { + sword chk; // the check number + sword typ; // for the appli, for free list when not allocated + const void* obj; // the object +}; + +class CcuIdTable { +friend class CcuIdIter; + +protected: + CcuIdCell* entries; // the table itself + CcuIdCell* last; // its end + sword free; // index of first free entry + sword last_free; // index of end of free list + sword num_free; // number of free entries + + bool Grow (int); + +public: + CcuIdTable (int = 4); // initial size should be power of 2 *** 4 for testing + + lword Store (const void*, sword = 0); + bool Remove (lword); + const void* Get (lword, sword* = 0); + void Change (lword, const void*, sword = 0); + +}; + +class CcuIdIter { +protected: + CcuIdTable* idt; + CcuIdCell* entries; + CcuIdCell* cur; + + void Step (); + +public: + CcuIdIter (CcuIdTable& t) { idt = &t; cur = entries = t.entries; Step (); } + + const void* operator () () { Step (); return cur ? cur->obj : 0; } + const void* operator ++ () { Step (); return cur ? cur++->obj : 0; } + const void* Current () { return cur ? cur->obj : 0; } + sword CurType () { return cur ? cur->typ : 0; } + lword CurId () { return cur ? (cur -> chk << TID_SHIFT) | (cur - entries) : 0; } + + void Reset () { cur = entries = idt->entries; } +}; + +#endif /* IdTable_H_ */ + diff --git a/utils/Initializer.h b/utils/Initializer.h new file mode 100644 index 0000000..b4d772d --- /dev/null +++ b/utils/Initializer.h @@ -0,0 +1,29 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Initializers for classes + * + * $Id$ + * $CurLog$ + */ + + +#ifndef Initializer_H_ +#define Initializer_H_ + +#include "cplus_bugs.h" + +#ifndef CPLUS_BUG19 +template class CcuInitializerFor { +public: +inline CcuInitializerFor () { CLASS::ClassInit (); } +}; +#endif + +#endif /* Initializer_H_ */ + diff --git a/utils/List.cc b/utils/List.cc new file mode 100644 index 0000000..1bbfd8e --- /dev/null +++ b/utils/List.cc @@ -0,0 +1,724 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic lists (original ideas by Yves Berteaud) + * + * $Id$ + * $CurLog$ + */ + +#include "List.h" +#include "Allocator.h" +#include +#include + +/*?class CcuList + +\dessin{CcuList}{Internal structure of \typ{CcuList}s} + +?*/ + +#ifdef CPLUS_BUG20 +class CcuListLink { +static CcuAllocator* ListLinkMem; +static void ClassInit (); +public: + CcuListItem* Entry; + CcuListLink* Next; +inline CcuListLink (CcuListItem* e, CcuListLink* n = 0) { Entry = e; Next = n ? n : this; } + CcuListLink* Previous (); + void* operator new (unsigned int); + void operator delete (void*); +}; +#endif + + + +#ifdef CPLUS_BUG20 +CcuAllocator* CcuListLink::ListLinkMem = 0; +#else +CcuAllocator* CcuList::CcuListLink::ListLinkMem = 0; +#endif + +/*?nodoc?*/ +void* +#ifdef CPLUS_BUG20 +CcuListLink :: operator new (unsigned int) +#else +CcuList::CcuListLink :: operator new (unsigned int) +#endif +{ + if (!ListLinkMem) +#ifdef CPLUS_BUG20 + ListLinkMem = new CcuAllocator (sizeof (CcuListLink)); +#else + ListLinkMem = new CcuAllocator (sizeof (CcuList::CcuListLink)); +#endif + return ListLinkMem->Alloc (); +} + +/*?nodoc?*/ +void +#ifdef CPLUS_BUG20 +CcuListLink :: operator delete (void* that) +#else +CcuList::CcuListLink :: operator delete (void* that) +#endif +{ + ListLinkMem->Free (that); +} + + +/*? +Get the link whose next link is this one. +?*/ +#ifndef CPLUS_BUG20 +CcuList::CcuListLink* +CcuList::CcuListLink :: Previous () +#else +CcuListLink* +CcuListLink :: Previous () +#endif +{ +#ifndef CPLUS_BUG20 + register CcuList::CcuListLink* pl = this; +#else + register CcuListLink* pl = this; +#endif + while (pl->Next != this) + pl = pl->Next; + return pl; +} + +#ifdef DOC +/*? +Create an empty list. +?*/ +CcuList :: CcuList () +{ +} +#endif + +/*? +Create a list with one element \var{e}. +?*/ +CcuList :: CcuList (CcuListItem* e) +: LastLink (new CcuListLink (e)), + StatusFlag (NoError) +{ +} + +/*?nodoc?*/ +CcuList :: CcuList (const CcuList& l) +: LastLink (0), + StatusFlag (NoError) +{ + CcuListIter li (l); + while (++li) + Append (*li); +} + + +/*? +Destructor for lists. No operation is performed on the elements. +?*/ +CcuList :: ~CcuList () +{ + Clear (); +} + +/*? +Empty a list. +?*/ +void +CcuList :: Clear () +{ + CcuListLink* del = LastLink; + while (del) { + CcuListLink* next = del->Next; + if (next == LastLink) + next = 0; + delete del; + del = next; + } + LastLink = 0; +} + +/*?nodoc?*/ +CcuList& +CcuList :: operator = (const CcuList& l) +{ + if (this != &l) { + Clear (); + CcuListIter li (l); + while (++li) + Append (*li); + } + return *this; +} + + +/*?nextdoc?*/ +CcuListItem* +CcuList :: First () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return LastLink->Next->Entry; +} + +/*? +Return the first (resp. last) element in the list, or 0 if the list was empty. +The case of a null element can be distinguished from the case +when the list is empty with the function \fun{GetStatus}. +?*/ +CcuListItem* +CcuList :: Last () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return LastLink->Entry; +} + +/*? +Get the \var{n}-th element of a list. If \var{n} is greater than the length of the list +this function returns 0 and sets the status to \var{TooFar}. If \var{n} is negative, +this function returns 0 but sets the status to \var{NoError}. +?*/ +CcuListItem* +CcuList :: Nth (int n) +{ + StatusFlag = NoError; + if (n <= 0) + return 0; + CcuListIter li (*this); + while (n > 0 && ++li) + --n; + if (n != 0) + StatusFlag = TooFar; + return *li; +} + +/*? +Compute the number of elements in a list. +?*/ +int +CcuList :: Length () const +{ + int result = 0; + CcuListIter li (*this); + while (++li) + ++result; + return result; +} + +/*? +Check whether an item is present in a list. +?*/ +int +CcuList :: Find (CcuListItem* e) const +{ + CcuListIter li (*this); + while (++li) + if (*li == e) + return 1; + return 0; +} + +/*?nextdoc?*/ +void +CcuList :: Prepend (CcuListItem* e) +{ + if (LastLink) + /* remember that LastLink->Next is the first */ + LastLink->Next = new CcuListLink (e, LastLink->Next); + else + LastLink = new CcuListLink (e); +} + +/*? +Add an element at the beginning (resp. end) of a list. +?*/ +void +CcuList :: Append (CcuListItem* e) +{ + if (LastLink) { + LastLink = LastLink->Next = new CcuListLink (e, LastLink->Next); + } else + LastLink = new CcuListLink (e); +} + +/*? +Remove the first element of a list and return it. +?*/ +CcuListItem* +CcuList :: RemoveFirst () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + /* Get the first element and its data */ + CcuListLink* first = LastLink->Next; + CcuListItem* data = first->Entry; + /* Remove it from the chain */ + if (LastLink == first) + LastLink = 0; + else + LastLink->Next = first->Next; + /* delete it */ + delete first; + /* return its data */ + return data; +} + + +/*? +Remove the last element of a list and return it. This function has to locate the last +element, and hence has a linear cost. +?*/ +CcuListItem* +CcuList :: RemoveLast () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + /* Find the element that will be the new LastLink */ + register CcuListLink* newlast = LastLink->Previous (); + + /* Save the element to be deleted and its data */ + CcuListLink* del = LastLink; + CcuListItem* data = LastLink->Entry; + /* Remove it from the chain */ + if (newlast == LastLink) + LastLink = 0; + else { + newlast->Next = LastLink->Next; + LastLink = newlast; + } + /* delete it */ + delete del; + /* return its data */ + return data; +} + +/*? +Insert an element before the link \var{l}. This function has a linear cost. +?*/ +void +CcuList :: InsertBeforeLink (CcuListLink* l, CcuListItem* e) +{ + CcuListLink* prev = l->Previous (); + CcuListLink* newlink = new CcuListLink (e, l); + prev->Next = newlink; +} + + +/*? +Insert an element after the link \var{l}. +?*/ +void +CcuList :: InsertAfterLink (CcuListLink* l, CcuListItem* e) +{ + CcuListLink* newlink = new CcuListLink (e, l->Next); + l->Next = newlink; + if (LastLink == l) + LastLink = newlink; +} + +/*? +Remove the link which is after \var{l} and return its entry. If \var{l} is the last link of +the list, the first one is removed. +?*/ +CcuListItem* +CcuList :: RemoveAfterLink (CcuListLink* l) +{ + CcuListLink* del = l->Next; + CcuListItem* data = del->Entry; + if (del == l) { + LastLink = 0; + } else { + l->Next = del->Next; + if (LastLink == del) + LastLink = l; + } + delete del; + return data; +} + +/*? +Remove an element from a list. This function iterates through the list until it deletes +\var{num} appearances of \var{entry}. The actual number of removals is returned. +If \var{num} is \var{All} or is negative, all appearances of \var{entry} are deleted. +?*/ +int +CcuList :: Remove (CcuListItem* entry, int num) +{ + int removed = 0; + CcuListIter li (*this); + CcuListIter lj (*this); + while ((num < 0 || removed < num) && ++li) { + if (*li == entry) { + RemoveAfter (lj); + ++removed; + li = lj; + } else + ++lj; + } + return removed; +} + +/*? +Remove elements from a list. This function iterates through the list until it deletes +\var{num} elements for which the function \var{p} returns a non-null value. +The actual number of removals is returned. +If \var{num} is \var{All} or is negative, all matching elements are deleted. +?*/ +int +CcuList :: Remove (int (*p) (CcuListItem*), int num) +{ + int removed = 0; + CcuListIter li (*this); + CcuListIter lj (*this); + while ((num < 0 || removed < num) && ++li) { + if ((*p) (*li)) { + RemoveAfter (lj); + ++removed; + li = lj; + } else + ++lj; + } + return removed; +} + + +/*?nextdoc?*/ +void +CcuList :: InsertAfter (const CcuListIter& li, CcuListItem* e) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return; + } + StatusFlag = NoError; + if (!li.CurLink) { + if (li.StatusFlag == CcuListIter::StartOfList) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuList::InsertAfter\n"); + abort (); + } + } else if (li.StatusFlag == CcuListIter::EndOfList) { + Append (e); + } else { + InsertAfterLink (li.CurLink, e); + } +} + +/*? +Insert an element before (resp. after) the current position of the iterator \var{li}. +These functions are both equivalent to \fun{CcuList::Prepend} if the iterator is at the +beginning of the list (ie. before the first element). +\fun{InsertAfter} is performed in a constant time, while \fun{InsertBefore} +has a linear cost. +?*/ +void +CcuList :: InsertBefore (const CcuListIter& li, CcuListItem* e) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return; + } + StatusFlag = NoError; + if (!li.CurLink) { + if (li.StatusFlag == CcuListIter::StartOfList) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuList::InsertAfter\n"); + abort (); + } + } else if (li.StatusFlag == CcuListIter::EndOfList) { + Append (e); + } else { + InsertBeforeLink (li.CurLink, e); + } +} + +/*? +Remove the element after the current element of the iterator \var{li}. +If \var{li} points before the beginning of the list, the first element is returned. +If \var{li} points at the last element, the status flag is set to \var{TooFar}. +If the list is empty, the flag is set to \var{EmptyList}. In both cases, the +return value is null. +This function may be used +when one wants to iterate through a list and remove some elements: + CcuListIter li (l); + CcuListIter lj (l); + while (++li) + if (do_remove (*li)) { + RemoveAfter (lj); + li = lj; + } else + ++lj; +?*/ +CcuListItem* +CcuList :: RemoveAfter (const CcuListIter& li) +{ + if (li.TheList != this) { + StatusFlag = BadIterator; + return 0; + } + if (li.CurLink == LastLink) { + StatusFlag = LastLink ? TooFar : WasEmpty; + return 0; + } + StatusFlag = NoError; + if (li.CurLink) { + return RemoveAfterLink (li.CurLink); + } else { + return RemoveAfterLink (LastLink); + } +} + + +#ifdef DOC + +/*? +Initialize an iterator associated to the list \var{l}. That iterator will point at the beginning +of the list, {\em before} the first element. +?*/ +CcuListIter :: CcuListIter (CcuList& l) +{ +} + +/*? +Get the status of an iterator. The status may be one of \var{Normal, StartOfList}, or +\var{EndOfList} +?*/ +listiter_status +CcuListIter :: GetStatus () const +{ +} + +/*? +Reset an iterator to the beginning of the list. +?*/ +void +CcuListIter :: Reset () +{ +} + +#endif /* DOC */ + + +/*? +Get the current entry pointed by an iterator. This operator returns 0 if the iterator is +at the beginning or the end of the list. To distinguish those cases from the +case when the entry is null, you can use the method \fun{GetStatus}. +?*/ +CcuListItem* +CcuListIter :: operator * () const +{ + return (CurLink && StatusFlag == Normal) ? CurLink->Entry : 0; +} + +#ifdef DOC +/*? +Check whether the status of an iterator is \var{Normal}. +?*/ +CcuListIter :: operator int () const +{ +} +#endif /* DOC */ + + +/*? +Take one step of iteration. +?*/ +CcuListIter& +CcuListIter :: operator ++ () +{ + /* This test covers all the cases : + - the iteration has already begun, and is at its end. + - the iteration has not begun, but the list is empty. + */ + if (CurLink == TheList->LastLink) { + StatusFlag = EndOfList; + } else { + CurLink = CurLink ? CurLink->Next : TheList->LastLink->Next; + StatusFlag = Normal; + } + return *this; +} + +#ifndef CPLUS_BUG16 +/*? +Post-increment equivalent of the previous operator. This operator is just here +as a demonstrator: it was not tested because no known compiler implements that feature, +and its semantics is quite muddy. +?*/ +CcuListIter& +CcuListIter :: operator ++ (int) +{ + ++(*this); + return *this; +} +#endif + +/*? +Try and find the element \var{e} in the list, starting from the +current position of the iterator (this position not included). +If \var{e} is present in the list, the iterator will +be correctly positionned. If not, it will have reached the end of the list. +?*/ +int +CcuListIter :: Find (CcuListItem* e) +{ + while (++(*this)) + if (**this == e) + return 1; + return 0; +} + +#ifdef DOC + +/*?class CcuListOf +The generic classes \typ{CcuListOf} and \typ{CcuListIterOf} are derived classes +of \typ{CcuList} and \typ{CcuListIter} that provide lists of pointers to class objects. +When parameterized by the class \typ{ITEM}, the following functions are redefined: +?*/ + +/*?nextdoc?*/ +CcuListOf :: CcuListOf (ITEM* it) +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListOf :: First () +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListOf :: Last () +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListOf :: Nth (int n) +{ +} + +/*?nextdoc?*/ +int +CcuListOf :: Find (ITEM* it) const +{ +} + +/*?nextdoc?*/ +void +CcuListOf :: Append (ITEM* it) +{ +} + +/*?nextdoc?*/ +void +CcuListOf :: Prepend (ITEM* it) +{ +} + +/*?nextdoc?*/ +CcuListOf& +CcuListOf :: operator << (ITEM* it) +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListOf :: RemoveFirst () +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListOf :: RemoveLast () +{ +} + +/*?nextdoc?*/ +int +CcuListOf :: Remove (ITEM* it, int nb = 1) +{ +} + +/*?nextdoc?*/ +int +CcuListOf :: Remove (int (*p) (ITEM*), int nb = 1) +{ +} + +/*?nextdoc?*/ +void +CcuListOf :: InsertAfter (const CcuListIterOf & li, ITEM*it) +{ +} + +/*? +These functions are equivalent to their homonyms in the class \typ{CcuList}, +except that they are customized in order to manipulate pointers to \typ{ITEM} +instead of \typ{void*}. +?*/ +void +CcuListOf :: InsertBefore (const CcuListIterOf & li, ITEM* it) +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListOf :: RemoveAfter (const CcuListIterOf & li) +{ +} + +/*?nextdoc?*/ +CcuListIterOf :: CcuListIterOf (const CcuListOf & l) +{ +} + +/*?nextdoc?*/ +ITEM* +CcuListIterOf :: operator * () const +{ +} + +/*? +These functions are equivalent to their homonyms in the class \typ{CcuListIter}, +except that they are customized in order to manipulate pointers to \typ{ITEM} +instead of \typ{void*}. +?*/ +int +CcuListIterOf :: Find (ITEM* it) +{ +} + + +#endif /* DOC */ diff --git a/utils/List.h b/utils/List.h new file mode 100644 index 0000000..9e61c9e --- /dev/null +++ b/utils/List.h @@ -0,0 +1,192 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic lists (original ideas by Yves Berteaud) + * + * $Id$ + * $CurLog$ + */ + +#ifndef List_H_ +#define List_H_ + +#include "cplus_bugs.h" + +class CcuAllocator; + +typedef void CcuListItem; + +#ifdef CPLUS_BUG20 +class CcuListLink; +#endif + +class CcuList { +friend class CcuListIter; + +#ifndef CPLUS_BUG20 + class CcuListLink { + static CcuAllocator* ListLinkMem; + public: + CcuListItem* Entry; + CcuListLink* Next; + inline CcuListLink (CcuListItem* e, CcuListLink* n = 0) { Entry = e; Next = n ? n : this; } + CcuListLink* Previous (); + void* operator new (unsigned int); + void operator delete (void*); + }; +#endif + +public: + enum list_status { NoError, WasEmpty, TooEarly, TooFar, BadIterator }; + enum list_remove { All = -1 }; + +private: + + CcuListLink* LastLink; + list_status StatusFlag; + + void InsertAfterLink (CcuListLink*, CcuListItem*); + void InsertBeforeLink (CcuListLink*, CcuListItem*); + CcuListItem* RemoveAfterLink (CcuListLink*); + +public: +inline CcuList () : LastLink (0), StatusFlag (NoError) { } + CcuList (CcuListItem*); + CcuList (const CcuList&); + ~CcuList (); + CcuList& operator = (const CcuList&); +inline list_status GetStatus () const { return StatusFlag; } + +inline int IsEmpty () const { return !LastLink; } + CcuListItem* First (); + CcuListItem* Last (); + CcuListItem* Nth (int n); + int Length () const; + int Find (CcuListItem*) const; + + void Append (CcuListItem*); + void Prepend (CcuListItem*); +inline CcuList& operator << (CcuListItem* it) { Append (it); return *this; } + + CcuListItem* RemoveFirst (); + CcuListItem* RemoveLast (); + int Remove (CcuListItem*, int = 1); + int Remove (int (*) (CcuListItem*), int = 1); + void Clear (); + + void InsertAfter (const CcuListIter&, CcuListItem*); + void InsertBefore (const CcuListIter&, CcuListItem*); + CcuListItem* RemoveAfter (const CcuListIter&); +}; + +class CcuListIter { +friend class CcuList; + +public: + enum listiter_status { Normal, StartOfList, EndOfList }; + +private: + const CcuList* TheList; +#ifdef CPLUS_BUG20 + CcuListLink* CurLink; +#else + CcuList::CcuListLink* CurLink; +#endif + listiter_status StatusFlag; + +public: +inline CcuListIter (const CcuList& l) : TheList (&l), CurLink (0), StatusFlag (StartOfList) { } +inline void Reset () { CurLink = 0; StatusFlag = StartOfList; } +inline CcuListIter& operator = (const CcuList& l) { TheList = &l; CurLink = 0; StatusFlag = StartOfList; return *this; } +inline CcuListIter& operator = (const CcuListIter& li) { TheList = li.TheList; CurLink = li.CurLink; StatusFlag = li.StatusFlag; return *this; } + CcuListIter& operator ++ (); +#ifndef CPLUS_BUG16 + CcuListIter& operator ++ (int); +#endif + int Find (CcuListItem*); + CcuListItem* operator * () const; +inline listiter_status GetStatus () const { return StatusFlag; } +inline operator int () const { return StatusFlag == Normal; } +}; + + +#ifndef CPLUS_BUG19 +template class CcuListIterOf; + +template class CcuListOf : public CcuList { +public: +inline CcuListOf () : CcuList () {} +inline CcuListOf (ITEM* it) : CcuList (it) {} +inline ITEM* First () { return (ITEM*) (CcuList::First ()); } +inline ITEM* Last () { return (ITEM*) (CcuList::Last ()); } +inline ITEM* Nth (int n) { return (ITEM*) (CcuList::Nth (n)); } +inline int Find (ITEM* it) const { return CcuList::Find (it); } + +inline void Append (ITEM* it) { CcuList::Append (it); } +inline void Prepend (ITEM* it) { CcuList::Prepend (it); } +inline CcuListOf& operator << (ITEM* it) { CcuList::Append (it); return *this; } + +inline ITEM* RemoveFirst () { return (ITEM*) (CcuList::RemoveFirst ()); } +inline ITEM* RemoveLast () { return (ITEM*) (CcuList::RemoveLast ()); } +inline int Remove (ITEM* it, int nb = 1) { return CcuList::Remove (it, nb); } +inline int Remove (int (*p) (ITEM*), int nb = 1) { return CcuList::Remove ((int (*) (ITEM*)) p, nb); } + +inline void InsertAfter (const CcuListIterOf & li, ITEM*it) { CcuList::InsertAfter (li, it); } +inline void InsertBefore (const CcuListIterOf & li, ITEM* it) { CcuList::InsertBefore (li, it); } +inline ITEM* RemoveAfter (const CcuListIterOf & li) { return (ITEM*) CcuList::RemoveAfter (li); } +}; + +template class CcuListIterOf : public CcuListIter { +public: +inline CcuListIterOf (const CcuListOf & l) : CcuListIter (l) { } +inline CcuListIterOf& operator = (const CcuListOf & l) { return (CcuListIterOf&) CcuListIter::operator = (l); } +inline CcuListIterOf& operator = (const CcuListIterOf& li) { return (CcuListIterOf&) CcuListIter::operator = (li); } +inline ITEM* operator * () const { return (ITEM*) CcuListIter::operator * (); } +inline int Find (ITEM* it) { return CcuListIter::Find (it); } +}; +#endif /* CPLUS_BUG19 */ + + + +typedef CcuListItem CcuStackItem; + +/* CPLUS_BUG10 */ +class CcuStack : _private CcuList { +public: + CcuList :: Clear; + CcuList :: IsEmpty; + CcuList :: GetStatus; +inline void Push (CcuStackItem* p) { Prepend (p); } +inline CcuStackItem* Pop () { return RemoveFirst (); } +inline CcuStackItem* Top () { return First (); } +}; + +typedef CcuListItem CcuQueueItem; + +/* CPLUS_BUG10 */ +class CcuQueue : _private CcuList { +public: + CcuList :: Clear; + CcuList :: IsEmpty; + CcuList :: GetStatus; +inline void Put (CcuQueueItem* p) { Append (p); } +inline CcuQueueItem* Get () { return RemoveFirst (); } +inline operator const CcuList& () { return *this; } +}; + +#ifndef CPLUS_BUG19 +template class CcuQueueOf : public CcuQueue { +public: +inline void Put (ITEM* p) { CcuQueue::Put (p); } +inline ITEM* Get () { return (ITEM*) CcuQueue::Get (); } +inline operator const CcuListOf & () { return *this; } +}; +#endif /* CPLUS_BUG19 */ + +#endif /* List_H_ */ + diff --git a/utils/RegExp.cc b/utils/RegExp.cc new file mode 100644 index 0000000..4fdc030 --- /dev/null +++ b/utils/RegExp.cc @@ -0,0 +1,163 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Regular expressions + * + * $Id$ + * $CurLog$ + */ + +#include "RegExp.h" + +/*?class CcuRegExp +The class \typ{CcuRegExp} was designed to encapsulate regular expression management, +implemented by \fun{re_comp} and \fun{re_exec}, or \fun{regcmp} and \fun{regex}, +depending on the operating system. The standard usage consists in initializing +a \typ{CcuRegExp}, then compiling it, and finally match strings against it. +?*/ + +#ifdef DOC +/*? +Initialize a \typ{CcuRegExp} with expression \var{expr}. The string \var{epxr} +is {\em not} copied. +?*/ +CcuRegExp :: CcuRegExp (const char* expr) +{ +} +#endif + + +#ifdef REGCOMP +#include +#include +#include + +/*? +Compile a regular expression before using it. This function returns FALSE upon failure, +TRUE upon success. +?*/ +bool +CcuRegExp :: Compile () +{ + struct regex_t tmp; + if (regcomp (&tmp, String, REG_NOSUB) == 0) { + Compiled = malloc (sizeof (struct regex_t)); + memcpy (&Compiled, &tmp, sizeof (struct regex_t)); + return TRUE; + } else + return FALSE; +} + +/*? +Match a string against a regular expression. This function returns FALSE upon failure, +TRUE upon success. +?*/ +bool +CcuRegExp :: Match (const char* s) +{ + if (Compiled) + return regexec ((struct regex_t*) Compiled, s, 0, 0, 0) ? TRUE : FALSE; + else + return FALSE; +} + +/*?nodoc?*/ +CcuRegExp :: ~CcuRegExp () +{ + if (Compiled) { + regfree ((struct regex_t*) Compiled); + free (Compiled); + } +} + +#endif + + +#ifdef RE_COMP + +extern "C" { + char* re_comp (const char*); + int re_exec (const char*); +} +/* should be #include , but not available everywhere ... */ + + +CcuRegExp* CcuRegExp::Compiled = 0; + +/*?nodoc?*/ +bool +CcuRegExp :: Compile () +{ + if (re_comp (String) != 0) { + Compiled = 0; + return FALSE; + } else { + Compiled = this; + return TRUE; + } +} + +/*?nodoc?*/ +bool +CcuRegExp :: Match (const char* s) +{ + if (Compiled != this) + if (!Compile ()) + return FALSE; + if (re_exec (s) == 1) + return TRUE; + else + return FALSE; +} + +#endif /* RE_COMP */ + +#if !defined(REGCOMP) && !defined(RE_COMP) + +#include +#include +#ifdef __GNUG__ +extern "C" { + char* regcmp (const char * ...); + char* regex (const char *, const char * ...); +} +#endif + +/*? +Compile a regular expression before using it. This function returns FALSE upon failure, +TRUE upon success. +?*/ +bool +CcuRegExp :: Compile () +{ + Compiled = regcmp (String, 0); + return Compiled ? TRUE : FALSE; +} + +/*? +Match a string against a regular expression. This function returns FALSE upon failure, +TRUE upon success. +?*/ +bool +CcuRegExp :: Match (const char* s) +{ + if (Compiled) + return regex (Compiled, s) ? TRUE : FALSE; + else + return FALSE; +} + +/*?nodoc?*/ +CcuRegExp :: ~CcuRegExp () +{ + if (Compiled) + free (Compiled); +} + +#endif /* !REGCOMP && !RE_COMP */ diff --git a/utils/RegExp.h b/utils/RegExp.h new file mode 100644 index 0000000..c46431c --- /dev/null +++ b/utils/RegExp.h @@ -0,0 +1,81 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Regular expressions + * + * $Id$ + * $CurLog$ + */ + +#ifndef RegExp_H_ +#define RegExp_H_ + +#include "cplus_bugs.h" +#include "bool.h" + +#ifdef __hpux +#define REGCOMP +#else +#define RE_COMP +#endif + +#ifdef REGCOMP + +/* POSIX version of regular expressions */ + +class CcuRegExp { +private: + const char* String; + void* Compiled; +public: +inline CcuRegExp (const char* s) : String (s), Compiled (0) {} + ~CcuRegExp (); + bool Compile (); + bool Match (const char*); +inline const char* GetExpr () {return String;} +}; + +#endif /* REGCOMP */ + +#ifdef RE_COMP + +class CcuRegExp { +private: + const char* String; +static CcuRegExp* Compiled; + +public: +inline CcuRegExp (const char* s) : String (s) {} +inline ~CcuRegExp () {}; + bool Compile (); + bool Match (const char*); +inline const char* GetExpr () {return String;} +}; + +#endif /* RE_COMP */ + +#if !defined(REGCOMP) && !defined(RE_COMP) + +class CcuRegExp { +private: + const char* String; + char* Compiled; + +public: +inline CcuRegExp (const char* s) : String (s), Compiled (0) {} + ~CcuRegExp (); + bool Compile (); + bool Match (const char*); +inline const char* GetExpr () { return String; } +}; + +#endif /* !REGCOMP && !RE_COMP */ + +#endif /* RegExp_H_ */ + diff --git a/utils/Signal.cc b/utils/Signal.cc new file mode 100644 index 0000000..ceb178b --- /dev/null +++ b/utils/Signal.cc @@ -0,0 +1,312 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Signal handling + * + * $Id$ + * $CurLog$ + */ + +#include "Signal.h" +#include "List.h" +#ifdef sun +/* This should come from , but no available C++ headers on Suns know about POSIX */ +extern "C" { + typedef int sigset_t; + struct sigaction { + void (*sa_handler)(...); + sigset_t sa_mask; + int sa_flags; + }; + +# define NSIG 32 +# define SIGHUP 1 +# define SIGINT 2 +# define SIGQUIT 3 +# define SIGILL 4 +# define SIGTRAP 5 +# define SIGIOT 6 +# define SIGABRT 6 +# define SIGEMT 7 +# define SIGFPE 8 +# define SIGKILL 9 +# define SIGBUS 10 +# define SIGSEGV 11 +# define SIGSYS 12 +# define SIGPIPE 13 +# define SIGALRM 14 +# define SIGTERM 15 +# define SIGURG 16 +# define SIGSTOP 17 +# define SIGTSTP 18 +# define SIGCONT 19 +# define SIGCHLD 20 +# define SIGCLD 20 +# define SIGTTIN 21 +# define SIGTTOU 22 +# define SIGIO 23 +# define SIGPOLL SIGIO +# define SIGXCPU 24 +# define SIGXFSZ 25 +# define SIGVTALRM 26 +# define SIGPROF 27 +# define SIGWINCH 28 +# define SIGLOST 29 +# define SIGUSR1 30 +# define SIGUSR2 31 + +# define SIG_DFL 0 +# define SIG_BLOCK 0x0001 +# define SIG_UNBLOCK 0x0002 +# define SIG_SETMASK 0x0004 + int sigaction (int, const struct sigaction*, struct sigaction*); + int sigemptyset (sigset_t*); + int sigfillset (sigset_t*); + int sigaddset (sigset_t*, int); + int sigprocmask (int, const sigset_t*, sigset_t*); +} +#else +#include +#endif + + +/*?class CcuBaseSignalHandler +The class \typ{CcuBaseSignalHandler} is provided as a base class for signal handlers. +It comes with a derived class \typ{CcuSignalHandler} that can be used as is, without +any derivation. +A signal handler is created for a specific signal, identified by a numeric value. +The following constants are defined: \var{AllSigs, SigHup, SigInt, SigQuit, SigIll, SigTrap, +SigAbrt, SigEmt, SigFpe, SigKill, SigBus, SigSegv, SigSys, SigPipe, SigAlrm, SigTerm, SigUsr1, +SigUsr2, SigChld, SigVtalrm, SigIo, SigStop, SigTstp, SigCont, SigTtin, SigTtou, SigUrg,} +and \var{SigLost}. The value \var{AllSigs} is not meaningful to signal handlers. + +When a signal is received by the program and a signal handler was created for that +signal, its method \fun{Handle} is called. This method should be redefined in derived +classes of \var{CcuBaseSignalHandler}. + +Several signal handlers can be created for the same signal. However, only one is +active at a time. A stack of signal handlers is maintained for every signal, so that +the latest created signal handler is the active one, until its destruction. At that time, +the previous signal handler, if there was one, is activated again. +?*/ + +const int NumSigs = NSIG-1; + +const int AllSigs = -1; +const int SigHup = SIGHUP; +const int SigInt = SIGINT; +const int SigQuit = SIGQUIT; +const int SigIll = SIGILL; +const int SigTrap = SIGTRAP; +const int SigAbrt = SIGABRT; +const int SigEmt = SIGEMT; +const int SigFpe = SIGFPE; +const int SigKill = SIGKILL; +const int SigBus = SIGBUS; +const int SigSegv = SIGSEGV; +const int SigSys = SIGSYS; +const int SigPipe = SIGPIPE; +const int SigAlrm = SIGALRM; +const int SigTerm = SIGTERM; +const int SigUsr1 = SIGUSR1; +const int SigUsr2 = SIGUSR2; +const int SigChld = SIGCHLD; +const int SigVtalrm = SIGVTALRM; +const int SigIo = SIGIO; +const int SigStop = SIGSTOP; +const int SigTstp = SIGTSTP; +const int SigCont = SIGCONT; +const int SigTtin = SIGTTIN; +const int SigTtou = SIGTTOU; +const int SigUrg = SIGURG; +const int SigLost = SIGLOST; + + +CcuList* CcuBaseSignalHandler::HandlerStacks = 0; + +/*?hidden?*/ +void +CcuBaseSignalHandler :: ClassInit () +{ + HandlerStacks = new CcuList [NumSigs]; +} + +/*? +Create a signal handler for the signal \var{sig}. +?*/ +CcuBaseSignalHandler :: CcuBaseSignalHandler (int sig) +: Signal (sig) +{ + CcuSignalBlocker b (sig); + if (!HandlerStacks) + ClassInit (); + HandlerStacks [Signal-1].Prepend (this); + Install (); +} + +/*?nodoc?*/ +CcuBaseSignalHandler :: ~CcuBaseSignalHandler () +{ + CcuSignalBlocker b (Signal); + CcuList& stack = HandlerStacks [Signal-1]; + if (stack.First () == this) { + stack.RemoveFirst (); + if (stack.IsEmpty ()) + InstallNone (Signal); + else + ((CcuBaseSignalHandler*) stack.First ())->Install (); + } else + stack.Remove (this, 1); +} + +/*?hidden?*/ +void +CcuBaseSignalHandler :: Install () +{ + struct sigaction act; + act.sa_handler = (void(*)(...)) DoHandle; + sigemptyset (&act.sa_mask); + act.sa_flags = 0; + sigaction (Signal, &act, 0); +} + +/*?hidden?*/ +void +CcuBaseSignalHandler :: InstallNone (int sig) +{ + struct sigaction act; + act.sa_handler = SIG_DFL; + sigemptyset (&act.sa_mask); + act.sa_flags = 0; + sigaction (sig, &act, 0); +} + +/*?hidden?*/ +void +CcuBaseSignalHandler :: DoHandle (int sig) +{ + CcuBaseSignalHandler* s = (CcuBaseSignalHandler*) HandlerStacks [sig-1].First (); + if (s) + s->Handle (); +} + +/*? +This virtual function should be redefined in derived classes. It is called +when this handler is the currently active one and a signal is received. +?*/ +void +CcuBaseSignalHandler :: Handle () +{ +} + +/*?class CcuSignalHandler +The class \typ{CcuSignalHandler} is a derived class of \typ{CcuBaseSignalHandler} that +can be used without deriving a new class. +Each \typ{CcuSignalHandler} holds a pointer to a function which is called when a +signal is received. This function, which is passed to the constructor, must +take an \typ{int} argument and return \typ{void}. +?*/ + +/*? +Create a signal handler for signal \var{sig}. The function \var{handler} will be +called when a signal is received. +?*/ +CcuSignalHandler :: CcuSignalHandler (int sig, void (*handler) (int)) +: CcuBaseSignalHandler (sig), + Handler (handler) +{ +} + +/*?nodoc?*/ +CcuSignalHandler :: ~CcuSignalHandler () +{ +} + +/*?nodoc?*/ +void +CcuSignalHandler :: Handle () +{ + (*Handler) (Signal); +} + +/*?class CcuSignalBlocker +The class \typ{CcuSignalBlocker} provides protection against signals. +When a \typ{CcuSignalBlocker} is created for a signal type, the program will +be protected against such signals during the lifetime of the signal blocker. +Signal blockers are often used as follows: +\begin{ccode} + void + sensitive_function () + { + CcuSignalBlocker b (SigAlrm); // protect this function against alarms + ... + } +\end{ccode} + +Some signals, such as \var{SIGKILL}, actually cannot be blocked. Creating +a signal blocker for such a signal is ineffective. +Please note that signal numbers currently cannot be combined. If you wish +to protect a function against two signals, you must create two signal blockers. +However, the special value \var{AllSigs} allows the creation of signal blockers +that protect against all kinds of signals. +?*/ + +int CcuSignalBlocker::BlockCounts [NumSigs]; + + +/*? +Create a signal blocker for the signal \var{sig}. If \var{sig} is \var{AllSigs}, +all signals will be blocked. +?*/ +CcuSignalBlocker :: CcuSignalBlocker (int sig) +: Signal (sig) +{ + int all = sig < 1 || sig > NumSigs; + sigset_t set; + if (all) { + sigfillset (&set); + } else { + sigemptyset (&set); + sigaddset (&set, Signal); + } + + /* inhibit interrupts before registering inhibitions */ + sigprocmask (SIG_BLOCK, &set, 0); + + if (all) { + for (int s = 0; s < NumSigs; s++) + BlockCounts [s]++; + } else { + BlockCounts [Signal-1]++; + } +} + +/*?nodoc?*/ +CcuSignalBlocker :: ~CcuSignalBlocker () +{ + int all = Signal < 1 || Signal > NumSigs; + int change = 0; + sigset_t set; + sigemptyset (&set); + + if (all) { + for (int s = 0; s < NumSigs; s++) { + if (!--BlockCounts [s]) { + sigaddset (&set, s+1); + change = 1; + } + } + } else if (!--BlockCounts [Signal-1]) { + sigaddset (&set, Signal); + change = 1; + } + + if (change) + sigprocmask (SIG_UNBLOCK, &set, 0); +} + diff --git a/utils/Signal.h b/utils/Signal.h new file mode 100644 index 0000000..c51b070 --- /dev/null +++ b/utils/Signal.h @@ -0,0 +1,79 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * Signal handling + * + * $Id$ + * $CurLog$ + */ + +#ifndef Signal_H_ +#define Signal_H_ + +#include "cplus_bugs.h" +class CcuList; + +#ifdef CPLUS_BUG21 +#ifdef sun +#define NSIG 32 +#else +#include +#endif +#endif + +class CcuBaseSignalHandler { +private: +static CcuList* HandlerStacks; +static void ClassInit (); + void Install (); +static void InstallNone (int); +static void DoHandle (int); + +public: + CcuBaseSignalHandler (int); +virtual ~CcuBaseSignalHandler (); + +protected: + int Signal; +/*?public?*/ +virtual void Handle (); + +}; + +extern const int AllSigs, SigHup, SigInt, SigQuit, SigIll, SigTrap, SigAbrt, SigEmt, SigFpe, + SigKill, SigBus, SigSegv, SigSys, SigPipe, SigAlrm, SigTerm, SigUsr1, + SigUsr2, SigChld, SigVtalrm, SigIo, SigStop, + SigTstp, SigCont, SigTtin, SigTtou, SigUrg, SigLost; + +class CcuSignalHandler : public CcuBaseSignalHandler { +protected: + void (*Handler) (int); + void Handle (); + +public: + CcuSignalHandler (int, void (*) (int)); + ~CcuSignalHandler (); +}; + + +class CcuSignalBlocker { +private: +#ifndef CPLUS_BUG21 +static int BlockCounts []; +#else +static int BlockCounts [NSIG-1]; +#endif +protected: + int Signal:6; +public: + CcuSignalBlocker (int); + ~CcuSignalBlocker (); +}; + +#endif /* Signal_H_ */ + diff --git a/utils/SmartPointer.cc b/utils/SmartPointer.cc new file mode 100644 index 0000000..264a7e1 --- /dev/null +++ b/utils/SmartPointer.cc @@ -0,0 +1,245 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1990, 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * smart pointers, originally by Michel Beaudouin-Lafon + * + * $Id$ + * $CurLog$ + */ + +#include +#include + +#include "SmartPointer.h" + +CcuSmartData::check_type CcuSmartData::check = Warn; +int CcuSmartData::NextCreatedIsDynamic = 0; + +/*?class CcuSmartData +The class \typ{CcuSmartData} is the base class for objects that you want to reference through smart pointers. +Such an object contains a reference count. +This reference count contains the number of smart pointers to this object. +When that number reaches 0 and the object was allocated dynamically, it is safe to destroy it +(unless there are still plain pointers to it!). +Hence, a \typ{CcuSmartData} destroys itself when its reference count reaches 0 +and it was allocated dynamically (ie. with \fun{operator new}). + +To implement the reference counting properly, it is necessary to overload the assignment operator on +the reference count, so that when object \var{a} is assigned to object \var{b}, +the reference count of \var{b} does not change. +This means that all classes deriving from \typ{CcuSmartData} will have their assignment operator implicitly redefined. +This implies a small run-time overhead, and a special care if you need to overload this operator +in a derived class of \typ{CcuSmartData}. + +Another point needs special attention. The only way of deciding whether an object was dynamically +allocated is to redefine \fun{operator new}. This was done in \typ{CcuSmartData}. However, you might +want to define your own \fun{new} and \fun{delete} in derived classes. If you do so, you +should take care that \fun{new} sets the flag \var{CcuSmartData::NextCreatedIsDynamic} to a non-null value. +?*/ + +void* +CcuSmartData :: operator new (unsigned size) +{ + NextCreatedIsDynamic = 1; + return ::operator new (size); +} + +/*? +Create a data, ie. initialize its reference count to 0. +?*/ +CcuSmartData :: CcuSmartData () +: State (NextCreatedIsDynamic ? 0 : 1) +{ + NextCreatedIsDynamic = 0; +} + +/*? +This is the copy constructor for the class \typ{CcuSmartData}. +Because there is a copy constructor defined, +all derived class will have a copy constructor defined implicitly, +unless you specify one explicitely. +?*/ +CcuSmartData :: CcuSmartData (const CcuSmartData&) +: State (NextCreatedIsDynamic ? 0 : 1) +{ + NextCreatedIsDynamic = 0; +} + +/*? +This is the destructor for class \typ{CcuSmartData}. It is {\em virtual}. +This destructor checks that the deleted object has a null reference count. +If not, it notifies the user according to the sanity check value defined with +the static member function \fun{SetCheck}. +Dynamically allocated \typ{CcuSmartData} objects are automatically deleted by the smart pointer package +when their reference count reaches zero. +?*/ +CcuSmartData :: ~CcuSmartData () +{ + if (State > 1) { + if (check >= OnlyDynamic) { + if (IsDynamic ()) + fprintf (stderr, "*** ~CcuSmartData (0x%x) : ref count of dynamic object is %d !\n", this, int (State/2)); + else if (check >= Warn) + fprintf (stderr, "*** ~CcuSmartData (0x%x) : ref count of global or automatic object is %d !\n", this, int (State/2)); + } + if (check == Abort) { + fprintf (stderr, "*** aborting\n"); + abort (); + } + } +} + + +void +CcuSmartData :: DecrRef () +{ + if (----State == 0) + delete this; +} + +#ifdef DOC +/*? +This protected member returns 1 if this object was allocated with \fun{operator new}. +?*/ +int +CcuSmartData :: IsDynamic () const +{ +} +#endif + + +/*? +This {\em static} member controls the sanity check done by the destructor of class \typ{CcuSmartData}: +a \typ{CcuSmartData} should not be destroyed when its refcount is non zero, because this means +that some smart pointers are still pointing at it. +Such errors can happen in two situations:\\ + \hspace*{0.5cm}1. when calling explicitely \fun{operator delete} on an object that has smart pointers to it;\\ + \hspace*{0.5cm}2. when a local object (an object on the stack) that has smart pointers to it is automatically +destroyed upon exit of its enclosing block.\\ +\vspace{0.5ex} +When an error occurs, the value of \var{chk} defines what happens, as follows:\\ + \hspace*{0.5cm}$\bullet$ if \var{t} is \var{Warn}, a message is issued on \var{stderr} and processing continues;\\ + \hspace*{0.5cm}$\bullet$ if \var{t} is \var{Abort}, a message is issued and and \fun{abort} is called, forcing a core dump;\\ +but not for dynamically allocated objects.\\ + \hspace*{0.5cm}$\bullet$ if \var{t} is \var{OnlyDynamic}, checking is disabled for global and automatic objects, + \hspace*{0.5cm}$\bullet$ if \var{t} is \var{NoCheck}, checking is disabled.\\ +\fun{SetCheck} returns the previous value of the checking status. +The initial value is 0 (warning message). +?*/ +CcuSmartData::check_type +CcuSmartData :: SetCheck (check_type t) +{ + check_type old = check; + check = t; + return old; +} + +/*?class CcuSmartPointerTo +The class \typ{CcuSmartPointerTo} is the smart pointer class itself. +A \typ{CcuSmartPointerTo} object contains a pointer to a \typ{DATA} object. +?*/ + +#ifdef DOC + +/*? +Construct a null smart pointer. +?*/ +CcuSmartPointerTo :: CcuSmartPointerTo () +{ +} + +/*? +Construct a smart pointer to data \var{d}. +\var{d} may be 0. +?*/ +CcuSmartPointerTo :: CcuSmartPointerTo (DATA* d) +{ +} + +/*? +This is the copy constructor for smart pointers. +It ensures that the reference counts are properly updated when a smart pointer +is initialized by copy (argument passing and function return for instance). +?*/ +CcuSmartPointerTo :: CcuSmartPointerTo (const CcuSmartPointerTo& p) +{ +} + +/*? +The destructor updates the reference count of the pointed to data, +and destroys it if the reference count reaches 0 and the data was dynamically allocated. +?*/ +CcuSmartPointerTo :: ~CcuSmartPointerTo () +{ +} + +/*? +This operator overloads the assignment of smart pointers. +It can destroy the data pointed by the left-hand side pointer if its reference count reaches 0. +?*/ +CcuSmartPointerTo& +CcuSmartPointerTo :: operator = (const DATA* d) +{ +} + +/*? +This operator overloads the dereferencing of smart pointers. +Unfortunately, it returns a \typ{DATA*} where one would prefer a pointer to a derived class of \typ{DATA}. +This problem, which occurs also with the overloading operators below, +is fixed by the generic pointer class (\fun{PointerClass}) described below. +?*/ +DATA* +CcuSmartPointerTo :: operator -> () +{ +} + +/*? +These conversion operators make it possible to pass a pointer to data where a smart pointer is expected. +They also make it possible to test a smart pointer like a usual pointer. +?*/ +CcuSmartPointerTo :: operator DATA* () +{ +} + +// note: this is hacked up for the doc stuff +/*? +This is a macro to generate a smart pointer class. +\typ{SmartClass} is the name of the class to generate, +and \typ{DataClass} is the name of the class to which \typ{SmartClass} objects will point. +\typ{DataClass} must derive from \typ{DATA}. +The generated class is similar to the class \typ{CcuSmartPointerTo} described above, +with \typ{CcuSmartPointerTo} replaced by \typ{SmartClass} and \typ{DATA} replaced by \typ{DataClass}. +In particular, this means that such smart pointers can be dereferenced with the \fun{operator ->} +like usual pointers. +?*/ +generic +PointerClass (SmartClass, DataClass) +{ +} + +/*? +This macro is similar to \fun{PointerClass} described above. +It generates a smart pointer class named \typ{SmartClass} +for the class \typ{DataClass}. +Unlike the previous macro, the generated class is not a base class, +but instead a derived class of \typ{SmartBaseClass}, +which must be a smart pointer class itself. +If \typ{pA} is a smart pointer class to class \typ{A} and \typ{B} derives from \typ{A}, +you can declare a smart pointer class \typ{pB} to the class \typ{B} with:\\ +\hspace*{1cm}\com{DerivedPointerClass (pB, pA, A)}\\ +Then \typ{pB} objects can be used where \typ{pA} objects are expected, +which would not be the case if \typ{pB} was declared with \fun{PointerClass}. +?*/ +generic +DerivedPointerClass (SmartClass, BaseSmartClass, DataClass) +{ +} + +#endif + diff --git a/utils/SmartPointer.h b/utils/SmartPointer.h new file mode 100644 index 0000000..90d1180 --- /dev/null +++ b/utils/SmartPointer.h @@ -0,0 +1,117 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1990, 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * smart pointers, originally by Michel Beaudouin-Lafon + * + * $Id$ + * $CurLog$ + */ + +#ifndef SmartPointer_H_ +#define SmartPointer_H_ + +#include "cplus_bugs.h" + +class CcuSmartData { +public: + enum check_type { NoCheck, OnlyDynamic, Warn, Abort }; +private: +static check_type check; + + + int State; +inline int IsDynamic () const { return !(State & 1); } + +protected: +static int NextCreatedIsDynamic; + +public: + void* operator new (unsigned); +inline void operator delete (void* that) { ::delete (that); } + + CcuSmartData (); + CcuSmartData (const CcuSmartData&); +virtual ~CcuSmartData (); + +static check_type SetCheck (check_type); + + void DecrRef (); +inline void IncrRef () { State += 2; } +}; + +#ifndef CPLUS_BUG19 +template class CcuSmartPointerTo { +protected: + DATA* Data; +inline void DecrDataRef () const { if (Data) Data->DecrRef (); } +inline void IncrDataRef () const { if (Data) Data->IncrRef (); } + +public: +inline CcuSmartPointerTo () : Data (0) { } +inline CcuSmartPointerTo (DATA* d) : Data (d) { IncrDataRef (); } +inline CcuSmartPointerTo (const CcuSmartPointerTo& p) : Data (p.Data) { IncrDataRef (); } +inline ~CcuSmartPointerTo () { DecrDataRef (); Data = 0; } +inline CcuSmartPointerTo& operator = (DATA* d) { if (d != Data) { DecrDataRef (); Data = d; IncrDataRef (); } return *this;} +inline int operator == (const DATA* d) const { return Data == d;} +inline int operator != (const DATA* d) const { return Data != d;} +inline int operator == (const CcuSmartPointerTo& p) const { return Data == p.Data;} +inline int operator != (const CcuSmartPointerTo& p) const { return Data != p.Data;} +inline DATA* operator -> () const { return Data; } +inline DATA& operator * () const { return *Data; } +inline operator DATA* () const { return Data; } +}; + +#define PointerClass(SmartClass, DataClass) typedef CcuSmartPointerTo SmartClass; + + +#else /* CPLUS_BUG19 */ + +#define PointerClass(SmartClass, DataClass) \ + class SmartClass { \ + protected: \ + DataClass* Data; \ + inline void DecrDataRef () const { if (Data) Data->DecrRef (); } \ + inline void IncrDataRef () const { if (Data) Data->IncrRef (); } \ + \ + public: \ + inline SmartClass () : Data (0) { } \ + inline SmartClass (DataClass* d) : Data (d) { IncrDataRef (); } \ + inline SmartClass (const SmartClass& p) : Data (p.Data) { IncrDataRef (); } \ + inline ~SmartClass () { DecrDataRef (); Data = 0; } \ + inline SmartClass& operator = (DataClass* d) { if (d != Data) { DecrDataRef (); Data = d; IncrDataRef (); } return *this;} \ + inline int operator == (const DataClass* d) const { return Data == d;} \ + inline int operator != (const DataClass* d) const { return Data != d;} \ + inline int operator == (const SmartClass& p) const { return Data == p.Data;} \ + inline int operator != (const SmartClass& p) const { return Data != p.Data;} \ + inline DataClass* operator -> () const { return Data; } \ + inline DataClass& operator * () const { return *Data; } \ + inline operator DataClass* () const { return Data; } \ + }; + +#endif /* CPLUS_BUG19 */ + +#define DerivedPointerClass(SmartClass, BaseSmartClass, DataClass) \ + class SmartClass : public BaseSmartClass { \ + public: \ + inline SmartClass () : BaseSmartClass () { } \ + inline SmartClass (const SmartClass& p) : BaseSmartClass (p) { } \ + inline SmartClass (DataClass* d) : BaseSmartClass (d) { } \ + inline SmartClass& operator = (DataClass* d) { if (d != Data) { DecrDataRef (); Data = d; IncrDataRef (); } return *this; } \ + inline DataClass* operator -> () const { return (DataClass*) Data; } \ + inline DataClass& operator * () const { return * ((DataClass*) Data); } \ + inline operator DataClass* () const { return (DataClass*) Data; } \ + }; + +#ifdef DOC +global macro PointerClass (SmartClass, DataClass); +global macro DerivedPointerClass (SmartClass, BaseSmartClass, DataClass); +#endif + +#endif /* SmartPointer_H_ */ + diff --git a/utils/String.cc b/utils/String.cc new file mode 100644 index 0000000..3da5d7d --- /dev/null +++ b/utils/String.cc @@ -0,0 +1,240 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * CcuString allocation and copying + * + * $Id$ + * $CurLog$ + */ + +#include "String.h" +#include +#include + +/*? +\label{newstring} +Allocate a string the same size as \var{s}, +copy \var{s} in it, and return the address. \var{s} must be a null-terminated string. +If \var{s} is 0, return 0. +?*/ +char* +NewString (const char* s) +{ + char* p; + + if (! s) + return 0; + + p = new char [strlen (s) + 1]; + strcpy (p, s); + return p; +} + + +/*? +Allocate a string of \var{n} characters, +copy the \var{n} first characters of \var{s} in it, +and return the address. The returned string is null terminated. +If \var{s} is 0, return 0. +?*/ +char* +NewString (const char* s, int n) +{ + char* p; + + if (! s) + return 0; + p = NewString (n); + if (! p) + return 0; + strncpy (p, s, n); + p [n] = 0; + return p; +} + +/*? +Allocate a string of \var{n} characters, +and return its address. Actually, \var{n+1} characters are allocated, +to keep space for the terminating null character. +If \var{n} is negative, return 0. Note that \fun{NewString}~\var{0} will allocate +one character that will be able to hold an empty string. +?*/ +char* +NewString (int n) +{ + if (n < 0) + return 0; + + return new char [n+1]; +} + + +/*? +Free a string which has previously been +allocated with \fun{NewString}. +If \var{s} is 0, do nothing. +Please be careful: it is impossible to test whether \var{s} was really allocated with \fun{NewString}. +?*/ +void +FreeString (char* s) +{ + if (s) +#ifdef CPLUS_BUG4 + delete [strlen (s) + 1] s; +#else + delete [] s; +#endif +} + +/*?class CcuString +?*/ + +#ifdef DOC +/*? +Build an empty \typ{CcuString}. +?*/ +CcuString :: CcuString () +{ +} +#endif + +/*? +Build a \typ{CcuString} from \var{s}. \var{s} can be null. +?*/ +CcuString :: CcuString (const char* s) +{ + Str = NewString (s); +} + +/*? +Create a \typ{CcuString} suitable for storing at most \var{n} characters, and +initialize it to the null string. +?*/ +CcuString :: CcuString (int n) +{ + Str = NewString (n); + *Str = '\0'; +} + +/*? +Create a new \typ{CcuString} by copying \var{s}. +?*/ +CcuString :: CcuString (const CcuString& s) +{ + Str = NewString (s); +} + +/*? +Create a new \typ{CcuString} by copying \var{s}. +?*/ +CcuString :: CcuString (const CcuShadowString& s) +{ + Str = NewString (s); +} + +/*?nodoc?*/ +CcuString :: ~CcuString () +{ + if (Str) + FreeString (Str); +} + + +/*? +Copy \var{s} into this string. The old string is freed. +?*/ +CcuString& +CcuString :: operator = (const CcuString& s) +{ + if (this != &s) { + FreeString (Str); + Str = NewString (s); + } + return *this; +} + +CcuString& +CcuString :: operator = (const char* s) +{ + if (Str != s) { + FreeString (Str); + Str = NewString (s); + } + return *this; +} + +CcuString& +CcuString :: operator = (const CcuShadowString& s) +{ + if (Str != (const char*) (s)) { + FreeString (Str); + Str = NewString (s); + } + return *this; +} + +#ifdef DOC +/*? +Return the value of a string. +?*/ +CcuString :: operator const char* () const +{ +} +#endif + +int +CcuString :: Length () const +{ + return strlen (Str); +} + +#ifdef DOC +/*? +Build an empty \typ{CcuShadowString}. +?*/ +CcuShadowString :: CcuShadowString () +{ + Str = 0; +} +#endif + +/*? +?*/ +CcuShadowString :: CcuShadowString (const char* s) +{ + Str = s; +} + +/*? +Create a new \typ{CcuShadowString} by referencing \var{s}. +?*/ +CcuShadowString :: CcuShadowString (const CcuString& s) +{ + Str = (const char*) s; +} + +#ifdef DOC +CcuShadowString& +CcuShadowString :: operator = (const CcuString& s) +{ +} + +CcuShadowString& +CcuShadowString :: operator = (const char* s) +{ +} + +/*? +Return the value of a string. +?*/ +CcuShadowString :: operator const char* () const +{ +} +#endif + + diff --git a/utils/String.h b/utils/String.h new file mode 100644 index 0000000..4aa83ca --- /dev/null +++ b/utils/String.h @@ -0,0 +1,61 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * CcuString allocation and copying + * + * $Id$ + * $CurLog$ + */ + +#ifndef String_H_ +#define String_H_ + +#include "cplus_bugs.h" + +/*? class StringMemory ?*/ +extern char* NewString (const char*); +extern char* NewString (const char*, int); +extern char* NewString (int); +extern void FreeString (char*); +/*? end ?*/ + +class CcuShadowString; + +class CcuString { +private: + char* Str; +public: +inline CcuString () { Str = 0; } + CcuString (const char*); + CcuString (int); + CcuString (const CcuString&); + CcuString (const CcuShadowString&); + ~CcuString (); + CcuString& operator = (const CcuString&); + CcuString& operator = (const char*); + CcuString& operator = (const CcuShadowString&); +inline operator const char* () const { return Str; } + int Length () const; +}; + +class CcuShadowString { +private: + const char* Str; +public: +inline CcuShadowString () { Str = 0; } + CcuShadowString (const char*); + CcuShadowString (const CcuString&); +inline CcuShadowString& operator = (const CcuString& s) { Str = (const char*) s; return *this; } +inline CcuShadowString& operator = (const char* s) { Str = s; return *this; } +inline operator const char* () const { return Str; } + int Length () const; +}; + +#endif /* String_H_ */ + diff --git a/utils/Time.cc b/utils/Time.cc new file mode 100644 index 0000000..6780178 --- /dev/null +++ b/utils/Time.cc @@ -0,0 +1,90 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * time management + * + * $Id$ + * $CurLog$ + */ + +#include "Time.h" +#include +extern "C" int gettimeofday (struct timeval *, struct timezone *); + +/*?class CcuTimeStamp +The class \var{CcuTimeStamp} provides variables that can be manipulated as +integers, but whose initial value is set according to the current time. +The following example should be self-explanatory: +\begin{ccode} + CcuTimeStamp before; + long_task (); + CcuTimeStamp after; + Millisecond delay = after - before; +\end{ccode} +The values of \typ{CcuTimeStamp}s are expressed in milliseconds. +The type \typ{Millisecond} is currently defined as \typ{long int}. +?*/ + +/*? +Create a time stamp. Its value is set according to the current time. +?*/ +CcuTimeStamp :: CcuTimeStamp () +{ + struct timeval tv; + gettimeofday (&tv, 0); + Value = 1000 * tv.tv_sec + tv.tv_usec / 1000; +} + +#ifdef DOC +/*? +Get the value of a time stamp. +?*/ +CcuTimeStamp :: operator Millisecond () const +{ +} +#endif /* DOC */ + +/*?class CcuTime +The class \typ{CcuTime} provides a simple way of manipulating real-time. Objects +of this class are used like integer variables whose value would change with time. +That behavior is obtained through the redefinition of the operator yielding the +integer value. + +Time values are expressed with the type \typ{Millisecond}, which is currently implemented +as \typ{long int}. You may initialize a \typ{CcuTime} with a negative value. +?*/ + +/*? +Initialize a time variable with initial value \var{t}. +?*/ +CcuTime :: CcuTime (Millisecond t) +{ + CcuTimeStamp now; + Offset = now - t; +} + +/*? +Get the current value of a time variable. +?*/ +CcuTime :: operator Millisecond () const +{ + CcuTimeStamp now; + return now - Offset; +} + +/*? +Reinitialize a time variable to the value \var{t}. +?*/ +CcuTime& +CcuTime :: operator = (Millisecond t) +{ + CcuTimeStamp now; + Offset = now - t; + return *this; +} + diff --git a/utils/Time.h b/utils/Time.h new file mode 100644 index 0000000..998a23c --- /dev/null +++ b/utils/Time.h @@ -0,0 +1,41 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * time management + * + * $Id$ + * $CurLog$ + */ + +#ifndef Time_H_ +#define Time_H_ + +#include "cplus_bugs.h" + +typedef long Millisecond; + +class CcuTimeStamp { +protected: + Millisecond Value; +public: + CcuTimeStamp (); +inline operator Millisecond () const { return Value; } +}; + + +class CcuTime { +protected: + Millisecond Offset; +public: + CcuTime (Millisecond = 0); + CcuTime& operator = (Millisecond); + operator Millisecond () const; +}; + +#endif /* Time_H_ */ + diff --git a/utils/Timer.cc b/utils/Timer.cc new file mode 100644 index 0000000..7911f9a --- /dev/null +++ b/utils/Timer.cc @@ -0,0 +1,402 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * timers + * + * $Id$ + * $CurLog$ + */ + +#include "Timer.h" +#include "Signal.h" +#include "List.h" + +#include +#include +#include +#include +#include + +/*?class CcuBaseTimer +The class \typ{CcuBaseTimer} is provided as a base class for timers. +It comes with a derived class \typ{CcuTimer} that can immediately be used. +A timer is created with a period expressed in milliseconds. It will then +periodically call the member function \fun{Handle}, which should be redefined +in derived classes. + +Please note that timers use the signal \var{SIGALRM} and the interval timers +provided by UNIX. +Using them concurrently with system calls such as \fun{sleep} yields +unexpected results. + +The member function \fun{Handle} has a time parameter: it is passed the +current (absolute) time when the signal was received from the system. However, +several timers may be triggered at the same time. +If one of them has a slow \fun{Handle}, the time passed to the next ones no more +corrresponds to the current time. If you want to know the exact time, and you are +not sure of the behaviour of the other timers, it is preferable to use a \typ{CcuTimeStamp}. +?*/ + +/*!class CcuBaseTimer +The implementation of CcuBaseTimer is a bit tricky, because it tries to be fast. +Here is the basic idea: active timers are stored in a list, sorted by increasing time-out +times. When a signal occurs, all timers whose time-out time is smaller than the current +time are notified and removed from the list, then they are inserted again. +Then, the optimizations. First, we distinguish the first active timer from the others. +It is not in the list, but has a pointer of its own. Second, we do not remove timers +from the list when they are stopped, but rather flag them as inactive. It means that +we have to test a flag when extracting timers from the list. It also means that we can +have many occurences of the same timer in the list, only one being in the right place. +Even worse, when such a timer is inserted again in the list, there is no way of knowing +that the other occurences are wrong: it is the same object, and it no longer flagged as +inactive. However, if we remove all encountered inactive timers when inserting one, +and if we make sure that a timer is flagged as inactive when we insert it, all wrong +occurences before the right one will be removed. +!*/ + +CcuSignalHandler* CcuBaseTimer::TimeOutHandler = 0; +CcuBaseTimer* CcuBaseTimer::FirstActive = 0; +#ifndef CPLUS_BUG19 +CcuListOf * CcuBaseTimer::OtherActive = 0; +#else +CcuList* CcuBaseTimer::OtherActive = 0; +#endif + +/*?nodoc?*/ +void +CcuBaseTimer :: ClassInit () +{ + TimeOutHandler = new CcuSignalHandler (SigAlrm, &CcuBaseTimer::HandleSignal); +#ifndef CPLUS_BUG19 + OtherActive = new CcuListOf ; +#else + OtherActive = new CcuList; +#endif +} + +/*?hidden?*/ +void +CcuBaseTimer :: StopAlarm () +{ + struct itimerval itval; + timerclear (&itval.it_value); + timerclear (&itval.it_interval); + setitimer (ITIMER_REAL, &itval, 0); +} + +/*?hidden?*/ +void +CcuBaseTimer :: SetAlarm (Millisecond delay) +{ + if (delay <= 0) { + StopAlarm (); + kill (getpid (), SigAlrm); + return; + } + + struct itimerval itval; + timerclear (&itval.it_interval); + itval.it_value.tv_sec = delay / 1000; + itval.it_value.tv_usec = 1000 * (delay % 1000); + setitimer (ITIMER_REAL, &itval, 0); +} + +/*! +Remove and return the first active timer in the active timer list. +Timers in that list can actually be inactive. +!*/ +/*?hidden?*/ +CcuBaseTimer* +CcuBaseTimer :: ExtractNextActive () +{ + CcuBaseTimer* t; + + /* all entries of OtherActive are valid pointers, + hence t == 0 iff OtherActive is empty */ +#ifndef CPLUS_BUG19 + while ((t = OtherActive->RemoveFirst ()) && (t->Status != Active)) +#else + while ((t = (CcuBaseTimer*) OtherActive->RemoveFirst ()) && (t->Status != Active)) +#endif + ; + return t; +} + +#ifndef CPLUS_BUG19 + +/*?hidden?*/ +int +CcuBaseTimer :: IsInactive (CcuBaseTimer* t) +{ + return (t->Status != Active); +} + +#else + +/*?hidden?*/ +int +CcuBaseTimer :: IsInactive (CcuListItem* t) +{ + return (((CcuBaseTimer*) t)->Status != Active); +} + +#endif /* CPLUS_BUG19 */ + + +/*! +This function is called by the signal handler. The first active timer is expired +and scheduled again. Then all the timers whose expiration time is earlier +that the current time are removed from the list, expired and scheduled again. +The first non-expired timer, if any, is removed from the list and saved +as the first active timer. +Finally, the alarm is set up to expire at the expiration time of the new first +active timer. +!*/ +/*?hidden?*/ +void +CcuBaseTimer :: HandleSignal (int) +{ + CcuTimeStamp now; + + /* Handle the first timer */ + FirstActive->Reschedule (); + FirstActive->Handle (now); + + /* handle all other expired timers. */ + CcuBaseTimer* t; + while (t = ExtractNextActive ()) { + /* Problem : if one Handle () is long, "now" will then be wrong. */ + if (t->NextDate > now) + break; + t->Reschedule (); + t->Handle (now); + } + + CcuTimeStamp then; + if (t) + SetAlarm (t->NextDate - then); + + + FirstActive = t; +} + + +/*? +Create a timer that will send a signal every \var{period} milliseconds, \var{pulses} times. +If \var{pulses} is negative, the timer will send signals forever. +Timers are activated at creation time. They are disactivated, but not destroyed, after +their last signal. +?*/ +CcuBaseTimer :: CcuBaseTimer (Millisecond period, int pulses) +: Status (Active), + Period (period), + PulsesLeft (pulses) +{ + CcuSignalBlocker b (SigAlrm); + + if (!TimeOutHandler) + ClassInit (); + if (PulsesLeft != 0) + Activate (); +} + + +/*?hidden?*/ +CcuBaseTimer :: ~CcuBaseTimer () +{ + /* stop it */ + if (Status == Active) + Stop (); + + /* Remove all entries pointing to inactive timers, including this one */ + OtherActive->Remove (IsInactive, CcuList::All); +} + +/*? +Change the period of a timer. The new period will not be taken into account +before the next time-out. +?*/ +void +CcuBaseTimer :: ChangePeriod (Millisecond period) +{ + CcuSignalBlocker b (SigAlrm); + Period = period; +} + +/*? +Stop this timer if it was running, then start it with its current period. +This function can be used to reset a timer to the beginning of a period. +?*/ +void +CcuBaseTimer :: Restart () +{ + if (PulsesLeft == 0) + return; + + /* this function could be optimized: sometimes SetAlarm is called twice. */ + CcuSignalBlocker b (SigAlrm); + if (Status == Active) + Stop (); + Activate (); +} + +/*! +This function sets up a timer that was previously inactive. +The timer is inserted in the list of active timers, and if it is the +first one, the alarm is updated. +!*/ +/*?hidden?*/ +void +CcuBaseTimer :: Activate () +{ + CcuTimeStamp now; + NextDate = now + Period; + + if (!FirstActive) { + FirstActive = this; + SetAlarm (Period); + } else if (NextDate < FirstActive->NextDate ) { + SetAlarm (Period); + OtherActive->Prepend (FirstActive); + FirstActive = this; + } else + Schedule (NextDate); + Status = Active; +} + +/*?hidden?*/ +void +CcuBaseTimer :: Reschedule () +{ + if (PulsesLeft == 0) // this should not happen... + return; + + if (PulsesLeft > 0) + if (--PulsesLeft == 0) + return; + + Schedule (NextDate + Period); +} + +/*?hidden?*/ +void +CcuBaseTimer :: Schedule (Millisecond when) +{ + NextDate = when; + + /* temporarily set status to inactive so that obsolete entries + in OtherActive pointing to this timer can be removed */ + Status = Inactive; + +#ifndef CPLUS_BUG19 + CcuListIterOf li (*OtherActive); + CcuListIterOf lj (*OtherActive); +#else + CcuListIter li (*OtherActive); + CcuListIter lj (*OtherActive); +#endif + + while (++li) { + /* while we're at it, remove inactive timers from the list */ +#ifndef CPLUS_BUG19 + CcuBaseTimer* cur = *li; +#else + CcuBaseTimer* cur = (CcuBaseTimer*) *li; +#endif + if (cur->Status != Active) { + OtherActive->RemoveAfter (lj); + li = lj; + } else if (cur->NextDate < NextDate) + ++lj; + else + break; + } + OtherActive->InsertAfter (lj, this); + Status = Active; +} + +/*? +Stop a timer. +This timer will not deliver any signal until \fun{Restart} is called. +?*/ +void +CcuBaseTimer :: Stop () +{ + if (Status != Active) + return; + + CcuSignalBlocker b (SigAlrm); + + Status = Inactive; + + /* if this timer was the first active one, find another one to replace it */ + if (this == FirstActive) { + FirstActive = ExtractNextActive (); + if (FirstActive == 0) + StopAlarm (); + else { + CcuTimeStamp now; + SetAlarm (FirstActive->NextDate -now); + } + } +} + +/*? +Wait for this timer to expire. If it is stopped, return immediately. +?*/ +void +CcuBaseTimer :: Wait () +{ + if (Status != Active) + return; + + Millisecond next_date = NextDate; + for (;;) { + if (wait (0) >= 0) // not an interrupt + continue; + if (Status != Active || next_date != NextDate) + return; + } +} + +/*?hidden?*/ +void +CcuBaseTimer :: Handle (Millisecond) +{ +} + +/*?class CcuTimer +The class \typ{CcuTimer} is a derived class of \typ{CcuBaseTimer} that +can be used without deriving a new class. +Each \typ{CcuTimer} holds a pointer to a function which is called when the timer +expires. This function, which is passed to the constructor, must +take a \typ{Millisecond} argument and return \typ{void}. +?*/ + +/*? +Create a timer that will expire every \var{period} milliseconds and call +the function \var{handler}. +?*/ +CcuTimer :: CcuTimer (Millisecond period, void (*handler) (Millisecond), int pulses) +: CcuBaseTimer (period, pulses), + Handler (handler) +{ +} + +/*?nodoc?*/ +CcuTimer :: ~CcuTimer () +{ +} + +/*?nodoc?*/ +void +CcuTimer :: Handle (Millisecond ref) +{ + (*Handler) (ref); +} + diff --git a/utils/Timer.h b/utils/Timer.h new file mode 100644 index 0000000..d361802 --- /dev/null +++ b/utils/Timer.h @@ -0,0 +1,83 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * timers + * + * $Id$ + * $CurLog$ + */ + +#ifndef Timer_H_ +#define Timer_H_ + +#include "cplus_bugs.h" +#include "Time.h" + +class CcuSignalHandler; +#if 0 +template class CcuListOf; +#else +#include "List.h" +#endif + +class CcuBaseTimer { +public: + enum timer_status { Active, Inactive }; + +private: +static CcuSignalHandler* TimeOutHandler; +static CcuBaseTimer* FirstActive; +#ifndef CPLUS_BUG19 +static CcuListOf * OtherActive; +#else +static CcuList* OtherActive; +#endif + +static void ClassInit (); +static void HandleSignal (int); +static void SetAlarm (Millisecond); +static void StopAlarm (); +static CcuBaseTimer* ExtractNextActive (); +static int IsInactive (CcuBaseTimer*); + + Millisecond NextDate; + Millisecond Period; + int PulsesLeft; + timer_status Status; + + void Activate (); + void Schedule (Millisecond); + void Reschedule (); + +protected: +virtual void Handle (Millisecond); + +public: + CcuBaseTimer (Millisecond, int = -1); +virtual ~CcuBaseTimer (); + void ChangePeriod (Millisecond first); + void Stop (); + void Restart (); + void Wait (); +inline Millisecond GetPeriod () const { return Period; } +inline int GetNbPulses () const { return PulsesLeft; } +inline timer_status GetStatus () const { return Status; } +}; + +class CcuTimer : public CcuBaseTimer { +protected: + void (*Handler) (Millisecond); + void Handle (Millisecond); + +public: + CcuTimer (Millisecond, void (*) (Millisecond), int = -1); + ~CcuTimer (); +}; + +#endif /* Timer_H_ */ + -- cgit v1.1