Stack of strings

Hi,

The attached files are for a library I've written to manage a stack (first-in, last-out) of six strings (i.e. six arrays of characters). Each string is 10 characters long.

The library works as expected, but it has a couple of shortcomings... a) The length of each string has to be decided at design-time, not run-time. (not a very big issue, I just change the value of maxWidth) b) The number of strings in the stack is an integral part of the code. If I want to increase the number of strings from six, to say ten, I need to hardcode changes to the header file and to edit most of the functions in the .cpp file.

It's not a big issue, but if I could I'd like to design the library so that the length and number of strings in the stack could be decided at runtime (maybe passed as parameters to the constructor) allowing greater flexibility.

To pre-empt a couple of issues, I've used char arrays not Strings because the great and the good on the forum seem to be a bit sniffy about their use, for reasons that I don't quite understand (something to do with memory management), Also I think I've been told in the past that the length of arrays should be decided at design time, not run time.

Cheers

would probably help if I included the files…

#ifndef MemStack_h                        // These lines (together with the #endif at the end of the file) prevent
#define MemStack_h                        // any problems occuring if this library should be included twice.

extern "C" {
  #include <string.h>
}

#include <stdlib.h>                        // needed for 'free'
#if defined(ARDUINO) && ARDUINO >= 100
#include "Arduino.h"                       // replacement for "WProgram.h" - required for versions after to 1.0.1
#else
#include "WProgram.h"                      // needed for 'Serial' - required for earlier versions
#endif
#include <avr/pgmspace.h>                  // Needed for PROGMAN stuff
#include <ProgmemConst.h>                  // Global progmem constants
#include <Log.h>                           // needed for Singlog2.h
#include <Misc.h>                          // needed for Log.h
#include <MiniTime.h>                      // needed for Log.h
#include <SingLog2.h>
#include <SdFileFunctions.h>               // requires SD.h
#include <SD.h>                            // New wrapper library for all the low level SD file functions. Replaces Sd2Card.h, FatStructs.h, Sd2PinMap.h, SdFat.h, SdFatmainpage.h, SdFatUtil.h, SdInfo.h

#define DEBUG_LOG                          // If defined, data will be writen to a logfile as well as displayed on screen

#define maxItems   6                      // Maximum number of strings (i.e. messages) stored in memory.
#define maxWidth   10+1                   // Width (i.e. length) of each element in the stack

class MemStack
{
  public:
    MemStack();                             // Constructor
    void begin(void);                       // Setup object
    void addNew(char *new_element);         // Add a new element (i.e. string) to the array
    void displayAll();                      // Display all the items in the array
    void removeItem(byte item);             // Remove a particular item from the stack (and then close the gap)
    char* getItem(byte item);               // Get an item from the array
    inline byte getSize(){return _stackCount;}      // Return number of items currently in stack
    inline byte getMaxSize(){return byte(maxItems);}// Return maximum size of stack
    inline byte getWidth(){return byte(maxWidth);}  // Return width of stack

  private:
    // Member variables
    char * _info;                           // Temporary storage used for holding strings (normally error messages) 
                                            // for logging to SD card.
    char item_01[maxWidth+1];
    char item_02[maxWidth+1];
    char item_03[maxWidth+1];
    char item_04[maxWidth+1];
    char item_05[maxWidth+1];
    char item_06[maxWidth+1];

    byte _stackCount;                      // Actual number of items currently in the stack


    // Private functions
    void leftShift();                      // Shift every element in the array one place to the left 
    void rightShift();                     // Shift every item in the array to the right.
    void logging(char * output);           // display to screen or file
                     
};

#endif

And the 2nd one…

extern "C" {
  #include <string.h>
}

#include <stdlib.h>                        // needed for 'free'
#if defined(ARDUINO) && ARDUINO >= 100
#include "Arduino.h"                       // replacement for "WProgram.h" - required for versions after to 1.0.1
#else
#include "WProgram.h"                      // needed for 'Serial' - required for earlier versions
#endif
#include "MemStack.h"                     // header for this library
#include <avr/pgmspace.h>                  // Needed for PROGMAN stuff
#include <ProgmemConst.h>
#include <Log.h>                           // needed for Singlog2.h
#include <Misc.h>                          // needed for Log.h
#include <MiniTime.h>                      // needed for Log.h
#include <SingLog2.h>
#include <SdFileFunctions.h>               // requires SD.h
#include <SD.h>                            // New wrapper library for all the low level SD file functions. Replaces Sd2Card.h, FatStructs.h, Sd2PinMap.h, SdFat.h, SdFatmainpage.h, SdFatUtil.h, SdInfo.h

