An Experiment: From C Definitions To Templates

Posted 05-02-2015 at 09:22 PM by rainbowsally
Updated 05-03-2015 at 11:13 PM by rainbowsally (additions and corrections, description mod)

Tags computer mad science, simple c, template

An Experiment: From C Definitions To Templates

This is a tangent, but a forgivable one, no?

Today's mind-blowing Mad Computer Science features:

An experiment morphing a regular old C style set of functions into a set of C++ templates.
We rename a literal parameter type to a template parameter T and voila!
This will help demystify the horrible noise in the messy STL templates by making a simple transition from main_1 to main_2, in which error messages from the compiler ARE the tutorial.

If you've been scratching your head over templates, this really might help. Try adding some of the other functions defined in the objlist_* definitions and get a feel for how the compiler will literally guide you to working code.

And for those happy with STL, we wonder why. While the standard template library for C++ is pretty nifty in some ways there are two (count 'em 2) problems with it.

It's incredibly difficult to understand, even tracing it in a debugger, and
it's a bit large, and
it's somewhat oversized, and
it's kinda big, and
it doesn't always play nice with straight simple C.

What we want is something faster than light speed and as small as a pin point.

And we want it to be easy to follow reasonably well in a debugger. (Kdbg is my favorite debugger but ddd is adequate for most purposes, I think.)

With the above in mind and given the challenge of (foremost) givig C/C++ the capabilities of a lowly bash script, we want AS A MINIMUM to be able to address an array of strings as though they were char** types, like the arg list of a call to main. (This is not done today, but with these results we expect to have what we need shortly.)

Fair enough?

And we want to be able to read files into these arrays ala a=$(<filename) write them into files ala echo $a > filename, and to have similar bash-like read/write capabilities with pipes, also directly using with char** types, as C will perceive them to be.

This has all been accomplished in SList.cpp and .h in previous Mad Computer Science extravaganzas, but now we would like to do it with C++ templates... for no other reason than it sounds like some cool Computer Mad Science.

But wait. There's one additional constraint imposed by this nonsense, and that is that the class variables need to be contiguous with the data. That is, we cannot just create a class with a pointer to the data, because that would mess up attempts to case the C++ structure to C. So the header (as it were) must be tucked in at a lower address than lowest visible addresses of the data structure.

For example for a list of char** named "args" the "args" address would be the visible part of the data like so...

Code:

char** "args";

...but the the header is hidden UNDER this data like so...

Code:

HDR* hdr = (HDR*) args;  hdr = hdr - 1;

If you follow this code above, you'll see that hdr points sizeof(HDR) bytes BELOW the data that is above it.

The advantages of this system will become obvious. The practicality of doing it with templates? Well... That COULD be another story. And we're about to find that out.

file: src/main_1.cpp
purpose: source file

Code:

// looking at templates


#include <malloc.h>

void dbg(){}

// We'll start with the working code for an objlist (taken from previous 
// adventures in Computer Mad Science.

// And we'll convert the basic functions to type to T, as this will become 
// a class template type in the main_2.cpp.
typedef void* T;
typedef T* OBJLIST; // temporary def for conversion

// for detecting valid objlist derivatives
static const char* objlist_ID = "objlist";

typedef struct
{
  const char* id; // must be first field for valid id check.
  long n_items;   // small and beautiful, only two fields.
}OBJLIST_HDR;


// returns a pointer to the first (null) object in a new list.
OBJLIST objlist_new()
{
  OBJLIST_HDR* base = (OBJLIST_HDR*)malloc(sizeof(T) + sizeof(OBJLIST_HDR));
  base->id = objlist_ID;
  base->n_items = 0;
  base[1].id = 0;
  return (T*)&base[1].id;
}
// Note the decrementing of the pointer to point to the header 
// which is tucked below the data.
int objlist_count(OBJLIST* pData)
{
  return ((OBJLIST_HDR*)*pData)[-1].n_items;
}

// returns index of first item (always 0 if any items in the array, else -1.
int objlist_first(OBJLIST* plist)
{
  if(objlist_count(plist))
    return 0;
  else 
    return -1;
}

// returns index of last item (count -1), returns -1 if none.
int objlist_last(OBJLIST* plist)
{
  return objlist_count(plist) - 1;
}

// deletes only the base, classes using this must delete
// their own data, if necessary.
void objlist_delete(OBJLIST* plist)
{
  T* list = *plist;
  OBJLIST_HDR* base = ((OBJLIST_HDR*)list) - 1;
  free(base);
  *plist = 0;
}

// returns item at index
T objlist_get(OBJLIST* plist, int index)
{
  if(index >= objlist_count(plist))
    return 0;
  if(index < 0)
    return 0;
  return (*plist)[index];
}

// Zeros out the items, does not resize memory, delete objects
// or delete the base
void objlist_clear(OBJLIST* plist)
{
  int i; // loop index
  T* list = *plist;
  OBJLIST_HDR* base = ((OBJLIST_HDR*)list) -1;
  for(i = 0; i < base->n_items; i++)
    list[i] = 0;
  base->n_items = 0;
  *plist = list;
}


void objlist_append(OBJLIST* plist, T o)
{
  T* list = *plist;
  OBJLIST_HDR* base = ((OBJLIST_HDR*)list) -1;
  // add two below for new item plus terminator below
  int next_size = sizeof(OBJLIST_HDR) + (sizeof(T) * (base->n_items + 2) + sizeof(sizeof(OBJLIST_HDR)));
  base = (OBJLIST_HDR*)realloc(base, next_size);
  list = (T*)&base[1].id;
  list[base->n_items] = o;
  base->n_items++;
  list[base->n_items] = 0; // null last object, always
  *plist = list;
}

static void objlist_setCount(OBJLIST* plist, int n)
{
  ((OBJLIST_HDR*)*plist)[-1].n_items = n;
}

// removes (and frees) item at idx if any. Does not resize the list
void objlist_remove(OBJLIST* plist, int idx)
{
  int i; // loop index
  T* list = *plist;
  int n_items = objlist_count(plist);
  if((idx < 0) || (idx > n_items))
    return;
  
  for(i = idx; i < n_items; i++)
    list[i] = list[i+1];
  
  objlist_setCount(plist, n_items - 1);
}

// inserts new item at idx, or end or at beginning if out of range
void objlist_insert(OBJLIST* plist,  int idx, T o)
{ 
  int i; // loop index 

  // easiest to append and then to move
  objlist_append(plist, (void*)o);
  
  // get list after possible reallocation
  OBJLIST list = *plist;

  int n_items = objlist_count(plist);
  
  // check range 
  if(idx < 0)
    idx = 0;
  else if(idx >= n_items)
    idx = n_items - 1;
  
  if(idx == n_items - 1) 
    return;
  
  // grab the appended object, then shift the list up
  // and put the new object in at idx.
  void* tmp = (void*)list[n_items - 1];
  
  // point to last and copy prev to current and decrement
  for(i = n_items - 1; i > idx; i--)
    list[i] = list[i-1];
  list[idx] = tmp;
}

int main(int argc, char** argv)
{
  dbg();
  
  int n;
  T* whatever;
  whatever = objlist_new();
  printf("First we test the data as a list of objects.\n");
  
  // append test
  objlist_append(&whatever, (T)"this is the first string");
  objlist_append(&whatever, (T)"this is the third string");
  
  // insert test, put it at position 1, zero-based.
  objlist_insert(&whatever, 1, (T)"this is inserted as the second string");
  n = objlist_count(&whatever);
  for(int i = 0; i < n; i++)
    printf("d: s\n", i + 1, objlist_get(&whatever, i));
  
  printf("Next we test the data as a list of strings like an arg list.\n");
  
  for(int i = 0; whatever[i] != 0; i++)
    printf("d: s\n", i + 1, whatever[i]);

  // When the line below is commented out valgrind reports
  // that we lose 48 bytes though it is not accessible.
  
  objlist_delete(&whatever);

  return 0;
}

And here's the same thing converted now to templates which might make it more versatile due to now being a "generic" objlist. But even more generic than C with type casting? Let us proceed to find out.

file: src/main_2.cpp
purpose: source file

Code:

// looking at templates -- the moment of truth...

/*

The result of the test is that we discover only a few minor changes between the C 
definitions of the objlist in main_1.cpp and the C++ template version in main_2.cpp.
The compiler complains when we make mistakes and they are pretty easily fixed.

To see all the differences use a diff program.  And so now we're apparently clear to 
make even more strange creations, bearing in mind however, that the simple objlist
class has no way to delete members of the array that may have dynamically allocated 
memory.  For these tests, using string constants, ints or longs or whatever for 
the array elements there is nothing to delete when the array is collapsed.

The Computer Mad Science Team.

*/

#include <malloc.h>

void dbg(){}

// We'll start with the working code for an objlist (taken from previous 
// adventures in Computer Mad Science.

// And we'll convert the basic functions to type T, as this will become 
// a class template in the next main file.
//typedef void* T;
//typedef T* OBJLIST; // temporary def for conversion

// for detecting valid objlist derivatives
static const char* objlist_ID = "objlist";

typedef struct
{
  const char* id; // must be first field for valid id check.
  long n_items;   // small and beautiful, only two fields.
}OBJLIST_HDR;


// returns a pointer to the first (null) object in a new list.
template <class T>
T* objlist_new()
{
  OBJLIST_HDR* base = (OBJLIST_HDR*)malloc(sizeof(T) + sizeof(OBJLIST_HDR));
  base->id = objlist_ID;
  base->n_items = 0;
  base[1].id = 0;
  return (T*)&base[1].id;
}

// Note the decrementing of the pointer to point to the header 
// which is tucked below the data.
template <class T>
int objlist_count(T** pData)
{
  return ((OBJLIST_HDR*)*pData)[-1].n_items;
}

// returns index of first item (always 0 if any items in the array, else -1.
template <class T>
int objlist_first(T** plist)
{
  if(objlist_count(plist))
    return 0;
  else 
    return -1;
}

// returns index of last item (count -1), returns -1 if none.
template <class T>
int objlist_last(T** plist)
{
  return objlist_count(plist) - 1;
}

// deletes only the base, classes using this must delete
// their own data, if necessary.
template <class T>
void objlist_delete(T** plist)
{
  T* list = *plist;
  OBJLIST_HDR* base = ((OBJLIST_HDR*)list) - 1;
  free(base);
  *plist = 0;
}

// returns item at index
template <class T>
T objlist_get(T** plist, int index)
{
  if(index >= objlist_count(plist))
    return 0;
  if(index < 0)
    return 0;
  return (*plist)[index];
}

// Zeros out the items, does not resize memory, delete objects
// or delete the base
template <class T>
void objlist_clear(T** plist)
{
  int i; // loop index
  T* list = *plist;
  OBJLIST_HDR* base = ((OBJLIST_HDR*)list) -1;
  for(i = 0; i < base->n_items; i++)
    list[i] = 0;
  base->n_items = 0;
  *plist = list;
}

template <class T>
void objlist_append(T** plist, T o)
{
  T* list = *plist;
  OBJLIST_HDR* base = ((OBJLIST_HDR*)list) -1;
  // add two below for new item plus terminator below
  int next_size = sizeof(OBJLIST_HDR) + (sizeof(T) * (base->n_items + 2) + sizeof(sizeof(OBJLIST_HDR)));
  base = (OBJLIST_HDR*)realloc(base, next_size);
  list = (T*)&base[1].id;
  list[base->n_items] = o;
  base->n_items++;
  list[base->n_items] = 0; // null last object, always
  *plist = list;
}

template <class T>
static void objlist_setCount(T** plist, int n)
{
  ((OBJLIST_HDR*)*plist)[-1].n_items = n;
}

// removes (and frees) item at idx if any. Does not resize the list
template <class T>
void objlist_remove(T** plist, int idx)
{
  int i; // loop index
  T* list = *plist;
  int n_items = objlist_count(plist);
  if((idx < 0) || (idx > n_items))
    return;
  
  for(i = idx; i < n_items; i++)
    list[i] = list[i+1];
  
  objlist_setCount(plist, n_items - 1);
}

// inserts new item at idx, or end or at beginning if out of range
template <class T>
void objlist_insert(T** plist,  int idx, T o)
{ 
  int i; // loop index 

  // easiest to append and then to move
  objlist_append<T>(plist, o);
  
  // get list after possible reallocation
  T* list = *plist;

  int n_items = objlist_count(plist);
  
  // check range 
  if(idx < 0)
    idx = 0;
  else if(idx >= n_items)
    idx = n_items - 1;
  
  if(idx == n_items - 1) 
    return;
  
  // grab the appended object, then shift the list up
  // and put the new object in at idx.
  T tmp = list[n_items - 1];
  
  // point to last and copy prev to current and decrement
  for(i = n_items - 1; i > idx; i--)
    list[i] = list[i-1];
  list[idx] = tmp;
}



int main(int argc, char** argv)
{
  dbg();
  
  int n;
  //T* whatever;
  const char** whatever;
  whatever = objlist_new<const char*>();
  printf("First we test the data as a list of objects.\n");
  // append test
  objlist_append<const char*>(&whatever, "this is the first string");
  objlist_append<const char*>(&whatever, "this is the third string");
  // insert test, put it at position 1, zero-based.
  objlist_insert(&whatever, 1, "this is inserted as the second string");
  n = objlist_count(&whatever);
  for(int i = 0; i < n; i++)
    printf("d: %s\n", i + 1, objlist_get(&whatever, i));
  
  printf("\nNext we test the data as a list of strings like an arg list.\n");
  
  for(int i = 0; whatever[i] != 0; i++)
    printf("%d: %s\n", i + 1, whatever[i]);


  short* something; // now let's try a list of short integers, 16 bits in size.
  something = objlist_new<short>();
  objlist_append<short>(&something, 1111);
  objlist_append<short>(&something, 3333);
  objlist_insert<short>(&something, 1, 2222); // inserted at position 1, zero-based.
  
  printf("\nNext we test the data as an objlist (or expandable array) of short integers\n");
  
  for(int i = 0; i < objlist_count<short>(&something); i++)
    printf("%d: %d\n", i + 1, something[i]);
  
  printf("\nAnd as a short[i] array addressed by index i\n");
  
  for(int i = 0; something[i] != 0; i++)
    printf("%d: %d\n", i + 1, something[i]);

  printf("\nBut what if we create and call printf() on an array of chars, 'T'+'e'+'s'+'t'?\n");
  char* carray;
  carray = objlist_new<char>();
  objlist_append<char>(&carray, 'T');
  objlist_append<char>(&carray, 'e');
  objlist_append<char>(&carray, 's');
  objlist_append<char>(&carray, 't');
  
  printf("%s\n", carray);
  
  // When the lines below are commented out valgrind reports
  // that we lose lots of bytes are lost in three blocks.
  
  objlist_delete(&carray);
  objlist_delete(&whatever);
  objlist_delete(&something);
  
  return 0;
}

Well? Well?? What happens?
----------------------------------

Ok, here's the details.

The result of the test is that we discover only a few minor changes between the C definitions of the objlist in main_1.cpp and the C++ template version in main_2.cpp. The compiler complains when we make mistakes and they are pretty easily fixed.

Most of the mistakes/modifications came from having to tell the template call what type to treat <whatever> class as. That was stuff in the main() function.

And the corrections were an insert of the <classname> after the name of the function and before the parameter list. Yo ho! Things begin to make sense.

Other more minor issues were where we had cast to or from now no longer used types for which we were able to simply use the T template definition.

To see all the differences use a diff program. And so now we're apparently clear to make even more strange creations, bearing in mind however, that the simple objlist class has no way to delete members of the array that may have dynamically allocated memory. For these tests, using string constants, ints or longs or whatever for the array elements there is nothing to delete when the array is collapsed.

The Computer Mad Science Team.
:-)

