Barebone.tar

Makefile0000700060175106017510000000227114475437150011603 0ustar  goetzgoetzCPPOPT=-g -Og -D_DEBUG
# -O2 -Os -Ofast
# -fprofile-generate -fprofile-use
CPPFLAGS=$(CPPOPT) -Wall -ansi -pedantic
# -Wparentheses -Wno-unused-parameter -Wformat-security
# -fno-rtti -std=c++11 -std=c++98

# documents and scripts
DOCS=Tasks.txt
SCRS=

# headers and code sources
HDRS=	defs.h \
		Iterator.h Scan.h Filter.h Sort.h
SRCS=	defs.cpp Assert.cpp Test.cpp \
		Iterator.cpp Scan.cpp Filter.cpp Sort.cpp

# compilation targets
OBJS=	defs.o Assert.o Test.o \
		Iterator.o Scan.o Filter.o Sort.o

# RCS assists
REV=-q -f
MSG=no message

# default target
#
Test.exe : Makefile $(OBJS)
	g++ $(CPPFLAGS) -o Test.exe $(OBJS)

trace : Test.exe Makefile
	@date > trace
	./Test.exe >> trace
	@size -t Test.exe $(OBJS) | sort -r >> trace

$(OBJS) : Makefile defs.h
Test.o : Iterator.h Scan.h Filter.h Sort.h
Iterator.o Scan.o Filter.o Sort.o : Iterator.h
Scan.o : Scan.h
Filter.o : Filter.h
Sort.o : Sort.h

list : Makefile
	echo Makefile $(HDRS) $(SRCS) $(DOCS) $(SCRS) > list
count : list
	@wc `cat list`

ci :
	ci $(REV) -m"$(MSG)" $(HDRS) $(SRCS) $(DOCS) $(SCRS)
	ci -l $(REV) -m"$(MSG)" Makefile
co :
	co $(REV) -l $(HDRS) $(SRCS) $(DOCS) $(SCRS)

clean :
	@rm -f $(OBJS) Test.exe Test.exe.stackdump trace
defs.h0000700060175106017510000000645414475064001011233 0ustar  goetzgoetz#pragma once

#include <stddef.h>
#include <stdint.h>
#include <cstdio>

typedef uint8_t byte;

#define slotsof(a)	(sizeof (a) / sizeof (a[0]))

#define nullptr	((void *) NULL)

#define yesno(b)	((b) ? "yes" : "no")

// call-through to assert() from <assert.h>
//
void Assert (bool const predicate,
		char const * const file, int const line);
//
#if defined ( _DEBUG )  ||  defined (DEBUG)
#define DebugAssert(b)	Assert ((b), __FILE__, __LINE__)
#else // _DEBUG DEBUG
#define DebugAssert(b)	(void) (0)
#endif // _DEBUG DEBUG
//
#define FinalAssert(b)	Assert ((b), __FILE__, __LINE__)
//	#define FinalAssert(b)	(void) (0)
//
#define ParamAssert(b)	FinalAssert (b)

#define traceprintf printf ("%s:%d:%s ", \
		__FILE__, __LINE__, __FUNCTION__), \
	printf

// -----------------------------------------------------------------

class Trace
{
public :

	Trace (bool const trace, char const * const function,
			char const * const file, int const line);
	~Trace ();

private :

	void _trace (char const lead []);

	bool const _output;
	char const * const _function;
	char const * const _file;
	int const _line;
}; // class Trace

#define TRACE(trace)	Trace __trace (trace, __FUNCTION__, __FILE__, __LINE__)

// -----------------------------------------------------------------

template <class Value> inline bool odd (
		Value const value, int bits_from_lsb = 0)
{
	return ((value >> bits_from_lsb) & Value (1)) != 0;
}
//
template <class Value> inline bool even (
		Value const value, int bits_from_lsb = 0)
{
	return ((Value (1) << bits_from_lsb) & value) == 0;
}

