along/secondo
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
secondo/Tools/NestedLists/NestedList.cpp

2750 lines
69 KiB
C++
Raw Permalink Normal View History

firs commit
2026-01-23 17:03:45 +08:00
/*
----
This file is part of SECONDO.
Copyright (C) 2004, University in Hagen, Department of Computer Science,
Database Systems for New Applications.
SECONDO is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
SECONDO is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with SECONDO; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
----
//paragraph [1] Title: [{\Large \bf ] [}]
//[ae] [\"a]
//[oe] [\"o]
//[ue] [\"u]
//[ss] [{\ss}]
//[->] [$\rightarrow $]
1 Implementation of Stable Nested Lists
Copyright (C) 1995 Gral Support Team
November 1995 Ralf Hartmut G[ue]ting
March 8, 1996 Holger Schenk
May 13, 1996 Carsten Mund
June 10, 1996 RHG Changed result type of procedure RealValue back to REAL.
September 24, 1996 RHG Cleaned up PD representation.
October 22, 1996 RHG Corrected EndOfList, Nth-Element, and Second ... Sixth.
Made operations ~ListLength~ and ~WriteListExpr~ available. Changed internal
procedure ~WriteList~ so that atoms following a list are written indented to
the same level as a preceding list. This affects all output of lists.
November 14, 1996 RHG Removed ~SetValid~ commands.
November 18, 1996 RHG Changed Import from ~CatalogManager~ to ~Ctable~
in component ~ListsAndTables~.
November 22, 1996 RHG Added a final ~WriteLn~ in ~WriteToFile~.
January 20, 1997 RHG Corrected procedure ~AtomType~. Removed error message
from ~ReadFromString~.
September 26, 1997 Stefan Dieker Corrected wrong order of CTable calls in
~Append~, ~AppendText~, and all procedures creating atoms.
May 8, 1998 RHG Changed the way how text atoms are written to the screen.
Affects procedures ~WriteAtom~, ~WriteLists~.
October 12, 1998 Stefan Dieker. The name of the temporary file created by
~ReadFromString~ is now unique for each call of ~ReadFromString~.
December 1, 2001 Ulrich Telle Port to C++
November 28, 2002 M. Spiekermann coding of reportVectorSizes().
December 05, 2002 M. Spiekermann methods InitializeListMemory() and
CopyList/CopyRecursive implemented.
April 22, 2003 V. Almeida changed the methods CopyList and Destroy to use
iteration instead of recursion.
Jan - May 2003, M. Spiekermann. Get() and Put() Methods of CTable.h were
used to allow switching between persistent and in memory implementations of
NL without writing special code for both implementations.
Uncomment the precompiler directive \#define CTABLE\_PERSISTENT for support
of big nested lists.
Currently it is not possible to mix both alternatives.
December 2003, M. Spiekermann. A new method GetNextText has been introduced
and and the implementation of Text2String was changed in order to use
stringstreams.
February 2004, M. Spiekermann. Reading of binary encoded lists was implemented.
WriteAtom changed;
only 48 bytes of text atoms are displayed on screen now.
July 2004, M. Spiekermann. A big constant was replaced by UINT\_MAX and PD
syntax corrected.
August 2004, M. Spiekermann. A char pointer in ~StringSymbolValue~ has been
changed to an array of char.
1 Introduction
A nested list is represented by four stable tables called ~Nodes~, ~Ints~,
~Strings~, and ~Texts~.
2 Imports
*/
#include <string.h>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include "CharTransform.h"
#include "NLParser.h"
#include "WinUnix.h"
#include "FileSystem.h"
#include "LogMsg.h"
#include "Counter.h"
#include "StringUtils.h"
using namespace std;
// used in PagedArray.h
unsigned int FileCtr = 0;
/*
3 Preliminaries
3.1 Constants, Types \& Variables
Definitions implied by convention:
*/
size_t NestedList::NLinstance = 0;
NodeRecord::NodeRecord() :
nodeType(BoolType),
isRoot(false),
strLength(0),
inLine(0),
references(1){
}
ostream& operator<<(ostream& out, const NodeRecord& nr){
out << "nr: " << NestedList::NodeType2Text(nr.nodeType) << " " ;
if(nr.nodeType==NoAtom){
out << (nr.isRoot?"root":"non-root");
}
if(nr.nodeType==StringType || nr.nodeType==SymbolType){
out << " strlength("<< (int)nr.strLength<<") ";
out << (nr.inLine ?"inline" : "non-inline") ;
}
out << " refs = " << nr.references << " ";
if(nr.nodeType == NoAtom){
out << "left(" << nr.n.left << ") "
<< ", right(" << nr.n.right << ")";
} else if(nr.nodeType==IntType){
out << "value = " <<nr.a.value.intValue;
} else if (nr.nodeType==RealType){
out << "value = " << nr.a.value.realValue;
} else if(nr.nodeType==BoolType){
out << "value = " << (nr.a.value.boolValue?"true":"false");
} else if( (nr.nodeType==StringType)
||(nr.nodeType==SymbolType)){
if(!nr.inLine){
out << "first("<<nr.s.first<<")";
out << "field -> stringTable";
} else {
out << "field =" << string(nr.s.field,nr.strLength);
}
} else if( nr.nodeType==TextType){
out << "start(" << nr.t.start<<")";
out << "last(" << nr.t.last<<")";
} else {
out << "unknown nodetype" ;
}
return out;
}
template<class Array>
Cardinal emptySlot(Array& a, set<Cardinal>& freeSlots){
if(freeSlots.empty()){
return a.EmptySlot();
}
set<Cardinal>::iterator it = freeSlots.begin();
Cardinal res = *it;
freeSlots.erase(it);
return res;
}
/*
This constant defines whether the ~Destroy~ method really destroys a
nested list. Only if ~doDestroy~ is ~true~, nested lists are destroyed.
The ~Destroy~ method was never used. The concept for freeing list memory has
changed and therefore an implementation of this method is no longer useful.
However, the code for destroying in this file will not be compiled but unless
you comment out the line below.
*/
#ifdef THREAD_SAFE
boost::mutex smtx;
#endif
NestedList::NestedList(string dir /* ="" */,
const uint32_t nodeMem,
const uint32_t strMem,
const uint32_t textMem )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::mutex> guard1(smtx);
#endif
assert( sizeof(float) == 4);
// How can we convert a N byte floating point representation
// to a M byte representation?
stringTable = 0;
nodeTable = 0;
textTable = 0;
instanceNo = NLinstance++;
stringstream ss;
if(!dir.empty()){
FileSystem::AppendSlash(dir);
if(!FileSystem::FileOrFolderExists(dir)){
if(FileSystem::CreateFolderEx(dir)){
ss << dir;
}
} else {
if(FileSystem::IsDirectory(dir)){
ss << dir;
}
}
}
ss << "TMP_NESTED_LIST_" << WinUnix::getpid() << "_" << instanceNo;
basename = ss.str();
setMem(nodeMem, strMem, textMem);
initializeListMemory();
}
NestedList::~NestedList()
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
DeleteListMemory();
}
void
NestedList::DeleteListMemory()
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
//cerr << "DeleteListMem this = " << (void*)this << endl;
//cerr << "stringTable = " << (void*) stringTable << endl;
//cerr << "nodeTable = " << (void*) nodeTable << endl;
//cerr << "textTable = " << (void*) textTable << endl;
if(stringTable){
delete stringTable;
stringTable = 0;
}
if(nodeTable){
delete nodeTable;
nodeTable = 0;
}
if(textTable){
delete textTable;
textTable = 0;
}
freeNodeSlots.clear();
freeStringSlots.clear();
freeTextSlots.clear();
}
void
NestedList::setMem( Cardinal nodeMem, Cardinal strMem, Cardinal textMem)
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
nodeEntries = (nodeMem * 1024) / sizeof(NodeRecord);
stringEntries = (strMem * 1024) / sizeof(StringRecord);
textEntries = (textMem * 1024) / sizeof(TextRecord);
}
void
NestedList::initializeListMemory()
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
//cout << endl << "### NestedList::initializeListMemory" << endl;
DeleteListMemory(); //cleans also free sets
nodeTable = BigArray<NodeRecord>::newInstance(basename+"_nodes",
nodeEntries,true);
stringTable = BigArray<StringRecord>::newInstance(basename+"_strings",
stringEntries,true);
textTable = BigArray<TextRecord>::newInstance(basename+"_texts",
textEntries,true);
typeError = SymbolAtom("typeerror");
errorList = OneElemList( SymbolAtom("ERRORS") );
}
string
NestedList::SizeOfStructs() {
stringstream sizes;
sizes << "NodeRecord: " << sizeof(NodeRecord) << endl;
sizes << "TextRecord: " << sizeof(TextRecord) << endl;
sizes << "StringRec.: " << sizeof(StringRecord) << endl;
return sizes.str();
}
/*
3.1 PrintTableTexts
PrintTableTexts displays the contents of the Table 'Texts' on the screen.
The procedure was very helpful during the test phase of the module, and is
not used anywhere in the current version of the module.
*/
void
NestedList::PrintTableTexts() const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
Cardinal i, numEntries;
numEntries = textTable->NoEntries();
cout << "/////////////////////////////////////////////////////////////"
<< endl;
for ( i = 1; i <= numEntries; i++ )
{
if ( textTable->IsValid( i ) )
{
const TextRecord& entry = (*textTable)[i];
cout << endl << "Index: " << i;
cout << endl << "Field: " << entry.field;
cout << endl << "Next: " << entry.next << endl;
}
}
cout << "||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||"
<< endl;
}
/*
3.2 NodeType2Text
Converts an instance of NODETYPE into the corresponding textual representation.
*/
string
NestedList::NodeType2Text( NodeType type )
{
switch (type)
{
case NoAtom: return ("NoAtom");
case IntType: return ("IntType");
case RealType: return ("RealType");
case BoolType: return ("BoolType");
case StringType: return ("StringType");
case SymbolType: return ("SymbolType");
case TextType: return ("TextType");
default: return ("Type unknown");
}
}
ListExpr
NestedList::First( const ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( !IsEmpty( list ) && !IsAtom( list ) );
return ((*nodeTable)[list].n.left);
};
ListExpr
NestedList::Rest( const ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( !IsEmpty( list ) && !IsAtom( list ) );
return ((*nodeTable)[list].n.right);
};
ListExpr
NestedList::End( ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
ListExpr last = Empty();
while ( !IsEmpty(list) ) {
last = list;
list = Rest(list);
}
return last;
}
/*
4.2 Cons
*/
ListExpr
NestedList::Cons( const ListExpr left, const ListExpr right,
bool incRefs)
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( !IsAtom( right ) );
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
// concatenate nodes
NodeRecord tmpNodeVal;
nodeTable->Get(newNode, tmpNodeVal);
tmpNodeVal.nodeType = NoAtom;
tmpNodeVal.n.left = left;
tmpNodeVal.n.right = right;
tmpNodeVal.isRoot = 1;
tmpNodeVal.references = 1;
(*nodeTable).Put(newNode, tmpNodeVal);
if ( ! IsEmpty( left ) )
{
nodeTable->Get(left, tmpNodeVal);
tmpNodeVal.isRoot = 0;
if(incRefs){
tmpNodeVal.references++;
}
(*nodeTable).Put(left, tmpNodeVal);
}
if ( !IsEmpty( right ) )
{
(*nodeTable).Get(right, tmpNodeVal);
if(incRefs){
tmpNodeVal.references++;
}
tmpNodeVal.isRoot = 0;
(*nodeTable).Put(right, tmpNodeVal);
}
return (newNode);
}
/*
4.3 Append
*/
ListExpr
NestedList::Append ( const ListExpr lastElem,
const ListExpr newSon,
bool incRef )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( EndOfList(lastElem) );
NodeRecord lastElemNodeRec;
(*nodeTable).Get(lastElem, lastElemNodeRec);
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
NodeRecord newNodeRec;
(*nodeTable).Get(newNode, newNodeRec);
lastElemNodeRec.n.right = newNode;
newNodeRec.nodeType = NoAtom;
newNodeRec.n.left = newSon;
newNodeRec.n.right = 0;
newNodeRec.isRoot = 0;
newNodeRec.references = 1;
(*nodeTable).Put(lastElem, lastElemNodeRec);
(*nodeTable).Put(newNode, newNodeRec);
if ( !IsEmpty( newSon ) ) {
NodeRecord newSonRec;
(*nodeTable).Get(newSon, newSonRec);
newSonRec.isRoot = 0;
if(incRef){
newSonRec.references++;
}
(*nodeTable).Put(newSon, newSonRec);
}
return (newNode);
}
/*
4.4 Destroy
The ~Destroy~ method was never used. The concept for freeing list memory has
changed and therefore an implementation of this method is no longer useful.
The code in this file will not compile but may be used as start point for
an implementation if ever needed. Look at the Copy List method which works
similarly.
*/
void NestedList::DestroyRec(ListExpr& list){
if(IsEmpty(list)){
return;
}
switch( AtomType(list) ) {
case BoolType :
case IntType :
case RealType : {
NodeRecord root;
nodeTable->Get(list, root);
assert(root.references>0);
root.references--;
if(root.references>0){
nodeTable->Put(list,root);
return;
}
freeNodeSlots.insert(list);
}
break;
case SymbolType :
case StringType : {
NodeRecord root;
nodeTable->Get(list, root);
assert(root.references>0);
root.references--;
if(root.references>0){
nodeTable->Put(list,root);
return;
}
freeNodeSlots.insert(list);
if(!root.inLine){
Cardinal next = root.s.first;
root.s.first = 0;
while(next){
StringRecord sr;
stringTable->Get(next,sr);
freeStringSlots.insert(next);
Cardinal last = next;
next = sr.next;
sr.next = 0;
stringTable->Put(last, sr);
}
}
}
break;
case TextType : {
NodeRecord root;
nodeTable->Get(list, root);
assert(root.references>0);
root.references--;
if(root.references>0){
nodeTable->Put(list,root);
return;
}
Cardinal next = root.t.start;
root.t.start = 0;
freeNodeSlots.insert(list);
while(next){
TextRecord tr;
textTable->Get(next,tr);
freeTextSlots.insert(next);
Cardinal last = next;
next = tr.next;
tr.next = 0;
textTable->Put(last, tr);
}
}
break;
case NoAtom : {
NodeRecord root;
nodeTable->Get(list, root);
assert(root.references>0);
root.references--;
if(root.references>0){
nodeTable->Put(list,root);
return;
}
freeNodeSlots.insert(list);
// destroy first
DestroyRec(root.n.left);
// destroy rest
Cardinal scan = root.n.right;
while(scan){
nodeTable->Get(scan, root);
root.references--;
if(root.references==0){
freeNodeSlots.insert(scan);
}
DestroyRec(root.n.left);
scan = root.n.right;
}
}
break;
default: assert(false); // invalid atom type
}
}
void
NestedList::Destroy(ListExpr& list )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
DestroyRec(list);
list = 0;
}
void NestedList::IncReferences(ListExpr& list){
if(list){
NodeRecord node;
nodeTable->Get(list, node);
assert(node.references>0);
node.references++;
nodeTable->Put(list,node);
}
}
/*
5 Simple Tests
5.1 ListLength
*/
int
NestedList::ListLength( ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
~list~ may be any list expression. Returns the number of elements, if it is
a list, and -1, if it is an atom.
*/
int result = 0;
if ( IsAtom( list ) )
{
result = -1;
}
else
{
while ( !IsEmpty( list ) )
{
result++;
list = Rest( list );
}
}
return (result);
}
bool
NestedList::HasLength( ListExpr list, const int n ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if ( IsAtom(list) ){
return false;
}
int result = 0;
while ( !IsEmpty( list ) && (result < n) )
{
result++;
list = Rest( list );
}
return (result == n) && (IsEmpty(list));
}
/*
~HasMinLength~
Returns true iff the Given Listexpr contains at least n elements.
*/
bool
NestedList::HasMinLength( ListExpr list, const int n ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if ( IsAtom(list) ){
return false;
}
int result = 0;
while ( !IsEmpty( list ) && (result < n) )
{
result++;
list = Rest( list );
}
return (result == n) ;
}
int
NestedList::ExprLength( ListExpr expr ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
Reads a list expression ~expr~ and counts the number ~length~ of
subexpressions.
*/
int length = 0;
while (!IsAtom( expr ) && !IsEmpty( expr ))
{
length++;
expr = Rest( expr );
}
if ( IsAtom( expr ) )
{
length++;
}
return (length);
}
/*
enum NodesStacked { None, Left, Right, Both };
struct CopyStackRecord
{
CopyStackRecord( NodeRecord nr, NodesStacked ns = None, ListExpr le = 0 ):
nr( nr ),
ns( ns ),
le( le )
{}
NodeRecord nr;
NodesStacked ns;
ListExpr le;
};
*/
ListExpr
NestedList::SimpleCopy(const ListExpr list, NestedList* target) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
//cout << "NestedList::SimpleCopy" << endl;
stringstream ss;
ListExpr temp = list;
WriteBinaryTo(temp, ss);
ListExpr result = TheEmptyList();
target->ReadBinaryFrom(ss, result);
return result;
}
bool
NestedList::IsEqual( const ListExpr atom, const string& str,
const bool caseSensitive ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
returns TRUE if ~atom~ is a symbol atom and has the same value as ~str~.
*/
if ( IsAtom( atom ) && (AtomType( atom ) == SymbolType) )
{
if ( caseSensitive )
{
return (SymbolValue( atom ) == str);
}
else
{
string aStr = SymbolValue( atom );
string bStr = str;
transform( aStr.begin(), aStr.end(),
aStr.begin(), ToUpperProperFunction );
transform( bStr.begin(), bStr.end(),
bStr.begin(), ToUpperProperFunction );
return (aStr == bStr);
}
}
else
{
return (false);
}
}
/*
6 Scanning and Parsing
6.1 ReadFromFile
*/
bool
NestedList::ReadFromFile ( const string& fileName, ListExpr& list )
{
if(!FileSystem::FileOrFolderExists(fileName) ||
FileSystem::IsDirectory(fileName)){
return false;
}
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
bool success = false;
list = 0;
ifstream ifile( fileName.c_str() );
if ( ifile )
{
NLParser* nlParser = new NLParser( this, &ifile );
if ( nlParser->parse() == 0 )
{
list = nlParser->GetNestedList();
success = true;
}
delete nlParser;
ifile.close();
}
else
{
cmsg.error() << "Could not access file '" << fileName << "'" << endl;
cmsg.send();
}
return (success);
}
/*
Internal procedure *WriteAtom*
*/
void
NestedList::WriteAtom( const ListExpr atom,
bool toScreen, ostream& ostr ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
switch ((*nodeTable)[atom].nodeType)
{
case IntType:
ostr << IntValue( atom );
break;
case RealType:
{
ostringstream os;
//os << showpoint ;
//os << scientific ;
os << setprecision(16) << RealValue( atom );
if ( (os.str().find( '.' ) == string::npos) &&
(os.str().find('e') == string::npos))
{
os << ".0";
}
ostr << os.str();
}
break;
case BoolType:
ostr << BoolToStr( BoolValue( atom ) );
break;
case StringType:{
string s(StringValue(atom));
s = stringutils::replaceAll(
stringutils::replaceAll(s,"\\","\\\\"),"\"","\\\"");
ostr << "\"" << s << "\"";
break;
}
case SymbolType:
ostr << SymbolValue( atom );
break;
case TextType:
{
if ( !toScreen )
{
ostr << "'";
string textFragment = "";
TextScanInfo info;
while ( GetNextText(atom, textFragment, 1024, info) ) {
ostr << transformText2Outtext(textFragment);
}
ostr << "'";
} else {
static const size_t len=48;
string textFragment = "";
TextScan textScan = CreateTextScan( atom );
GetText( textScan, len, textFragment );
ostr << "'" << textFragment << "'";
if ( textFragment.length() > len ) {
ostr << " ... (text atom truncated after "
<< len << " bytes)";
}
DestroyTextScan ( textScan );
}
}
break;
default: /* Error */
ostr << "WriteAtom: NodeType out of range!" << endl;
break;
}
}
/*
Internal procedure *WriteList*
*/
bool
NestedList::WriteList( ListExpr list,
const int level,
const bool afterList,
const bool toScreen,
ostream& os,
const int offset /*=4*/ ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
Write a list ~List~ indented by 4 blanks for each ~Level~ of nesting. Atoms
are written sequentially into a line as long as they do not follow a
nonempty list (~AfterList~ = FALSE). Otherwise (~AfterList~ = TRUE) they are
also indented to the current level. Text atoms are written indented into a
new line like lists. If ~ToScreen~ is true, then text atoms are written
without their brackets.
*/
const int indent = level*offset;
bool after = false;
if ( IsEmpty( list ) )
{
os << endl << tab(indent) << "()";
return (afterList);
}
else if ( IsAtom( list ))
{
if ( afterList || (AtomType( list) == TextType ) )
{
os << endl << tab(indent);
}
WriteAtom( list, toScreen, os );
return (afterList);
}
else
{
os << endl << tab(indent) << "(";
after = WriteList( First( list ), level+1, false, toScreen, os, offset );
while (!IsEmpty( Rest( list ) ))
{
list = Rest( list );
os << " ";
after = WriteList( First( list ), level+1, after, toScreen, os, offset );
}
os << ")";
return (true);
}
}
/*
6.2 WriteToFile
*/
bool
NestedList::WriteToFile( const string& fileName, const ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( !IsAtom( list ) );
bool ok = false;
ofstream outFile( fileName.c_str() );
if ( outFile )
{
WriteList( list, 0, false, false, outFile );
outFile << endl;
outFile.close();
ok = true;
}
return (ok);
}
/*
6.3 ReadFromString
*/
bool
NestedList::ReadFromString( const string& nlChars, ListExpr& list )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
The job of this procedure is to read a string and to convert it to a nested
list.
Short: String [->] NestedList
*/
bool success = false;
list = 0;
istringstream inString( nlChars );
if ( inString )
{
NLParser* nlParser = new NLParser( this, &inString );
if ( nlParser->parse() == 0 )
{
list = nlParser->GetNestedList();
success = true;
}
delete nlParser;
}
return (success);
}
/*
6.4 String Conversion
6.4.1 ToString
*/
string
NestedList::ToString( const ListExpr list ) const
{
string listStr;
int Success = WriteToString(listStr, list);
assert( Success );
return listStr;
}
/*
6.4.2 WriteToString
*/
bool
NestedList::WriteToString( string& nlChars, const ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
bool ok =false;
ostringstream nlos;
if ( (ok=WriteToStringLocal( nlos, list ))) {
nlChars = nlos.str();
} else {
nlChars = "";
}
return ok;
}
/*
6.4.2 WriteStringTo
Write a list in its textual representation into an ostream object
*/
bool
NestedList::WriteStringTo( const ListExpr list, ostream& os ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
bool ok =false;
ok=WriteToStringLocal( os, list );
return ok;
}
/*
Internal procedure *WriteToStringLocal*
*/
bool
NestedList::WriteToStringLocal( ostream& nlChars, ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
Error Handling in this procedure: If anything goes wrong, the execution of the
function is finished immediately, and the function result is ~false~, if the
string nlChars could not be written properly, or if there was something wrong
within the structure of the list, otherwise, the function result is ~true~.
*/
ostringstream os;
if ( IsEmpty( list ) )
{
nlChars << "()";
}
else if ( IsAtom ( list ) )
{
switch ( (*nodeTable)[list].nodeType )
{
case IntType:
os << IntValue( list );
nlChars << os.str();
break;
case RealType:
os << setprecision(16) << RealValue( list );
if ( (os.str().find( '.' ) == string::npos )&&
(os.str().find('e') == string::npos))
{
os << ".0";
}
nlChars << os.str();
break;
case BoolType:
nlChars << BoolToStr( BoolValue( list ) );
break;
case StringType:{
string s = StringValue(list);
s = stringutils::replaceAll(
stringutils::replaceAll(s,"\\","\\\\"),"\"","\\\"");
nlChars << ("\"" + s + "\"");
break;
}
case SymbolType:
nlChars << SymbolValue( list );
break;
case TextType:
// ToDo replace tempText with a loop which
// writes small fragments into nlChars
{
/*
TextScan textScan = CreateTextScan( list );
string tempText = "";
GetText( textScan, TextLength( list ), tempText );
DestroyTextScan( textScan );
nlChars << ("<text>" + tempText + "</text--->");
*/
if ( RTFlag::isActive("NL:TextLength") ) {
cerr << "list, TextLength( list ): "
<< list << "," << TextLength( list ) << endl;
}
nlChars << "'";
string textFragment = "";
TextScanInfo info;
while ( GetNextText(list, textFragment, 1024, info) ) {
textFragment = transformText2Outtext(textFragment);
nlChars << textFragment;
}
nlChars << "'";
}
break;
default:
return (2);
}
}
else
{ /* List is neither empty nor an atom */
nlChars << "(";
bool ok = WriteToStringLocal( nlChars, First( list ) );
if ( !ok ) {
return (ok);
}
while ( !IsEmpty( Rest( list ) ) )
{
nlChars << " ";
list = Rest( list );
ok = WriteToStringLocal( nlChars, First( list ) );
if ( !ok ) {
return (ok);
}
}
nlChars << ")";
}
/* This point in the function is only reached if no error occurred before. */
return (true);
}
/*
6.4 WriteBinaryTo: Write a list in binary encoded format into
an output stream
*/
bool
NestedList::WriteBinaryTo(const ListExpr list, ostream& os) const {
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( os.good() );
const nlbyte v[7] = {'b','n','l',0,1,0,2};
os.write((char*)v,7);
bool ok = WriteBinaryRec(list, os);
os.flush();
return ok;
}
/*
6.4 ReadBinaryFrom: Reconstruct a list from
an input stream containing a binary encoded list
*/
bool
NestedList::ReadBinaryFrom(istream& in, ListExpr& list) {
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( in.good() );
char version[8] = {0,0,0,0,0,0,0,0};
in.read(version,7);
string vStr = string(version);
if ( vStr.substr(0,3) != "bnl" ) {
cerr << "Error: Input stream is not a binary encoded nested list." << endl;
list = 0;
return false;
}
// version number check ommitted
unsigned long pos = 0;
bool ok = ReadBinaryRec(list, in, pos);
return ok;
}
/*
6.4 hton (host to network) converts a 'long' value with
LSB (little endian) byte order into the network representation
MSB (big endian). This computation should be independent of the
hosts internal representation of a long value.
*/
void
NestedList::hton(long value, char* buffer) const {
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
static const int n = sizeof(long);
for (int i=0; i<n; i++) {
buffer[n-1-i] = (nlbyte) (value & 255);
value = value >> 8;
}
}
// Type IDs for binary encoded lists
static const nlbyte BIN_LONGLIST = 0;
static const nlbyte BIN_INTEGER = 1;
static const nlbyte BIN_REAL = 2;
static const nlbyte BIN_BOOLEAN = 3;
static const nlbyte BIN_LONGSTRING = 4;
static const nlbyte BIN_LONGSYMBOL = 5;
static const nlbyte BIN_LONGTEXT = 6;
static const nlbyte BIN_LIST = 10;
static const nlbyte BIN_SHORTLIST = 11;
static const nlbyte BIN_SHORTINT = 12;
static const nlbyte BIN_BYTE = 13;
static const nlbyte BIN_STRING = 14;
static const nlbyte BIN_SHORTSTRING = 15;
static const nlbyte BIN_SYMBOL= 16;
static const nlbyte BIN_SHORTSYMBOL = 17;
static const nlbyte BIN_TEXT = 18;
static const nlbyte BIN_SHORTTEXT = 19;
static const nlbyte BIN_DOUBLE = 20;
/*
6.4 GetBinaryType: Determine the binary type ID of a list value
depending on the size of the list atom.
*/
nlbyte
NestedList::GetBinaryType(const ListExpr list) const {
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
switch( AtomType(list) ) {
case BoolType : return BIN_BOOLEAN;
case IntType : { long v = IntValue(list);
if( v>=numeric_limits<char>::min()
&& v<=numeric_limits<char>::max())
return BIN_BYTE;
if( v>=numeric_limits<short>::min()
&& v<=numeric_limits<short>::max())
return BIN_SHORTINT;
return BIN_INTEGER;
}
case RealType : return BIN_DOUBLE;
case SymbolType : { int len = SymbolValue(list).length();
if(len<256)
return BIN_SHORTSYMBOL;
if(len<65536)
return BIN_SYMBOL;
return BIN_LONGSYMBOL;
}
case StringType : { int len = StringValue(list).length();
if(len<256)
return BIN_SHORTSTRING;
if(len<65536)
return BIN_STRING;
return BIN_LONGSTRING;
}
case TextType : { int len = TextLength(list);
if(len<256)
return BIN_SHORTTEXT;
if(len<65536)
return BIN_TEXT;
return BIN_LONGTEXT;
}
case NoAtom : { if(HasMinLength(list,256)){
return BIN_LONGLIST;
} else {
return BIN_SHORTLIST;
}
}
default : return (nlbyte) 255;
}
}
/*
6.4 ReadInt: This is the counterpart to the function hton.
A 4 byte (signed) integer value is created.
*/
int32_t
NestedList::ReadInt(istream& in, const int len /*= 4*/) const{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
static const bool debug = RTFlag::isActive("NL:BinaryListDebug");
char buffer[4] = { 0, 0, 0, 0 };
int32_t result = 0;
in.read(buffer,len);
if( debug ) {
cerr << "Hex-Value: ";
for (int i=0; i<len; i++) {
cerr << setiosflags(ios::showbase | ios::hex)
<< (unsigned char) buffer[i] << " ";
}
}
for (int i=0; i<len; i++) {
result = result << 8;
result += (unsigned char) 255 & buffer[i];
}
if( debug ) {
cerr << " => Int-Value: " << setiosflags(ios::dec)
<< result << endl;
}
return result;
}
/*
6.4 ReadShort: This is the counterpart to the function hton.
A 2 byte (signed) integer value is created.
*/
int32_t
NestedList::ReadShort(istream& in) const {
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
int32_t result = ReadInt(in, 2);
if((result & 0x8000) == 0x8000) {
//result is negativ, adjust first bytes
result |= ((~0l) ^ 0xffff) ;
}
return result;
}
/*
6.4 swap: Convert a ~N~ byte buffer into reverse order. This is needed to
convert float/double values between little endian an big endian
representation.
*/
inline void
NestedList::swap(char* buffer, const int n) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
for (int i = 0; i < n/2; i++)
{
char c = buffer[n-1-i];
buffer[n-1-i] = buffer[i];
buffer[i] = c;
}
}
/*
6.4 ReadString: This function allocates temporarily
a character buffer, reads a given number of characters into it and
converts the buffer into a string object.
*/
void
NestedList::ReadString( istream& in,
string& outStr, unsigned long length) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
char* strBuf = new char[length+1];
in.read(strBuf, length);
strBuf[length]=0;
outStr = string(strBuf);
delete [] strBuf;
}
bool
NestedList::ReadBinarySubLists( ListExpr& LE, istream& in,
unsigned long length,
unsigned long& pos )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if(length==0) {
LE = TheEmptyList();
return true;
}
ListExpr subList = 0;
bool ok = ReadBinaryRec(subList, in, pos);
if(!ok) // error in reading sublist
return false;
LE = OneElemList(subList,false);
ListExpr Last = LE;
ListExpr Next = 0;
for(unsigned int i=1; i<length; i++){
bool ok = ReadBinaryRec(Next, in, pos);
if(!ok) // error in reading sublist
return false;
Last = Append(Last,Next,false);
}
return true;
}
/*
6.4 ReadBinaryRec: This recursive function reconstructs a list from
a stream containing binary encoded list data.
*/
bool
NestedList::ReadBinaryRec(ListExpr& result, istream& in, unsigned long& pos) {
static const bool debug = RTFlag::isActive("NL:BinaryListDebug");
unsigned long len = 0;
string str = "";
nlbyte typeId = 255 & in.get();
pos++;
if( debug ) {
cerr << "TypeId: " << (unsigned int) (255 & typeId) << endl;
}
switch( typeId ){
case BIN_BOOLEAN : { result = BoolAtom( in.get() ? true : false );
pos++;
return true;
}
case BIN_BYTE : { char c = 0;
in.read(&c,1);
result = IntAtom( c );
pos++;
return true;
}
case BIN_SHORTINT : { result = IntAtom( ReadShort(in) );
pos += 2;
return true;
}
case BIN_INTEGER : { result = IntAtom( ReadInt(in) );
pos +=4;
return true;
}
case BIN_REAL : {
float fval = 0;
char* fp = (char*) &fval;
in.read(fp, 4);
pos +=4;
if ( WinUnix::isLittleEndian() ) {
swap(fp,sizeof(float));
}
result = RealAtom( fval );
return true;
}
case BIN_DOUBLE : {
double dval = 0;
char* dp = (char*) &dval;
in.read(dp, 8);
pos += 8;
if ( WinUnix::isLittleEndian() ) {
swap(dp,sizeof(double));
}
result = RealAtom( dval );
return true;
}
case BIN_SHORTSTRING : { len = 255 & in.get();
ReadString(in, str, len);
pos = pos + 1 + len;
result = StringAtom( str );
return true;
}
case BIN_STRING : { len = 65535 & ReadShort(in);
ReadString(in, str, len);
pos = pos + 2 + len;
result = StringAtom( str );
return true;
}
case BIN_LONGSTRING : { len = UINT_MAX & ReadInt(in);
ReadString(in, str, len);
pos = pos + 4 + len;
result = StringAtom( str );
return true;
}
case BIN_SHORTSYMBOL : { len = 255 & in.get();
ReadString(in, str, len);
pos = pos + 1 + len;
result = SymbolAtom( str );
return true;
}
case BIN_SYMBOL : { len = 65535 & ReadShort(in);
ReadString(in, str, len);
pos = pos + 2 + len;
result = SymbolAtom( str );
return true;
}
case BIN_LONGSYMBOL : { len = UINT_MAX & ReadInt(in);
ReadString(in, str, len);
pos = pos + 4 + len;
result = SymbolAtom( str );
return true;
}
case BIN_SHORTTEXT : { len = 255 & in.get();
ReadString(in, str, len);
pos = pos + 1 + len;
ListExpr text = TextAtom();
AppendText(text, str );
result = text;
return true;
}
case BIN_TEXT : { len = 65535 & ReadShort(in);
ReadString(in, str, len);
pos = pos + 2 + len;
ListExpr text = TextAtom();
AppendText(text, str );
result = text;
return true;
}
case BIN_LONGTEXT : { len = UINT_MAX & ReadInt(in);
ReadString(in, str, len);
pos = pos + 4 + len;
ListExpr text = TextAtom();
AppendText(text, str );
result = text;
return true;
}
case BIN_SHORTLIST : { len = 255 & in.get();
pos++;
ListExpr LE = 0;
if( debug ) {
cerr << "len: " << len << endl;
}
bool ok = ReadBinarySubLists(LE, in, len,pos);
if (!ok) {
result = 0;
return false;
} else {
result = LE;
return true;
}
}
case BIN_LIST : { len = 65535 & ReadShort(in);
pos += 2;
ListExpr LE = 0;
bool ok = ReadBinarySubLists(LE, in,len,pos);
if (!ok) {
result = 0;
return false;
} else {
result = LE;
return true;
}
}
case BIN_LONGLIST : { len = 4294967295u & ReadInt(in); // 2^32-1
pos += 4;
ListExpr LE = 0;
bool ok = ReadBinarySubLists(LE,in,len,pos);
if (!ok) {
cout << "Error in ReadBinarySubLists(...)!"
<< endl;
result = 0;
return false;
} else {
result = LE;
return true;
}
}
default : {
cerr << "Error: Unknown binary list type ID: "
<< (unsigned int) typeId
<< " at position " << pos << endl;
//cerr << "Last read string: " << str << endl;
return false;
}
}
}
/*
6.4 WriteBinaryRec: This recursive function writes
lists in binary format to the output stream.
*/
bool
NestedList::WriteBinaryRec(ListExpr list, ostream& os) const {
static const bool debug = RTFlag::isActive("NL:BinaryListDebug");
static const int floatLen=sizeof(float);
static const int doubleLen=sizeof(double);
static const int longLen=sizeof(long);
unsigned long strlen = 0;
unsigned int len = 0;
os.flush();
assert( os.good() );
nlbyte typeId = GetBinaryType(list);
os << typeId;
switch( typeId ) {
case BIN_BOOLEAN: {
bool b = BoolValue(list);
nlbyte value = (nlbyte) (b?1:0);
os << (nlbyte) value;
return true;
}
case BIN_BYTE: {
char value = (char) IntValue(list);
os.write(&value,1);
return true;
}
case BIN_SHORTINT:
case BIN_INTEGER:
{
long value = IntValue(list);
char pv[sizeof(long)];
hton(value,pv);
if (typeId == BIN_BYTE) {
len = 1;
} else {
len = (typeId == BIN_SHORTINT) ? 2 : 4;
}
os.write(pv+longLen-len,len);
return true;
}
case BIN_REAL: {
float value = RealValue(list);
char val[floatLen];
memcpy( (void*) val, (void*) &value, floatLen );
if ( WinUnix::isLittleEndian() ) {
swap(val,sizeof(float));
}
os.write(val,floatLen);
return true;
}
case BIN_DOUBLE: {
double value = RealValue(list);
char val[doubleLen];
memcpy( (void*) val, (void*) &value, doubleLen );
if ( WinUnix::isLittleEndian() ) {
swap(val,sizeof(double));
}
os.write(val,doubleLen);
return true;
}
case BIN_SHORTSTRING:
case BIN_STRING:
case BIN_LONGSTRING: {
string value = StringValue(list);
strlen = value.length();
char pv[sizeof(long)];
hton(strlen,pv);
if (typeId == BIN_SHORTSTRING) {
len = 1;
} else {
len = (typeId == BIN_STRING) ? 2 : 4;
}
os.write(pv+longLen-len,len);
os << value;
return true;
}
case BIN_SHORTSYMBOL:
case BIN_SYMBOL:
case BIN_LONGSYMBOL: {
string value = SymbolValue(list);
strlen = value.length();
char pv[sizeof(long)];
hton(strlen,pv);
if (typeId == BIN_SHORTSYMBOL) {
len = 1;
} else {
len = (typeId == BIN_SYMBOL) ? 2 : 4;
}
os.write(pv+longLen-len,len);
os << value;
return true;
}
case BIN_SHORTTEXT:
case BIN_TEXT:
case BIN_LONGTEXT: {
strlen = TextLength(list);
char pv[sizeof(long)];
hton(strlen,pv);
if (typeId == BIN_SHORTTEXT) {
len = 1;
} else {
len = (typeId == BIN_TEXT) ? 2 : 4;
}
os.write(pv+longLen-len,len);
string value="";
TextScanInfo info;
while ( GetNextText(list, value, 1024, info) ) {
os << value;
}
return true;
}
case BIN_SHORTLIST:
case BIN_LIST:
case BIN_LONGLIST: {
if (debug) {
cerr << "TypeId: " << (unsigned int) (255 & typeId) << endl;
cerr << "ListLength: " << ListLength(list) << endl;
cerr << "sizeof(long): " << sizeof(long) << endl;
}
char pv[sizeof(long)];
hton(ListLength(list),pv);
if (typeId == BIN_SHORTLIST) {
len = 1;
} else {
len = (typeId == BIN_LIST) ? 2 : 4;
}
if (debug) {
cerr << "len: " << len << endl;
}
int offset=longLen-len;
if (debug) {
cerr << "offset: " << offset << endl;
}
os.write(pv+offset,len);
while( !IsEmpty(list) ){
if( !WriteBinaryRec( First(list), os ) ) {
// error in writing sublist
return false;
}
list=Rest(list);
}
return true;
}
default: return false;
}
}
/*
6.5 WriteListExpr
Write ~list~ indented by level to standard output.
*/
void
NestedList::WriteListExpr( const ListExpr list,
ostream& ostr /*= cout*/,
const bool toScreen, /*=true*/
const int offset /*= 4*/ )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
WriteList( list, 0, false, toScreen, ostr, offset );
}
/*
7 Traversal
7.3 NthElement
*/
ListExpr
NestedList::NthElement( const Cardinal n,
const Cardinal initialN,
const ListExpr list ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
/*
Return the ~n~-th element of ~List~. Since this is used recursively,
~initialN~ keeps the argument of the first call to be able to give intelligent
error messages. Must hence be called externally always with ~n~ = ~initialN~.
*Precondition* (for initial call): ~List~ is not empty and no atom and has at
least ~N~ elements.
*/
if ( IsEmpty( list ) )
{
cerr << endl << "NestedList-ERROR. *********" << endl
<< "Element " << initialN << " selected from a list with "
<< initialN - n << " elements!" << endl;
abort();
}
else if ( IsAtom( list ) )
{
cerr << endl << "NestedList-ERROR. *********" << endl
<< "Element " << initialN << " selected from an atom!" << endl;
abort();
}
else if ( n == 0 )
{
cerr << endl << "NestedList-ERROR. *********" << endl
<< "Function 'NthElement' called with Zero!" << endl;
abort();
}
else if ( n == 1)
{
return (First( list ));
}
else
{
return (NthElement( n-1, initialN, Rest( list ) ));
}
return (0);
}
/*
8 Construction of Atoms
8.1 IntAtom
*/
ListExpr
NestedList::IntAtom( const long value )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
NodeRecord newNodeRec;
nodeTable->Get(newNode, newNodeRec);
newNodeRec.nodeType = IntType;
newNodeRec.a.value.intValue = value;
newNodeRec.references = 1;
nodeTable->Put(newNode, newNodeRec);
return (newNode);
}
/*
8.2 RealAtom
*/
ListExpr
NestedList::RealAtom( const double value )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
NodeRecord newNodeRec;
nodeTable->Get(newNode, newNodeRec);
newNodeRec.nodeType = RealType;
newNodeRec.a.value.realValue = value;
newNodeRec.references = 1;
nodeTable->Put(newNode, newNodeRec);
return (newNode);
}
/*
8.3 BoolAtom
*/
ListExpr
NestedList::BoolAtom( const bool value )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
NodeRecord newNodeRec;
nodeTable->Get(newNode, newNodeRec);
newNodeRec.nodeType = BoolType;
newNodeRec.a.value.boolValue = value;
newNodeRec.references = 1;
nodeTable->Put(newNode, newNodeRec);
return (newNode);
}
/*
8.4 StringAtom
*/
ListExpr
NestedList::StringAtom( const string& value, bool isString /*=true*/ )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
int strLen = value.length();
assert( strLen <= MAX_STRINGSIZE );
NodeRecord newNodeRec;
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
nodeTable->Get(newNode, newNodeRec);
// store length and type information
newNodeRec.strLength = strLen;
if ( isString ) {
newNodeRec.nodeType = StringType;
} else {
newNodeRec.nodeType = SymbolType;
}
newNodeRec.references = 1;
if ( strLen <= STRING_INTERNAL_SIZE ) {
// store string directly in the node record
newNodeRec.inLine = 1;
value.copy( newNodeRec.s.field, strLen );
nodeTable->Put(newNode, newNodeRec);
return newNode;
}
newNodeRec.inLine = 0; // create records in the string table
StringRecord strRec;
Cardinal index = emptySlot(*stringTable, freeStringSlots);
stringTable->Get(index, strRec);
newNodeRec.s.first = index;
nodeTable->Put(newNode, newNodeRec);
unsigned char appendedChars = 0;
while ( strLen > appendedChars ) {
unsigned char n = strLen - appendedChars;
if ( n > StringFragmentSize ) {
n = StringFragmentSize;
}
value.copy( strRec.field, n, appendedChars );
appendedChars += n;
if ( appendedChars < strLen ) { // another fragment is needed
Cardinal pred = index; // save reference
index = emptySlot(*stringTable, freeStringSlots);
strRec.next = index;
stringTable->Put(pred, strRec);
stringTable->Get(index, strRec);
} else { // last fragment
strRec.next = 0;
stringTable->Put(index, strRec);
}
}
return newNode;
}
/*
8.5 SymbolAtom
*/
ListExpr
NestedList::SymbolAtom( const string& value )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
ListExpr newNode = StringAtom( value, false );
return (newNode);
}
/*
8.6 TextAtom
*/
ListExpr
NestedList::TextAtom()
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
Cardinal newNode = emptySlot(*nodeTable, freeNodeSlots);
NodeRecord newNodeRec;
(*nodeTable).Get(newNode, newNodeRec);
newNodeRec.nodeType = TextType;
newNodeRec.references = 1;
newNodeRec.t.start = emptySlot(*textTable, freeTextSlots);
newNodeRec.t.last = newNodeRec.t.start;
//newNodeRec.t.length = 0;
(*nodeTable).Put(newNode, newNodeRec);
TextRecord newTextRec;
(*textTable).Get(newNodeRec.t.start, newTextRec);
newTextRec.next = TheEmptyList();
memset( newTextRec.field, 0, TextFragmentSize );
(*textTable).Put(newNodeRec.t.start, newTextRec);
return (newNode);
}
/*
8.7 AppendText
*/
void
NestedList::AppendText( const ListExpr atom,
const string& textBuffer )
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( AtomType( atom ) == TextType );
NodeRecord atomContentRec;
(*nodeTable).Get(atom, atomContentRec);
TextRecord lastTextRec;
(*textTable).Get(atomContentRec.t.last, lastTextRec);
Cardinal lastFragmentLength = lastTextRec.used();
Cardinal emptyFragmentLength = TextFragmentSize - lastFragmentLength;
/*
cerr << "(emptyFragmentLength, TextFragmentSize, "
<< "lastFragmentLength, textBuffer.length() ): "
<< emptyFragmentLength << ","
<< TextFragmentSize << ","
<< lastFragmentLength << ","
<< textBuffer.length()
<< endl;
*/
/*
There are two cases: Either there is enough space in the current fragment
for NoChars, or there is not enough space. The last fragment of a text atom
is never filled completely (with TextFragmentSize characters), but it is
empty or it is filled with up to TextFragmentSize-1 characters.
*/
Cardinal textLength = textBuffer.length();
Cardinal textStart = 0;
if ( (lastFragmentLength + textLength) <= TextFragmentSize )
{
/* There is enough space in the last fragment. (Case 1) */
/* --> Append new text. */
textBuffer.copy( lastTextRec.field + lastFragmentLength,
emptyFragmentLength );
(*textTable).Put(atomContentRec.t.last, lastTextRec);
(*nodeTable).Put(atom, atomContentRec);
}
else
{
ListExpr newFragmentID;
/* There is not enough space in the last fragment. (Case 2) */
/* Steps 1/2: Fill current fragment completely. */
textBuffer.copy( lastTextRec.field + lastFragmentLength,
emptyFragmentLength );
textLength -= emptyFragmentLength;
textStart += emptyFragmentLength;
/* Step 2/2: Create new (empty) fragments and append them */
TextRecord newTextRec;
//TextRecord* plastRec = &lastTextRec;
while ( textLength > 0 )
{
// create a new text record
newFragmentID = emptySlot(*textTable, freeTextSlots);
(*textTable).Get(newFragmentID, newTextRec);
memset( newTextRec.field, 0, TextFragmentSize );
newTextRec.next = TheEmptyList();
// let the last one point to it and save it
lastTextRec.next = newFragmentID;
(*textTable).Put(atomContentRec.t.last, lastTextRec);
// compute how much bytes must be copied
emptyFragmentLength = (textLength <= TextFragmentSize)
? textLength
: TextFragmentSize;
textBuffer.copy( newTextRec.field, TextFragmentSize, textStart );
//textBuffer.copy( test1, TextFragmentSize, textStart );
//cerr << textLength << ", " << textStart << ":" << test1 << endl;
//cerr << "substr: "
// << textBuffer.substr(textStart, TextFragmentSize) << endl;
textLength -= emptyFragmentLength;
textStart += emptyFragmentLength;
atomContentRec.t.last = newFragmentID;
lastTextRec = newTextRec;
}
//cout << "textLength: " << textLength << endl;
//cout << "textStart: " << textStart << endl;
//cout << "field: " << string(newTextRec.field) << endl;
(*textTable).Put(atomContentRec.t.last, lastTextRec);
(*nodeTable).Put(atom, atomContentRec);
}
}
/*
9 Reading Atoms
9.1 IntValue
*/
long
NestedList::IntValue( const ListExpr atom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( AtomType( atom ) == IntType );
return ((*nodeTable)[atom].a.value.intValue);
}
/*
9.2 RealValue
*/
double
NestedList::RealValue( const ListExpr atom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( AtomType( atom ) == RealType );
return ((*nodeTable)[atom].a.value.realValue);
}
/*
9.3 BoolValue
*/
bool
NestedList::BoolValue( const ListExpr atom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( AtomType( atom ) == BoolType );
return ((*nodeTable)[atom].a.value.boolValue);
}
/*
9.4 StringSymbolValue
*/
string
NestedList::StringSymbolValue( const ListExpr atom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
const NodeRecord& atomRef = (*nodeTable)[atom];
char buffer[MAX_STRINGSIZE + 1];
const unsigned char strLen = atomRef.strLength;
assert( strLen <= MAX_STRINGSIZE );
if ( atomRef.inLine == 1 ) { // copy chars out of node record
assert(strLen <= STRING_INTERNAL_SIZE);
memcpy( buffer, atomRef.s.field, strLen );
} else { // copy chars from string table
Cardinal index = atomRef.s.first;
unsigned char appendedChars = 0;
while ( index ) {
unsigned char n = strLen - appendedChars;
if (n > StringFragmentSize)
n = StringFragmentSize;
memcpy( &(buffer[appendedChars]), (*stringTable)[index].field, n );
appendedChars += n;
index = (*stringTable)[index].next;
}
if( strLen != appendedChars )
{
cerr << "strlen: " << (unsigned int) strLen
<< ", appendedChars: " << (unsigned int) appendedChars << endl;
assert( false );
};
}
buffer[strLen]='\0';
return string(buffer);
}
/*
9.5 StringValue and SymbolValue
*/
string
NestedList::StringValue( const ListExpr atom ) const
{
assert( AtomType( atom ) == StringType );
return StringSymbolValue(atom);
}
string
NestedList::SymbolValue( const ListExpr atom ) const
{
assert( AtomType( atom ) == SymbolType );
return StringSymbolValue(atom);
}
/*
9.6 Treatment of Text Atoms
9.6.1 CreateTextScan
*/
TextScan
NestedList::CreateTextScan (const ListExpr atom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( AtomType( atom ) == TextType );
TextScan textScan = new TextScanRecord;
textScan->currentFragment = (*nodeTable)[atom].t.start;
textScan->currentPosition = 0;
return (textScan);
}
/*
9.6.2 GetText
*/
void
NestedList::GetText ( TextScan textScan,
const Cardinal noChars,
string& textBuffer ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
// load the current fragment
TextRecord fragment;
(*textTable).Get(textScan->currentFragment, fragment);
Cardinal sum=0; // already retrieved bytes in this call
Cardinal curPos = textScan->currentPosition;
while( sum < noChars) {
Cardinal n = min( fragment.used() - curPos, noChars );
textBuffer.append( &fragment.field[curPos], n);
sum += n;
textScan->currentPosition += n;
if (sum >= noChars) // all bytes retrieved
return;
if( fragment.next != 0 )
{
// get the next Fragment
textScan->currentFragment = fragment.next;
textScan->currentPosition = 0;
curPos = 0;
(*textTable).Get(textScan->currentFragment,fragment);
}
else
{
// more characters requested than stored
return;
}
}
}
/*
9.6.3 TextLength
Currently the length is aggregated by visiting all text record. This is
expensive and was only implemented as a temporary solution. It was done
to save memory in the NodeRecord representation.
*/
Cardinal
TextRecord::used() const {
Cardinal usedLength = 0;
for ( usedLength = 0;
usedLength < TextFragmentSize &&
field[usedLength];
usedLength++ );
return usedLength;
}
Cardinal
NestedList::TextLength ( const ListExpr textAtom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
assert( AtomType( textAtom ) == TextType );
TextRecord fragment;
Cardinal textLength = 0;
TextsEntry tnext = (*nodeTable)[textAtom].t.start;
textTable->Get(tnext, fragment);
textLength += TextFragmentSize;
while ( (tnext = fragment.next) != 0 ) {
textTable->Get(tnext, fragment);
textLength += TextFragmentSize;
}
textLength = textLength - TextFragmentSize + fragment.used();
return (textLength);
}
/*
9.6.4 EndOfText
*/
bool
NestedList::EndOfText( const TextScan textScan ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if ( textScan->currentFragment == 0 )
{
cerr << "textScan->currentFragment == 0: "
<< textScan->currentFragment << endl;
return (true);
}
else
{
TextRecord fragment = (*textTable)[textScan->currentFragment];
Cardinal used = fragment.used();
cerr << "fragment.next == 0, textScan->currentPosition"
<< " >= usedFragmentLength: "
<< fragment.next << ","
<< textScan->currentPosition << ","
<< used
<< endl;
return ((fragment.next == 0) &&
(textScan->currentPosition >= used));
}
}
/*
9.6.5 Alternative function for iteration over text atoms. This
was implemented, since EndOfText has not been used in the complete
SECONDO code.
*/
bool
NestedList::GetNextText( const ListExpr textAtom,
string& textFragment,
Cardinal size,
TextScanInfo& info ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if (info.last) { // end of text reached ?
textFragment = "";
DestroyTextScan ( info.textScan );
info.first = true;
info.last = false;
return false;
}
if (info.first) { // initialize status variables
info.atom = textAtom;
info.textFragmentLength = size;
info.textLength = TextLength( info.atom );
info.textScan = CreateTextScan( info.atom );
textFragment.resize(size);
info.first = false;
}
assert( (size == info.textFragmentLength));
assert(info.atom == textAtom);
textFragment="";
/* Write the text atom to the output stream in chunks
* of size textFragmentLength
*/
if (info.textFragmentLength < info.textLength)
{
GetText( info.textScan, info.textFragmentLength, textFragment );
info.textLength -= info.textFragmentLength;
assert(info.textLength >= 0);
return true;
} else {
GetText ( info.textScan, info.textLength, textFragment );
info.last = true; // end of text reached
return true;
}
}
/*
9.6.5 DestroyTextScan
*/
void
NestedList::DestroyTextScan( TextScan& textScan ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if ( textScan != 0 )
{
delete textScan;
textScan = 0;
}
}
/*
9.6.1 Text2String
*/
void
NestedList::Text2String( const ListExpr& textAtom, string& resultStr ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
ostringstream outStream;
string textFragment = "";
TextScanInfo info;
while ( GetNextText(textAtom, textFragment, 1024,info) ) {
outStream << textFragment;
}
resultStr = outStream.str();
}
string
NestedList::Text2String( const ListExpr& textAtom ) const {
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
ostringstream outStream;
string textFragment = "";
TextScanInfo info;
while ( GetNextText(textAtom, textFragment, 1024,info) ) {
outStream << textFragment;
}
return outStream.str();
}
/*
Replace some critical symbols within strings representing text atoms.
*/
string transformText2Outtext(const string& value)
{
string textReplaced = "";
textReplaced = stringutils::replaceAll(value, "\\", "\\\\");
textReplaced = stringutils::replaceAll(textReplaced, "'", "\\'");
return textReplaced;
};
/*
10 AtomType
*/
NodeType
NestedList::AtomType (const ListExpr atom ) const
{
#ifdef THREAD_SAFE
boost::lock_guard<boost::recursive_mutex> guard1(mtx);
#endif
if ( !IsAtom( atom ) )
{
return (NoAtom);
}
else
{
return ((*nodeTable)[atom].nodeType);
}
}
std::ostream& operator<<(ostream& out, StringRecord sr){
out << string(sr.field,StringFragmentSize);
if(sr.next) {
out << " -> " << sr.next << endl;
}
return out;
}
std::ostream& NestedList::printTables(std::ostream& out) const{
out << " Nodes: " << endl;
NodeRecord node;
if(!nodeTable){
out << "not present" << endl;
} else {
out << "nodeTable has " << nodeTable->NoEntries() << " entries" << endl;
for(size_t i=1;i<=nodeTable->NoEntries(); i++){
out << i << " : " ;
if(freeNodeSlots.find(i)!=freeNodeSlots.end()){
out << " free " << endl;
} else {
nodeTable->Get(i,node);
out << node << endl;
}
}
}
out << endl << " Strings : " << endl;
StringRecord sr;
if(!stringTable){
out << "not present" << endl;
} else {
out << "stringTable has " << stringTable->NoEntries()
<< " entries" << endl;
for(size_t i=1;i<=stringTable->NoEntries(); i++){
out << i << " : " ;
if(freeStringSlots.find(i)!=freeStringSlots.end()){
out << " free " << endl;
} else {
stringTable->Get(i,sr);
out << sr << endl;
}
}
}
out << endl << " Texts : " << endl;
return out;
}
const double Tolerance::MINERR = 1e-10;
Reference in New Issue Copy Permalink