file: mc2.def
purpose: creates Makefile with mc2 or mc2-multi (from previous experiment)

Code:

# mc2.def template created with Makefile Creator 'mc2'

# sandbox path and other new variables
PREFIX = $(HOME)/usr
BUILDDIR := $(PWD)

OUTNAME = MULTI

SRCDIR = src
OBJDIR = o

BINDIR = .

# what COMPILE should do
COMPILE = g++ -c -o # COMPILE <output_file> (for C, 32 bit, object)
 CFLAGS = -Wall -g3 # debug
# CFLAGS = -Wall -O2 # optimized
INCLUDE = -I $(SRCDIR) -I $(PREFIX)/include -I /usr/include 

# what LINK should do
LINK = g++ -o

# include a shotgun spread of libs here so all the files work
LDFLAGS = # -lLQ-qt
LIB = -L$(PREFIX)/lib -L/usr/lib 
 
semiclean: $(EXT_SEMICLEAN)
  @rm -f $(OBJ)
  @rm -f *~ */*~ */*/*~ */*/*/*~
  @rm -f *.kdevelop.filelist  *.kdevelop.pcs  *.kdevses Doxyfile

strip:
  @strip $(MAIN_FILES)
  @make semiclean

clean: $(EXT_CLEAN)
  @rm -f $(MAIN_FILES)
  @rm -f $(OBJ)
  @rm -f *.kdevelop.pcs *.kdevses
  @rm -f *~ */*~ */*/*~ */*/*/*~ tmp.mak
  

force: # used to force execution

file: Makefile.sfxz
purpose: self extracting Makefile run as 'sh Makefile.sfxz'

Code:

# run this as 'sh Makefile.sfxz' to extract the Makefile.
cat << _eof | base64 -d > Makefile.tar.xz
/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4BH/A+1dACaYSWZp2dmN5MBFtRePdUOjo4dtjvAfsZp8
QOWMi+VouNxbegkAknV2GVyjL3q5Uvroh8nsD2MBj43e8LYWvYUyZEG+naoF0wJ5Rzn3ze8aFieU
xX9u36X6X6wH53SqpC3mLigZPJZE8IJ5YvlgMvpBE5D2P+yiKuL3L7ZbO0wKHlzR8hzkkV+SKTKL
Ei0K4N6ZmxBDBjLU6mw645VSRmdG5D66dze/oznJgWe3c79qtp8kMGOttkcs4W/ADm7yTVXo/wPh
+GkwHbLDJF1yG1s+pEtbz8MmJtLX/o6KgVms5+ERuy7VyzisY7R1mD3VyBWXJ0sWytg9eH9fhM6Y
/fQugeW2w62zP9X9bDoWfasxGW7Q1pDI0wKOf7M6KhvA/dMk5mX3CfdLQQrLBClozU9wrd6FmK+n
ruiYRxG/FbwwPUreuNE/sLqTdEiRVYcmOvYriB5VFEKtjc5Vkiod+PdITBvwz2BSns1qccxMuhxN
a4qb/3Sjjuu08MHTaLnJQPekrDKB1e4OCWFPA/WEnTTCUCxQZBZWpTH9091DIZTYZFG+z9lCXi0C
DAaar0w7RFUqtDXosNVoKWxgYF/jEEGwGwVGZ5B9NfOYePCZ7i0IpTjBpBK4uoWXnj+ltTMjMUAb
gF+OlTgVqZNFZC/J+9BZEsz1DMVleNzPDQVEuPuOM4ltzkmqqADc5V74RcjHDBHJjFNbAS8fcaYk
y13yThZSFlfynGJHR8UY8245LdaYdCk7z3xHhWHKF5R+uhFtztxNfk9ViCSYrDqTU1y12g2RJsD4
9hA8E4DSfITdGjYcW1Ol9q0Hy6xw0lnchTpkQPbmr4Pgg7QBwUplBCC0R0KHSMaGffRRaVilvX5c
5XAytZf1NNKUk32fVltk+4DARnav5XdnzuJh8Qsaae68AzlNwUrfXRqGic8PfQnlLBAU+jfS3gzf
YXDfXpHvJ46BDRA4aCx7TbNnV/kvl5wVyPbeEY5G4qY3+VDStSrr2TfDqq6NQdAUKdtior3nP6F9
C/LcIHXaloIu+FIAqy3Di6i/54xJrVozO1q4qJw08oMONzoj2qkQxzNkwj7g5/jVStUHM5AcE5rq
eNsr4eJzje3bxjuur4Jvs7H67dwjG3pvQQAC6MHW2ze5ejxDAQ9JuBQ+i4afGEkY55J/oW3uflVI
kNd3xeJM2wVCuWxGOd5nAqSs7Rzqc6xX4DX14OjE/MeA1SJLjals3/BzWHuty0qRwJeYTEm6WGSd
sbZnwwYdt9KyMkrqJbx7LzSh3M3ZxSLsUMKCkQ1L1u67TtSKbQv+cppNvWzPgaZt3AC7iisJMbuK
9YCvDeQKYFcwAAAAAABWbiFrX978RgABiQiAJAAAC4KHGLHEZ/sCAAAAAARZWg==
_eof
tar -xaf Makefile.tar.xz
rm Makefile.tar.xz

An Experiment: From C Definitions To Templates

Comments