// templates for generic min and max operations
//
template <class Val> inline Val min (Val const a, Val const b)
{
	return a < b ? a : b;
}
//
template <class Val> inline Val max (Val const a, Val const b)
{
	return a > b ? a : b;
}
//
template <class Val> inline Val between (Val const value, Val const low, Val const high)
	// 'value' but no less than 'low' and no more than 'high'
{
	return (value < low ? low : value > high ? high : value);
}
//
template <class Val> inline void extremes (Val const value, Val & low, Val & high)
	// retain 'value' in 'low' or 'high' keeping track of extremes
{
	if (value < low) low = value;
	if (value > high) high = value;
}

// templates for generic division
// should work for any integer type
//
template <class Val> inline Val divide (Val const a, Val const b)
{
	return 1 + (a - 1) / b;
} // divide
//
template <class Val> inline Val roundup (Val const a, Val const b)
{
	return b * divide (a, b);
} // roundup

template <class Val> inline void exchange (Val & a, Val & b)
{
	Val const c = a;
	a = b;
	b = c;
} // exchange

// -----------------------------------------------------------------

template <class Val> inline Val mask (int const from, int const to)
{
	// from: index of lsb set to 1, range 0..31
	// to: index of msb set to 1, range from..31
	// from==to ==> single bit set
	//
	return (((Val) 2) << to) - (((Val) 1) << from);
} // Value mask (int from, int to)

size_t Random (size_t const range);
size_t Random (size_t const low_incl, size_t const high_incl);
size_t RoundDown (size_t const x, size_t const y);
size_t RoundUp (size_t const x, size_t const y);
bool IsPowerOf2 (size_t const x);
size_t lsb (size_t const x);
size_t msb (size_t const x);
int msbi (size_t const x);
char const * YesNo (bool const b);
char const * OkBad (bool const b);
Iterator.h0000644060175106017510000000054614475172404012115 0ustar  goetzgoetz#pragma once

#include "defs.h"

typedef uint64_t RowCount;

class Plan
{
	friend class Iterator;
public:
	Plan ();
	virtual ~Plan ();
	virtual class Iterator * init () const = 0;
private:
}; // class Plan

class Iterator
{
public:
	Iterator ();
	virtual ~Iterator ();
	void run ();
	virtual bool next () = 0;
private:
	RowCount _count;
}; // class Iterator
Scan.h0000644060175106017510000000065614475172362011215 0ustar  goetzgoetz#include "Iterator.h"

class ScanPlan : public Plan
{
	friend class ScanIterator;
public:
	ScanPlan (RowCount const count);
	~ScanPlan ();
	Iterator * init () const;
private:
	RowCount const _count;
}; // class ScanPlan

class ScanIterator : public Iterator
{
public:
	ScanIterator (ScanPlan const * const plan);
	~ScanIterator ();
	bool next ();
private:
	ScanPlan const * const _plan;
	RowCount _count;
}; // class ScanIterator
Filter.h0000644060175106017510000000075014475214511011542 0ustar  goetzgoetz#include "Iterator.h"

class FilterPlan : public Plan
{
	friend class FilterIterator;
public:
	FilterPlan (Plan * const input);
	~FilterPlan ();
	Iterator * init () const;
private:
	Plan * const _input;
}; // class FilterPlan

class FilterIterator : public Iterator
{
public:
	FilterIterator (FilterPlan const * const plan);
	~FilterIterator ();
	bool next ();
private:
	FilterPlan const * const _plan;
	Iterator * const _input;
	RowCount _consumed, _produced;
}; // class FilterIterator
Sort.h0000644060175106017510000000072214475172642011253 0ustar  goetzgoetz#include "Iterator.h"

class SortPlan : public Plan
{
	friend class SortIterator;
public:
	SortPlan (Plan * const input);
	~SortPlan ();
	Iterator * init () const;
private:
	Plan * const _input;
}; // class SortPlan

class SortIterator : public Iterator
{
public:
	SortIterator (SortPlan const * const plan);
	~SortIterator ();
	bool next ();
private:
	SortPlan const * const _plan;
	Iterator * const _input;
	RowCount _consumed, _produced;
}; // class SortIterator
defs.cpp0000700060175106017510000000312514474612667011576 0ustar  goetzgoetz#include <stdlib.h>
#include <stdio.h>