#ifdef DEBUG_LOG
SingLog2 *logMemStack = SingLog2::GetLogger();  // Global (to this class) singleton logger.
#endif


/**************************************************************************
  Constructor
**************************************************************************/
MemStack::MemStack()
{
  _info = gMedBuff;                    // link the local info buffer to the global buffer (defined in ProgmemConst.cpp)
  _stackCount = 0;
}


/**************************************************************************
  Do stuff
**************************************************************************/
void MemStack::begin(void)                       
{
}


/**************************************************************************
  Add a new item to the stack. The new item ALLWAYS goes in position 01, 
**************************************************************************/
void MemStack::addNew(char *new_element)
{
  //add a new message to the array. Records will be added as they arrive from left to right.
  //therefore the rightmost fix should always be the most recent


  // Check that the string about to be added is no longer than the buffer.
  if (strlen(new_element) > maxWidth)
  {
    //"ERROR - Stack size is <%d> chars, new item being added is <%d> chars."
    sprintf_P(_info, ERR_STAK_11, maxWidth,strlen(new_element));
    logging(_info);
  }

  // Left-shift the entire stack
  leftShift();

  // copy the new item to the first position.
  strcpy(item_01,new_element);

  // if the stack isn't already full, increment the counter.
  if (_stackCount != maxItems)
  {
    _stackCount++;
  }
}


/**************************************************************************
  Get selected item from a stack
**************************************************************************/
char* MemStack::getItem(byte item)
{
  switch (item)
  {
    case 1:
      return item_01;
      break;
    case 2:
      return item_02;
      break;
    case 3:
      return item_03;
      break;
    case 4:
      return item_04;
      break;
    case 5:
      return item_05;
      break;
    case 6:
      return item_06;
      break;
  }
}


/**************************************************************************
  Remove an item from the stack
**************************************************************************/
void MemStack::removeItem(byte item)
{
  
  // check that the stacks not already empty.
  if (_stackCount !=0)
  {
    // Remove the selected item, and shuffle up the remaining items to remove the blank
    switch (item)
    {
      case 1:
        rightShift();
        break;
      case 2:
        strcpy(item_02,item_03);
        strcpy(item_03,item_04);
        strcpy(item_04,item_05);
        strcpy(item_05,item_06);
        _stackCount--;
        break;
      case 3:
        strcpy(item_03,item_04);
        strcpy(item_04,item_05);
        strcpy(item_05,item_06);
        _stackCount--;
        break;
      case 4:
        strcpy(item_04,item_05);
        strcpy(item_05,item_06);
        _stackCount--;
        break;
      case 5:
        strcpy(item_05,item_06);
        _stackCount--;
        break;
      case 6:
        item_06[0]=0;
        _stackCount--;
        break;
    }

    // Reset any empty slots in the stack to null 
    switch (_stackCount)
    {
      case 1:
        item_02[0]=0;
        item_03[0]=0;
        item_04[0]=0;
        item_05[0]=0;
        item_06[0]=0;
        break;
      case 2:
        item_03[0]=0;
        item_04[0]=0;
        item_05[0]=0;
        item_06[0]=0;
        break;
      case 3:
        item_04[0]=0;
        item_05[0]=0;
        item_06[0]=0;
        break;
      case 4:
        item_05[0]=0;
        item_06[0]=0;
        break;
      case 5:
        item_06[0]=0;
        break;
      case 6:
        // Should be impossible - one item has just been removed
        break;
    }
  }
}


/**************************************************************************
  Shift every item in the stack to the left. This is needed every time 
  a new item is added to the array.
**************************************************************************/
void MemStack::leftShift()
{
  //shift the entire contents of the SMS array left one element. The leftmost element will be lost and
  //a space will be freed up on the righthand side

  strcpy(item_06,item_05);
  strcpy(item_05,item_04);
  strcpy(item_04,item_03);
  strcpy(item_03,item_02);
  strcpy(item_02,item_01);

  item_01[0]=0;

  // if the stack was full, then an item will have been lost, so decrement the counter. 
  if (_stackCount == maxItems)
  {
    _stackCount--;                       
  }
}


