J
jacob navia
This is the first part of this posting. This is the header file
containers.h
--------------------------------------------------------cut here
#ifndef __containers_h__
#define __containers_h__
#include <string.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
/*
A string collection is a table of zero terminated strings that will grow
automatically when you add elements to it.
As all other containers in this proposal, it uses an interface, i.e. a
table
of functions to provide the functionality and data access a string
collection
needs. Since the names of the functions are enclosed within the interface
structure we can use mnemonic names like Add, etc, without fear of
messing with
the user name space, and without adding lengthy prefixes.
Other advantage of an interface are the extensibility of it. You can add
functions of your own to the interface without interfering with the existing
ones. We will discuss this later when we discuss subclassing, but it is
obvious
that you can define a new interface that has the first members as the given
interface, but it has some extra members of your own.
*/
/* We define first an empty structure, that will be fully defined later,
to be
able to define the functions in our interface
*/
typedef struct _StringCollection StringCollection;
struct _StringEnumerator;
// Type definition of the compare function
typedef int (*CompareFunction)(void *elem1,void *elem2);
// Definition of the functions associated with this type.
typedef struct {
// Returns the number of elements stored
int (*GetCount)(StringCollection SC);
// Is this collection read only?
int (*IsReadOnly)(StringCollection SC);
// Sets this collection read-only or unsets the read-only flag
int (*SetReadOnly)(StringCollection SC,int flag);
// Adds one element at the end. Given string is copied
int (*Add)(StringCollection SC,char *newval);
// Adds a NULL terminated table of strings
int (*AddRange)(StringCollection SC,char **newvalues);
// Clears all data and frees the memory
int (*Clear)(StringCollection SC);
//Case sensitive search of a character string in the data
bool (*Contains)(StringCollection SC,char *str);
// Copies all strings into a NULL terminated vector
char **(*CopyTo)(StringCollection SC);
//Returns the index of the given string or -1 if not found
int (*IndexOf)(StringCollection SC,char *SearchedString);
// Inserts a string at the position zero.
int (*Insert)(StringCollection SC,char *);
// Inserts a string at the given position
int (*InsertAt)(StringCollection SC,int idx,char *newval);
// Returns the string at the given position
char *(*IndexAt)(StringCollection SC,int idx);
// Removes the given string if found
int (*Remove)(StringCollection SC,char *);
//Removes the string at the indicated position
int (*RemoveAt)(StringCollection SC,int idx);
// Frees the memory used by the collection
int (*Finalize)(StringCollection SC);
// Returns the current capacity of the collection
int (*GetCapacity)(StringCollection SC);
// Sets the capacity if there are no items in the collection
bool (*SetCapacity)(StringCollection SC,int newCapacity);
// Calls the given function for all strings. "Arg" is a used supplied
argument
// that can be NULL that is passed to the function to call
void (*Apply)(StringCollection SC,int (*Applyfn)(char *,void *
arg),void *arg);
// Calls the given function for each string and saves all results
// in an integer vector
int *(*Map)(StringCollection SC,int (*Applyfn)(char *));
// Pushes a string, using the collection as a stack
int (*Push)(StringCollection SC,char *str);
// Pops the last string off the collection
char * (*Pop)(StringCollection SC);
// Replaces the character string at the given position with a new one
char *(*ReplaceAt)(StringCollection SC,int idx,char *newval);
// Returns whether the collection makes case sensitive comparisons or not
int (*IsCaseSensitive)(StringCollection SC);
// Sets case sensitivity by comparisons
int (*SetCaseSensitive)(StringCollection SC,int newval);
// Compares two string collections
bool (*Equal)(StringCollection SC1,StringCollection SC2);
// Copy a string collection
StringCollection (*Copy)(StringCollection SC);
} StringCollectionInterface;
/*
Note that this lengthy structure is not replicated at each string collection
object. Each string collection holds just a pointer to it, spending only
sizeof(void *) bytes.
*/
// Definition of the String Collection type
struct _StringCollection {
StringCollectionInterface *lpVtbl; // The table of functions
int count; /* in element size units */
char **contents; /* The contents of the collection */
int capacity; /* in element_size units */
unsigned int flags; // Read-only or other flags
};
struct _StringEnumerator;
typedef struct _StringEnumeratorFunctions {
int (*Next)(struct _StringEnumerator *);
int (*Previous)(struct _StringEnumerator *);
char *(*GetCurrent)(struct _StringEnumerator *);
int (*SetCurrent)(struct _StringEnumerator *,int);
} StringEnumeratorFunctions;
typedef struct _StringEnumerator {
StringEnumeratorFunctions *lpVtbl;
StringCollection SC;
int CurrentIndex;
} StringEnumerator;
// This are the only exported functions from this module
StringCollection newStringCollection(int startsize);
#if 0
char *operator[](StringCollection *,int);
char *operator[]=(StringCollection SC,int idx,char *newval);
#endif
/* ------------------------------------------------------------------------
* LIST Interface
*
* This describes the single linked list data structure functions
*
* Each list objects has a list composed of list elemants.
*
*-------------------------------------------------------------------------*/
typedef struct _list_element {
struct _list_element *Next;
char Data[];
} list_element;
typedef struct _List List;
typedef struct {
// Returns the number of elements stored
int (*GetCount)(List AL);
// Is this collection read only?
int (*IsReadOnly)(List AL);
// Sets this collection read-only or unsets the read-only flag
int (*SetReadOnly)(List AL,int flag);
// Adds one element at the end. Given element is copied
int (*Add)(List AL,void *newval);
// Clears all data and frees the memory
int (*Clear)(List AL);
//Case sensitive search of a character string in the data
bool (*Contains)(List AL,void *str);
// Copies all strings into a NULL terminated vector
List (*Copy)(List AL);
//Returns the index of the given string or -1 if not found
int (*IndexOf)(List AL,void *SearchedElement);
// Inserts a value at the position zero.
int (*Insert)(List AL,void *);
// Inserts a value at the given position
int (*InsertAt)(List AL,int idx,void *newval);
// Returns the list at the given position
void *(*IndexAt)(List AL,int idx);
// Removes the given string if found
int (*Remove)(List AL,void *);
//Removes the string at the indicated position
int (*RemoveAt)(List AL,int idx);
// Frees the memory used by the collection
int (*Finalize)(List AL);
// Pushes a string, using the collection as a stack
int (*Push)(List AL,void *str);
// Pops the last string off the list
list_element * (*Pop)(List AL);
// Replaces the character string at the given position with a
new one
void *(*ReplaceAt)(List AL,int idx,void *newval);
// Sorts the list
List (*Sort)(List l,int (*compar)(const void *,const void *));
// Reverses the list
List (*Reverse)(List l);
// Gets an element range from the list
List (*GetRange)(List l,int start,int end);
// Compares two list (Shallow comparison)
bool (*Equal)(List l1,List l2);
// Add a list at the end of another
List (*Append)(List l1,List l2);
// Comparison function
int (*CompareFn)(void * elem1, void *elem2);
// Set The comparison function
CompareFunction (*SetCompareFunction)(List l,CompareFunction fn);
} ListInterface;
struct _List {
ListInterface *lpVtbl;
size_t ElementSize;
int count; /* in elements units */
list_element *Last; /* The last item */
list_element *First; /* The contents of the list start
here */
unsigned Flags;
};
List newList(int element_size);
#if 0
list_element * operator[]=(List &l,size_t position,void *data);
list_element * operator[](List &l,int position);
#endif
/*-------------------------------------------------------------------------
* inline functions
*------------------------------------------------------------------------*/
list_element *inline GetFirst(List *l)
{
return l->First;
}
list_element * inline GetNext(list_element *l)
{
return l->Next;
}
list_element * inline GetLast(List *l)
{
return l->Last;
}
/*****************************************************************************
*
*
* The array list
*
* We have now a general framework for handling string collections.
Looking
* at the code, it is easy to see that with a little effort, we could
make
* this much more general if we would replace the strings with a fixed
size
* object, that can be any data structure. This general container is
present
* in other languages like C#, where it is called ArrayList. You can
store
* in an ArrayList anything, in C# it is not even required that the
objects
* stored inside should be of the same type.
* Since the nature of the objects stored is not known to the container,
* it is necessary to cast the result of an ArrayList into the final type
* that the user knows it is in there. In C# this is the object, the root
* of the object hierarchy, in C it is the void pointer, a pointer
that can
* point to any kind of object.
* If we look at the code of one of the string collection functions we
can
* see the following:
* static char *IndexAt(struct _StringCollection *SC,int idx)
* {
* if (idx >=SC.count || idx < 0)
* return NULL;
* return SC.contents[idx];
* }
* We can easily generalize this to a container by changing the char
pointer
* result declaration to just a void pointer.
****************************************************************************/
// Forward declaration of the string collection type
typedef struct _ArrayList ArrayList;
// Definition of the functions associated with this type.
typedef struct {
// Returns the number of elements stored
int (*GetCount)(ArrayList *AL);
// Is this collection read only?
int (*IsReadOnly)(ArrayList *AL);
// Sets this collection read-only or unsets the read-only flag
int (*SetReadOnly)(ArrayList *AL,int flag);
// Adds one element at the end. Given element is copied
int (*Add)(ArrayList *AL,void *newval);
// Adds a NULL terminated table of strings
int (*AddRange)(ArrayList *AL,void **newvalues);
// Clears all data and frees the memory
int (*Clear)(ArrayList *AL);
//Case sensitive search of a character string in the data
bool (*Contains)(ArrayList *AL,void *str);
// Copies all strings into a NULL terminated vector
void **(*CopyTo)(ArrayList *AL);
//Returns the index of the given string or -1 if not found
int (*IndexOf)(ArrayList *AL,void *SearchedString);
// Inserts a string at the position zero.
int (*Insert)(ArrayList *AL,void *);
// Inserts a string at the given position
int (*InsertAt)(ArrayList *AL,int idx,void *newval);
// Returns the string at the given position
void *(*IndexAt)(ArrayList *AL,int idx);
// Removes the given string if found
int (*Remove)(ArrayList *AL,void *);
//Removes the string at the indicated position
int (*RemoveAt)(ArrayList *AL,int idx);
// Frees the memory used by the collection
int (*Finalize)(ArrayList *AL);
// Returns the current capacity of the collection
int (*GetCapacity)(ArrayList *AL);
// Sets the capacity if there are no items in the collection
bool (*SetCapacity)(ArrayList *AL,int newCapacity);
// Calls the given function for all strings. "Arg" is a used supplied
argument
// that can be NULL that is passed to the function to call
void (*Apply)(ArrayList *AL,int (*Applyfn)(void *,void * arg),void *arg);
// Pushes a string, using the collection as a stack
int (*Push)(ArrayList *AL,void *str);
// Pops the last string off the collection
void * (*Pop)(ArrayList *AL);
// Replaces the character string at the given position with a new one
void *(*ReplaceAt)(ArrayList *AL,int idx,void *newval);
} ArrayListInterface;
// Definition of the String Collection type
struct _ArrayList {
ArrayListInterface *lpVtbl; // The table of functions
int count; /* number of elements in the array */
void **contents; /* The contents of the collection */
int capacity; /* allocated space in the contents
vector */
unsigned int flags; // Read-only or other flags
size_t ElementSize; // Size of the elements stored in this array.
};
// This are the only exported functions from this module
ArrayList newArrayList(size_t elementsize,int startsize);
#if 0
void *operator[](ArrayList AL,int idx);
void *operator[]=(ArrayList AL,int idx,void *newval);
#endif
//******************************************************************************
//
// ErrorHandling
//
//******************************************************************************
#define CONTAINER_ERROR_BADARG (0x80070057)
#define CONTAINER_ERROR_NOMEMORY (0x8007000E)
#define CONTAINER_ERROR_INDEX -3
#define CONTAINER_ERROR_READONLY -4
#define CONTAINER_ERROR_FILEOPEN -5
void ContainerRaiseError(char *fnname,unsigned errorcode);
#endif
containers.h
--------------------------------------------------------cut here
#ifndef __containers_h__
#define __containers_h__
#include <string.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
/*
A string collection is a table of zero terminated strings that will grow
automatically when you add elements to it.
As all other containers in this proposal, it uses an interface, i.e. a
table
of functions to provide the functionality and data access a string
collection
needs. Since the names of the functions are enclosed within the interface
structure we can use mnemonic names like Add, etc, without fear of
messing with
the user name space, and without adding lengthy prefixes.
Other advantage of an interface are the extensibility of it. You can add
functions of your own to the interface without interfering with the existing
ones. We will discuss this later when we discuss subclassing, but it is
obvious
that you can define a new interface that has the first members as the given
interface, but it has some extra members of your own.
*/
/* We define first an empty structure, that will be fully defined later,
to be
able to define the functions in our interface
*/
typedef struct _StringCollection StringCollection;
struct _StringEnumerator;
// Type definition of the compare function
typedef int (*CompareFunction)(void *elem1,void *elem2);
// Definition of the functions associated with this type.
typedef struct {
// Returns the number of elements stored
int (*GetCount)(StringCollection SC);
// Is this collection read only?
int (*IsReadOnly)(StringCollection SC);
// Sets this collection read-only or unsets the read-only flag
int (*SetReadOnly)(StringCollection SC,int flag);
// Adds one element at the end. Given string is copied
int (*Add)(StringCollection SC,char *newval);
// Adds a NULL terminated table of strings
int (*AddRange)(StringCollection SC,char **newvalues);
// Clears all data and frees the memory
int (*Clear)(StringCollection SC);
//Case sensitive search of a character string in the data
bool (*Contains)(StringCollection SC,char *str);
// Copies all strings into a NULL terminated vector
char **(*CopyTo)(StringCollection SC);
//Returns the index of the given string or -1 if not found
int (*IndexOf)(StringCollection SC,char *SearchedString);
// Inserts a string at the position zero.
int (*Insert)(StringCollection SC,char *);
// Inserts a string at the given position
int (*InsertAt)(StringCollection SC,int idx,char *newval);
// Returns the string at the given position
char *(*IndexAt)(StringCollection SC,int idx);
// Removes the given string if found
int (*Remove)(StringCollection SC,char *);
//Removes the string at the indicated position
int (*RemoveAt)(StringCollection SC,int idx);
// Frees the memory used by the collection
int (*Finalize)(StringCollection SC);
// Returns the current capacity of the collection
int (*GetCapacity)(StringCollection SC);
// Sets the capacity if there are no items in the collection
bool (*SetCapacity)(StringCollection SC,int newCapacity);
// Calls the given function for all strings. "Arg" is a used supplied
argument
// that can be NULL that is passed to the function to call
void (*Apply)(StringCollection SC,int (*Applyfn)(char *,void *
arg),void *arg);
// Calls the given function for each string and saves all results
// in an integer vector
int *(*Map)(StringCollection SC,int (*Applyfn)(char *));
// Pushes a string, using the collection as a stack
int (*Push)(StringCollection SC,char *str);
// Pops the last string off the collection
char * (*Pop)(StringCollection SC);
// Replaces the character string at the given position with a new one
char *(*ReplaceAt)(StringCollection SC,int idx,char *newval);
// Returns whether the collection makes case sensitive comparisons or not
int (*IsCaseSensitive)(StringCollection SC);
// Sets case sensitivity by comparisons
int (*SetCaseSensitive)(StringCollection SC,int newval);
// Compares two string collections
bool (*Equal)(StringCollection SC1,StringCollection SC2);
// Copy a string collection
StringCollection (*Copy)(StringCollection SC);
} StringCollectionInterface;
/*
Note that this lengthy structure is not replicated at each string collection
object. Each string collection holds just a pointer to it, spending only
sizeof(void *) bytes.
*/
// Definition of the String Collection type
struct _StringCollection {
StringCollectionInterface *lpVtbl; // The table of functions
int count; /* in element size units */
char **contents; /* The contents of the collection */
int capacity; /* in element_size units */
unsigned int flags; // Read-only or other flags
};
struct _StringEnumerator;
typedef struct _StringEnumeratorFunctions {
int (*Next)(struct _StringEnumerator *);
int (*Previous)(struct _StringEnumerator *);
char *(*GetCurrent)(struct _StringEnumerator *);
int (*SetCurrent)(struct _StringEnumerator *,int);
} StringEnumeratorFunctions;
typedef struct _StringEnumerator {
StringEnumeratorFunctions *lpVtbl;
StringCollection SC;
int CurrentIndex;
} StringEnumerator;
// This are the only exported functions from this module
StringCollection newStringCollection(int startsize);
#if 0
char *operator[](StringCollection *,int);
char *operator[]=(StringCollection SC,int idx,char *newval);
#endif
/* ------------------------------------------------------------------------
* LIST Interface
*
* This describes the single linked list data structure functions
*
* Each list objects has a list composed of list elemants.
*
*-------------------------------------------------------------------------*/
typedef struct _list_element {
struct _list_element *Next;
char Data[];
} list_element;
typedef struct _List List;
typedef struct {
// Returns the number of elements stored
int (*GetCount)(List AL);
// Is this collection read only?
int (*IsReadOnly)(List AL);
// Sets this collection read-only or unsets the read-only flag
int (*SetReadOnly)(List AL,int flag);
// Adds one element at the end. Given element is copied
int (*Add)(List AL,void *newval);
// Clears all data and frees the memory
int (*Clear)(List AL);
//Case sensitive search of a character string in the data
bool (*Contains)(List AL,void *str);
// Copies all strings into a NULL terminated vector
List (*Copy)(List AL);
//Returns the index of the given string or -1 if not found
int (*IndexOf)(List AL,void *SearchedElement);
// Inserts a value at the position zero.
int (*Insert)(List AL,void *);
// Inserts a value at the given position
int (*InsertAt)(List AL,int idx,void *newval);
// Returns the list at the given position
void *(*IndexAt)(List AL,int idx);
// Removes the given string if found
int (*Remove)(List AL,void *);
//Removes the string at the indicated position
int (*RemoveAt)(List AL,int idx);
// Frees the memory used by the collection
int (*Finalize)(List AL);
// Pushes a string, using the collection as a stack
int (*Push)(List AL,void *str);
// Pops the last string off the list
list_element * (*Pop)(List AL);
// Replaces the character string at the given position with a
new one
void *(*ReplaceAt)(List AL,int idx,void *newval);
// Sorts the list
List (*Sort)(List l,int (*compar)(const void *,const void *));
// Reverses the list
List (*Reverse)(List l);
// Gets an element range from the list
List (*GetRange)(List l,int start,int end);
// Compares two list (Shallow comparison)
bool (*Equal)(List l1,List l2);
// Add a list at the end of another
List (*Append)(List l1,List l2);
// Comparison function
int (*CompareFn)(void * elem1, void *elem2);
// Set The comparison function
CompareFunction (*SetCompareFunction)(List l,CompareFunction fn);
} ListInterface;
struct _List {
ListInterface *lpVtbl;
size_t ElementSize;
int count; /* in elements units */
list_element *Last; /* The last item */
list_element *First; /* The contents of the list start
here */
unsigned Flags;
};
List newList(int element_size);
#if 0
list_element * operator[]=(List &l,size_t position,void *data);
list_element * operator[](List &l,int position);
#endif
/*-------------------------------------------------------------------------
* inline functions
*------------------------------------------------------------------------*/
list_element *inline GetFirst(List *l)
{
return l->First;
}
list_element * inline GetNext(list_element *l)
{
return l->Next;
}
list_element * inline GetLast(List *l)
{
return l->Last;
}
/*****************************************************************************
*
*
* The array list
*
* We have now a general framework for handling string collections.
Looking
* at the code, it is easy to see that with a little effort, we could
make
* this much more general if we would replace the strings with a fixed
size
* object, that can be any data structure. This general container is
present
* in other languages like C#, where it is called ArrayList. You can
store
* in an ArrayList anything, in C# it is not even required that the
objects
* stored inside should be of the same type.
* Since the nature of the objects stored is not known to the container,
* it is necessary to cast the result of an ArrayList into the final type
* that the user knows it is in there. In C# this is the object, the root
* of the object hierarchy, in C it is the void pointer, a pointer
that can
* point to any kind of object.
* If we look at the code of one of the string collection functions we
can
* see the following:
* static char *IndexAt(struct _StringCollection *SC,int idx)
* {
* if (idx >=SC.count || idx < 0)
* return NULL;
* return SC.contents[idx];
* }
* We can easily generalize this to a container by changing the char
pointer
* result declaration to just a void pointer.
****************************************************************************/
// Forward declaration of the string collection type
typedef struct _ArrayList ArrayList;
// Definition of the functions associated with this type.
typedef struct {
// Returns the number of elements stored
int (*GetCount)(ArrayList *AL);
// Is this collection read only?
int (*IsReadOnly)(ArrayList *AL);
// Sets this collection read-only or unsets the read-only flag
int (*SetReadOnly)(ArrayList *AL,int flag);
// Adds one element at the end. Given element is copied
int (*Add)(ArrayList *AL,void *newval);
// Adds a NULL terminated table of strings
int (*AddRange)(ArrayList *AL,void **newvalues);
// Clears all data and frees the memory
int (*Clear)(ArrayList *AL);
//Case sensitive search of a character string in the data
bool (*Contains)(ArrayList *AL,void *str);
// Copies all strings into a NULL terminated vector
void **(*CopyTo)(ArrayList *AL);
//Returns the index of the given string or -1 if not found
int (*IndexOf)(ArrayList *AL,void *SearchedString);
// Inserts a string at the position zero.
int (*Insert)(ArrayList *AL,void *);
// Inserts a string at the given position
int (*InsertAt)(ArrayList *AL,int idx,void *newval);
// Returns the string at the given position
void *(*IndexAt)(ArrayList *AL,int idx);
// Removes the given string if found
int (*Remove)(ArrayList *AL,void *);
//Removes the string at the indicated position
int (*RemoveAt)(ArrayList *AL,int idx);
// Frees the memory used by the collection
int (*Finalize)(ArrayList *AL);
// Returns the current capacity of the collection
int (*GetCapacity)(ArrayList *AL);
// Sets the capacity if there are no items in the collection
bool (*SetCapacity)(ArrayList *AL,int newCapacity);
// Calls the given function for all strings. "Arg" is a used supplied
argument
// that can be NULL that is passed to the function to call
void (*Apply)(ArrayList *AL,int (*Applyfn)(void *,void * arg),void *arg);
// Pushes a string, using the collection as a stack
int (*Push)(ArrayList *AL,void *str);
// Pops the last string off the collection
void * (*Pop)(ArrayList *AL);
// Replaces the character string at the given position with a new one
void *(*ReplaceAt)(ArrayList *AL,int idx,void *newval);
} ArrayListInterface;
// Definition of the String Collection type
struct _ArrayList {
ArrayListInterface *lpVtbl; // The table of functions
int count; /* number of elements in the array */
void **contents; /* The contents of the collection */
int capacity; /* allocated space in the contents
vector */
unsigned int flags; // Read-only or other flags
size_t ElementSize; // Size of the elements stored in this array.
};
// This are the only exported functions from this module
ArrayList newArrayList(size_t elementsize,int startsize);
#if 0
void *operator[](ArrayList AL,int idx);
void *operator[]=(ArrayList AL,int idx,void *newval);
#endif
//******************************************************************************
//
// ErrorHandling
//
//******************************************************************************
#define CONTAINER_ERROR_BADARG (0x80070057)
#define CONTAINER_ERROR_NOMEMORY (0x8007000E)
#define CONTAINER_ERROR_INDEX -3
#define CONTAINER_ERROR_READONLY -4
#define CONTAINER_ERROR_FILEOPEN -5
void ContainerRaiseError(char *fnname,unsigned errorcode);
#endif