#include "defs.h"

// -----------------------------------------------------------------

Trace::Trace (bool const trace, char const * const function,
		char const * const file, int const line)
	: _output (trace), _function (function), _file (file), _line (line)
{
	_trace (">>>>>");
} // Trace::Trace

Trace::~Trace ()
{
	_trace ("<<<<<");
} // Trace::~Trace

void Trace::_trace (char const lead [])
{
	if (_output)
		printf ("%s %s (%s:%d)\n", lead, _function, _file, _line);
} // Trace::_trace

// -----------------------------------------------------------------

size_t Random (size_t const range)
{
	return (size_t) rand () % range;
} // Random

size_t Random (size_t const low_incl, size_t const high_incl)
{
	return low_incl + (size_t) rand () % (high_incl - low_incl + 1);
} // Random

size_t RoundDown (size_t const x, size_t const y)
{
	return x - (x % y);
} // RoundDown

size_t RoundUp (size_t const x, size_t const y)
{
	size_t const z = x % y;
	return (z == 0 ? x : x + y - z);
} // RoundUp

bool IsPowerOf2 (size_t const x)
{
	return x > 0 && (x & (x - 1)) == 0;
} // IsPowerOf2

size_t lsb (size_t const x)
{
	size_t const y = x & (x - 1);
	return x ^ y;
} // lsb

size_t msb (size_t const x)
{
	size_t y = x;
	for (size_t z;  z = y & (y - 1), z != 0;  y = z)
		; // nothing
	return y;
} // msb

int msbi (size_t const x)
{
	int i = 0;
	for (size_t z = 2;  z <= x;  ++ i, z <<= 1)
		; // nothing
	return i;
} // msbi

char const * YesNo (bool const b)
{
	return b ? "Yes" : "No";
} // YesNo

char const * OkBad (bool const b)
{
	return b ? "Ok" : "Bad";
} // OkBad
Assert.cpp0000700060175106017510000000055514474614573012120 0ustar  goetzgoetz#include <stdio.h>

#if 0
#include <assert.h>
#else
#include <stdlib.h>
#endif

#include "defs.h"

void Assert (bool const predicate,
		char const * const file, int const line)
{
	if (predicate)
		return;

	fflush (stdout);
	fprintf (stderr, "failed assertion at %s, %d\n", file, line);
	fflush (stderr);

#if 0
	assert (false);
#else
	exit (1);
#endif
} // Assert
Test.cpp0000644060175106017510000000051314475436341011573 0ustar  goetzgoetz#include "Iterator.h"
#include "Scan.h"
#include "Filter.h"
#include "Sort.h"

int main (int argc, char * argv [])
{
	TRACE (true);

	Plan * const plan = new ScanPlan (7);
	// new SortPlan ( new FilterPlan ( new ScanPlan (7) ) );

	Iterator * const it = plan->init ();
	it->run ();
	delete it;

	delete plan;

	return 0;
} // main
Iterator.cpp0000644060175106017510000000065614475341137012453 0ustar  goetzgoetz#include "Iterator.h"

Plan::Plan ()
{
	TRACE (true);
} // Plan::Plan

Plan::~Plan ()
{
	TRACE (true);
} // Plan::~Plan

Iterator::Iterator () : _count (0)
{
	TRACE (true);
} // Iterator::Iterator

Iterator::~Iterator ()
{
	TRACE (true);
} // Iterator::~Iterator

void Iterator::run ()
{
	TRACE (true);

	while (next ())  ++ _count;

	traceprintf ("entire plan produced %lu rows\n",
			(unsigned long) _count);
} // Iterator::run
Scan.cpp0000644060175106017510000000137114475340570011541 0ustar  goetzgoetz#include "Scan.h"

ScanPlan::ScanPlan (RowCount const count) : _count (count)
{
	TRACE (true);
} // ScanPlan::ScanPlan