/**************************************************************************
  Shift every item in the stack to the right. 
**************************************************************************/
void MemStack::rightShift()
{
  //shift the entire contents of the SMS array right one element. The rightmost element (01) will be lost and
  //a space will be freed up on the lefthand side (06)

  strcpy(item_01,item_02);
  strcpy(item_02,item_03);
  strcpy(item_03,item_04);
  strcpy(item_04,item_05);
  strcpy(item_05,item_06);

  item_06[0]=0;

  // if the stack was full, then an item will have been lost, so decrement the counter. 
  //if (_stackCount == maxItems)
  //{
    _stackCount--;                       
  //}
}


/**************************************************************************
  Display all the elements in the array
**************************************************************************/
void MemStack::displayAll()
{
  //display the whole list
  Serial.println("Stack....."); 
  Serial.print("1 <");Serial.print(item_01);Serial.println(">");
  Serial.print("2 <");Serial.print(item_02);Serial.println(">");
  Serial.print("3 <");Serial.print(item_03);Serial.println(">");
  Serial.print("4 <");Serial.print(item_04);Serial.println(">");
  Serial.print("5 <");Serial.print(item_05);Serial.println(">");
  Serial.print("6 <");Serial.print(item_06);Serial.println(">");
}


/************************************************************************************
  Simple function to either log messages to a logfile on the SD card or the
  screen (or both)
************************************************************************************/
void MemStack::logging(char * output)
{
#ifdef DEBUG_LOG
  logMemStack->writeLn(output);
#else
  Serial.println(output);
#endif
}

Also I think I’ve been told in the past that the length of arrays should be decided at design time, not run time.

Because the Arduino has limited memory, dynamic memory allocation is generally not that great an idea.

b) The number of strings in the stack is an integral part of the code. If I want to increase the number of strings from six, to say ten, I need to hardcode changes to the header file and to edit most of the functions in the .cpp file.

Then, you are doing something wrong. Changing the header file might be required, but NO changes to the source file should be needed.

Using arrays instead of named variables would go a long ways towards solving that issue. Rather than shuffling strings around, you should be shuffling pointers.

Rather than shuffling strings around, you should be shuffling pointers.

Yes, but like a lot of intermediate developers I find working with pointers gives me brain strain!

Also, even if I could re-write it based on shuffling pointers around instead of strings, I'm still left with the problem that

dynamic memory allocation is generally not that great an idea.

Which brings me back to the original issue that it seems I must decide the size of each string in the stack, and the number of strings in the stack at design time.

Thanks

Yes, but like a lot of intermediate developers I find working with pointers gives me brain strain!

Suppose the strings were written on 3x5 cards. You want to remove the string on the first card. Do you erase the text on that card, and copy the data on the next card to the first card, and then erase the text on the second card, and write the text on the third card to the second card, etc.? Or, do you simply throw away the first card?

The program you have now has fixed cards. You are shuffling the data around on the cards.

The cards themselves are pointers to the strings. Toss a card, and move the others around. It's a lot simpler.

Your class should not own the data. The using program should own the data. Your class should be dealing just with the itty-bitty pointers, not the huge strings pointed to. Your stack class should be able to handle 50 pointers easily. The data pointed to is the using program's responsibility to maintain.

A doubly linked list requires 4 pointers - one to the previous instance, one to the next instance, one for the current instance, and one to the string. Dynamically allocating 8 bytes, even a hundred times, might not have a huge performance impact.

You can make your class responsible for the data or just for the pointers. Your choice, but I know which is easier.

Personally, when I have a class / function that needs to work on a buffer or block of data whose size is subject to change on a per-program basis, I usually leave it up to the user's program to allocate the data space, then pass a pointer to that to the class / function. It's trivial for the user to create a 2 dimensional array of characters, then pass that to the constructor (or begin() function) of your class along with the dimensions of that array. That way you are always working within a statically allocated block of memory and avoid any dynamic allocation problems.

OhMyCod: It's not a big issue, but if I could I'd like to design the library so that the length and number of strings in the stack could be decided at runtime (maybe passed as parameters to the constructor) allowing greater flexibility.

This needs a bit more clarification, as you mention "passed as parameters to the constructor", do you intend it to be as majenko says and have the string length and count determined on a per-program basis, or you want to use many unequal sized stacks.

Because if you want it per-program, templates will solve this problem easily, otherwise there are alternatives like a maximum buffer size, or very careful dynamic memory usage, which as of 1.0.4 free() has been fixed resulting in a reasonably stable, but not a fool proof memory allocator.