ScanPlan::~ScanPlan ()
{
	TRACE (true);
} // ScanPlan::~ScanPlan

Iterator * ScanPlan::init () const
{
	TRACE (true);
	return new ScanIterator (this);
} // ScanPlan::init

ScanIterator::ScanIterator (ScanPlan const * const plan) :
	_plan (plan), _count (0)
{
	TRACE (true);
} // ScanIterator::ScanIterator

ScanIterator::~ScanIterator ()
{
	TRACE (true);
	traceprintf ("produced %lu of %lu rows\n",
			(unsigned long) (_count),
			(unsigned long) (_plan->_count));
} // ScanIterator::~ScanIterator

bool ScanIterator::next ()
{
	TRACE (true);

	if (_count >= _plan->_count)
		return false;

	++ _count;
	return true;
} // ScanIterator::next
Filter.cpp0000644060175106017510000000165514475341232012103 0ustar  goetzgoetz#include "Filter.h"

FilterPlan::FilterPlan (Plan * const input) : _input (input)
{
	TRACE (true);
} // FilterPlan::FilterPlan

FilterPlan::~FilterPlan ()
{
	TRACE (true);
	delete _input;
} // FilterPlan::~FilterPlan

Iterator * FilterPlan::init () const
{
	TRACE (true);
	return new FilterIterator (this);
} // FilterPlan::init

FilterIterator::FilterIterator (FilterPlan const * const plan) :
	_plan (plan), _input (plan->_input->init ()),
	_consumed (0), _produced (0)
{
	TRACE (true);
} // FilterIterator::FilterIterator

FilterIterator::~FilterIterator ()
{
	TRACE (true);

	delete _input;

	traceprintf ("produced %lu of %lu rows\n",
			(unsigned long) (_produced),
			(unsigned long) (_consumed));
} // FilterIterator::~FilterIterator

bool FilterIterator::next ()
{
	TRACE (true);

	do
	{
		if ( ! _input->next ())  return false;
		++ _consumed;
	} while (_consumed % 2 == 0);

	++ _produced;
	return true;
} // FilterIterator::next
Sort.cpp0000644060175106017510000000167314475340615011611 0ustar  goetzgoetz#include "Sort.h"

SortPlan::SortPlan (Plan * const input) : _input (input)
{
	TRACE (true);
} // SortPlan::SortPlan

SortPlan::~SortPlan ()
{
	TRACE (true);
	delete _input;
} // SortPlan::~SortPlan

Iterator * SortPlan::init () const
{
	TRACE (true);
	return new SortIterator (this);
} // SortPlan::init

SortIterator::SortIterator (SortPlan const * const plan) :
	_plan (plan), _input (plan->_input->init ()),
	_consumed (0), _produced (0)
{
	TRACE (true);

	while (_input->next ())  ++ _consumed;
	delete _input;

	traceprintf ("consumed %lu rows\n",
			(unsigned long) (_consumed));
} // SortIterator::SortIterator

SortIterator::~SortIterator ()
{
	TRACE (true);

	traceprintf ("produced %lu of %lu rows\n",
			(unsigned long) (_produced),
			(unsigned long) (_consumed));
} // SortIterator::~SortIterator

bool SortIterator::next ()
{
	TRACE (true);

	if (_produced >= _consumed)  return false;

	++ _produced;
	return true;
} // SortIterator::next
Tasks.txt0000644060175106017510000000112414475460224011772 0ustar  goetzgoetzTrace existing code
Disable (not remove!) excessive tracing output
Define class for data records
Add data records (incl mem mgmt) to iterators
Add data generation (random values) in ScanIterator
Test with simple plan -- scan only
Add predicate evaluation to FilterIterator
Test with moderate plan -- scan & filter
Add in-memory sorting -- eg 10, 100, 1000 rows
Test with moderate plan -- scan & sort
Add Plan & Iterator that verify a sort order
Test with 0 rows and with 1 row, also 2, 3, 7 rows
Add Plan & Iterator that verify a set of rows
Test with 0, 1, 2, 3, 10, 29, 100, 576, 1000 rows
...