A container library in C. Part 2: String collection implementation

J

jacob navia

This is the implementation part of the string collection container

------------------------------------------------------------------

#include <string.h>
#include "strcollection.h"

#ifndef MALLOC
#include <stdlib.h>
#define MALLOC(s) malloc(s)
#define FREE(p) free(p)
#endif

// Forward definitions
static int GetCount(StringCollection *SC);
static int IsReadOnly(StringCollection *SC);
static int SetReadOnly(StringCollection *SC, int newval);
static int Add(StringCollection *SC, const char *newval);
static int AddRange(StringCollection *SC, const char * const *newvalues);
static int Clear(StringCollection *SC);
static int Contains(StringCollection *SC, const char *str);
static char **CopyTo(StringCollection *SC);
static int IndexOf(StringCollection *SC, const char *SearchedString);
static int Insert(StringCollection *SC, const char *str);
static int InsertAt(StringCollection *SC, int idx, const char *newval);
static char *IndexAt(StringCollection *SC, int idx);
static int Remove(StringCollection *SC, const char *str);
static int RemoveAt(StringCollection *SC, int idx);
static int Finalize(StringCollection *SC);
static int GetCapacity(StringCollection *SC);
static int SetCapacity(StringCollection *SC, int newCapacity);
static void Apply(StringCollection *SC,
int(*Applyfn)(char *str, void *arg), void *arg);
static int *Map(StringCollection *SC, int (*Applyfn)(char *str));
static int Push(StringCollection *SC, const char *str);
static char *Pop(StringCollection *SC);
static char *ReplaceAt(StringCollection *SC, int idx, const char *str);
static StringCollectionFunctions lpVtableSC = {
GetCount, IsReadOnly, SetReadOnly, Add, AddRange,
Clear, Contains, CopyTo, IndexOf, Insert,
InsertAt, IndexAt, Remove, RemoveAt,
Finalize, GetCapacity, SetCapacity, Apply,
Map, Push, Pop, ReplaceAt,
};

static char *DuplicateString(const char *str)
{
char *result;

if (str == NULL)
return NULL;
result = MALLOC(strlen(str) + 1);
if (result == NULL)
return NULL;
return strcpy(result, str);
}

#define SC_READONLY 1
#define CHUNKSIZE 20
#define DEFAULT_START_SIZE 0

StringCollection *newStringCollection(int startsize)
{
StringCollection *SC = MALLOC(sizeof(*SC));

if (SC == NULL)
return NULL;

SC->lpVtbl = &lpVtableSC;
SC->count = 0;
SC->contents = NULL;
SC->capacity = 0;
SC->flags = 0;

if (startsize == 0)
startsize = DEFAULT_START_SIZE;
if (startsize) {
SC->capacity = startsize;
SC->contents = MALLOC(startsize * sizeof(*SC->contents));
if (SC->contents == NULL) {
FREE(SC);
return NULL;
}
// useless, for cleanliness only
memset(SC->contents, 0, startsize * sizeof(*SC->contents));
}
return SC;
}

static int GetCount(StringCollection *SC)
{
return SC->count;
}

static int IsReadOnly(StringCollection *SC)
{
return (SC->flags & SC_READONLY) ? 1 : 0;
}

static int SetReadOnly(StringCollection *SC, int newval)
{
int oldval = (SC->flags & SC_READONLY) ? 1 : 0;

if (newval)
SC->flags |= SC_READONLY;
else
SC->flags &= ~SC_READONLY;
return oldval;
}

static int Resize(StringCollection *SC)
{
int newcapacity = SC->capacity + CHUNKSIZE;
char **newcontents;

newcontents = MALLOC(newcapacity * sizeof(*newcontents));
if (newcontents == NULL)
return 0;
memcpy(newcontents, SC->contents, SC->count * sizeof(*newcontents));
// useless, for cleanliness only
memset(newcontents + SC->count * sizeof(*newcontents),
0, (newcapacity - SC->count) * sizeof(*newcontents));
FREE(SC->contents);
SC->contents = newcontents;
SC->capacity = newcapacity;
return 1;
}

static int Add(StringCollection *SC, const char *str)
{
char *newval = NULL;

if (SC->flags & SC_READONLY)
return -1;
if (SC->count >= SC->capacity) {
if (!Resize(SC))
return 0;
}
if (str) {
newval = DuplicateString(str);
if (newval == NULL)
return 0;
}
SC->contents[SC->count] = newval;
return ++SC->count;
}

static int AddRange(StringCollection *SC, const char * const *data)
{
int i;

if (SC->flags & SC_READONLY)
return 0;
for (i = 0; data != NULL; i++) {
int r = Add(SC, data);
if (r <= 0)
return r;
}
return SC->count;
}

static int Clear(StringCollection *SC)
{
int oldval = SC->count, i;

if (SC->flags & SC_READONLY)
return 0;
for (i = 0; i < SC->count; i++) {
FREE(SC->contents);
SC->contents = NULL;
}
SC->count = 0;
return oldval;
}

static int Contains(StringCollection *SC, const char *str)
{
return (IndexOf(SC, str) >= 0);
}

static char **CopyTo(StringCollection *SC)
{
char **result = MALLOC((SC->count + 1) * sizeof(*result));
int i;

if (result == NULL)
return NULL;
for (i = 0; i < SC->count; i++) {
// XXX: MALLOC failure ignored
result = DuplicateString(SC->contents);
}
result = NULL;
return result;
}

#ifdef __LCC__
/* The lcc-win compiler allows operator overloading, and allows using
this abstract data type with the more natural [ ] operators */
char * __declspec(naked) operator[](StringCollection *SC, int idx)
{
}
#endif

static int IndexOf(StringCollection *SC, const char *str)
{
int c, i;

if (str == NULL) {
for (i = 0; i < SC->count; i++) {
if (SC->contents == NULL)
return i;
}
return -1;
} else {
c = *str;
for (i = 0; i < SC->count; i++) {
if (SC->contents == NULL)
continue;
if (c == SC->contents[0] && !strcmp(SC->contents, str))
return i;
}
return -1;
}
}

static char *IndexAt(StringCollection *SC, int idx)
{
if (idx < 0 || idx >= SC->count)
return NULL;
return SC->contents[idx];
}

static int InsertAt(StringCollection *SC, int idx, const char *str)
{
char *newval = NULL;

if (SC->flags & SC_READONLY)
return 0;
if (idx < 0 || idx > SC->count)
return -1;
if (SC->count >= SC->capacity) {
if (!Resize(SC))
return 0;
}
if (str) {
newval = DuplicateString(str);
if (newval == NULL)
return 0;
}
if (idx < SC->count) {
memmove(SC->contents + idx + 1, SC->contents + idx,
(SC->count - idx) * sizeof(*SC->contents));
}
SC->contents[idx] = newval;
return ++SC->count;
}

static int Insert(StringCollection *SC, const char *str)
{
return InsertAt(SC, 0, str);
}

static int RemoveAt(StringCollection *SC, int idx)
{
if (idx < 0 || idx >= SC->count)
return -1;
FREE(SC->contents[idx]);
memmove(SC->contents + idx, SC->contents + idx + 1,
(SC->count - idx - 1) * sizeof(*SC->contents));
SC->contents[--SC->count] = NULL;
return SC->count;
}

static int Remove(StringCollection *SC, const char *str)
{
int idx = IndexOf(SC, str);
if (idx < 0)
return idx;
return RemoveAt(SC, idx);
}

static int Push(StringCollection *SC, const char *str)
{
char *newval = NULL;

if (SC->flags & SC_READONLY)
return 0;
if (SC->count >= SC->capacity) {
if (!Resize(SC))
return 0;
}
if (str) {
newval = DuplicateString(str);
if (newval == NULL)
return 0;
}
SC->contents[SC->count++] = newval;
return SC->count;
}

static char * Pop(StringCollection *SC)
{
char *result;

if ((SC->flags & SC_READONLY) || SC->count == 0)
return NULL;
SC->count--;
result = SC->contents[SC->count];
SC->contents[SC->count] = NULL;
return result;
}

static int Finalize(StringCollection *SC)
{
int result = SC->count, i;

for (i = 0; i < SC->count; i++) {
FREE(SC->contents);
}
FREE(SC->contents);
FREE(SC);
return result;
}

static int GetCapacity(StringCollection *SC)
{
return SC->capacity;
}

static int SetCapacity(StringCollection *SC, int newcapacity)
{
char **newcontents;

if (newcapacity < 0)
return 0;

newcontents = MALLOC(newcapacity * sizeof(*newcontents));
if (newcontents == NULL)
return 0;

while (SC->count > newcapacity) {
FREE(SC->contents[--SC->count]);
}
memcpy(newcontents, SC->contents, SC->count * sizeof(*newcontents));
// useless, for cleanliness only
memset(newcontents + SC->count * sizeof(*newcontents),
0, (newcapacity - SC->count) * sizeof(*newcontents));
FREE(SC->contents);
SC->contents = newcontents;
SC->capacity = newcapacity;
return 1;
}

static void Apply(StringCollection *SC,
int (*Applyfn)(char *str, void *arg), void *arg)
{
int i;

for (i = 0; i < SC->count; i++) {
Applyfn(SC->contents, arg);
}
}

static int *Map(StringCollection *SC, int (*Applyfn)(char *str))
{
int *result = MALLOC(SC->count * sizeof(*result));
int i;

if (result == NULL)
return NULL;
for (i = 0; i < SC->count; i++) {
result = Applyfn(SC->contents);
}
return result;
}

#ifdef __LCC__
/* The lcc-win compiler allows operator overloading, and allows using
this abstract data type with the more natural [ ]= operators */
char * __declspec(naked) operator[]=(StringCollection *SC,
int idx, char *newval)
{
}
#endif

static char *ReplaceAt(StringCollection *SC, int idx, const char *str)
{
char *newval = NULL;

if (SC->flags & SC_READONLY)
return NULL;
if (idx < 0 || idx > SC->count)
return NULL;
if (idx == SC->count) {
if (!Add(SC, str))
return NULL;
} else {
if (str) {
newval = DuplicateString(str);
if (newval == NULL)
return NULL;
}
FREE(SC->contents[idx]);
SC->contents[idx] = newval;
}
return SC->contents[idx];
}

#ifdef TEST

#include <stdio.h>

static void PrintStringCollection(StringCollection *SC)
{
int i;

printf("Count %d, Capacity %d {\n",
SC->count, SC->capacity);
for (i = 0; i < SC->count; i++) {
printf(" \"%s\",\n", SC->lpVtbl->IndexAt(SC, i));
}
printf("}\n");
}

int main(void)
{
StringCollection *SC;
int count;
char *p;

SC = newStringCollection(0);
printf("newStringCollection(%d)\n", 0);
PrintStringCollection(SC);
SC->lpVtbl->Finalize(SC);

SC = newStringCollection(10);
printf("newStringCollection(%d)\n", 10);
PrintStringCollection(SC);
printf("Add \"%s\"\n", "Martin");
SC->lpVtbl->Add(SC, "Martin");
printf("Insert \"%s\"\n", "Jacob");
SC->lpVtbl->Insert(SC, "Jakob");
count = SC->lpVtbl->GetCount(SC);
if (count != 2)
printf("Count should be 2, is %d\n", count);
PrintStringCollection(SC);
printf("Insert at %d \"%s\"\n", 1, "Position 1");
SC->lpVtbl->InsertAt(SC, 1, "Position 1");
printf("Insert at %d \"%s\"\n", 2, "Position 2");
SC->lpVtbl->InsertAt(SC, 2, "Position 2");
PrintStringCollection(SC);
printf("Remove \"%s\"\n", "Jacob");
SC->lpVtbl->Remove(SC, "Jakob");
PrintStringCollection(SC);
printf("Push \"%s\"\n", "pushed");
SC->lpVtbl->Push(SC, "pushed");
PrintStringCollection(SC);
p = SC->lpVtbl->Pop(SC);
FREE(p);
printf("Pop -> \"%s\"\n", p);
PrintStringCollection(SC);
p = SC->lpVtbl->IndexAt(SC, 1);
printf("IndexAt %d -> \"%s\"\n", 1, p);
PrintStringCollection(SC);
SC->lpVtbl->Finalize(SC);

return 0;
}
#endif
 
B

Barry Schwarz

This is the implementation part of the string collection container

------------------------------------------------------------------

#include <string.h>
#include "strcollection.h"

#ifndef MALLOC
#include <stdlib.h>
#define MALLOC(s) malloc(s)
#define FREE(p) free(p)
#endif snip

#define SC_READONLY 1
#define CHUNKSIZE 20
#define DEFAULT_START_SIZE 0

StringCollection *newStringCollection(int startsize)
{
StringCollection *SC = MALLOC(sizeof(*SC));

if (SC == NULL)
return NULL;

SC->lpVtbl = &lpVtableSC;
SC->count = 0;
SC->contents = NULL;
SC->capacity = 0;
SC->flags = 0;

if (startsize == 0)
startsize = DEFAULT_START_SIZE;
if (startsize) {
Click to expand...

If the function was called with an argument of 0, startsize is still 0
and this block is not executed. SC->contents is still NULL.
SC->capacity = startsize;
SC->contents = MALLOC(startsize * sizeof(*SC->contents));
if (SC->contents == NULL) {
FREE(SC);
return NULL;
}
// useless, for cleanliness only
memset(SC->contents, 0, startsize * sizeof(*SC->contents));
Click to expand...

And this invokes undefined behavior when SC->contents is NULL.
 
B

Barry Schwarz

If the function was called with an argument of 0, startsize is still 0
and this block is not executed. SC->contents is still NULL.


And this invokes undefined behavior when SC->contents is NULL.
Click to expand...

Except of course that it never gets invoked and I should learn to
count braces more carefully.
 
J

jacob navia

Barry Schwarz a critics :
Except of course that it never gets invoked and I should learn to
count braces more carefully.
Click to expand...

To err is human... The catastrophe with my failed release should
prove that
:)

Thanks for reading my code.

jacob
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

strcollection.c 3
A string collection abstract data type 4
A container library in C. Part 1: Header file 14
A container library in C Part 4. The arraylist container 10
containers.h 0
test.c 4
A container library in C: Part 3. List container implementation 5
Engineering a list container. Part 1. 71

Members online

Total: 17 (members: 2, guests: 15)
Robots: 454

Forum statistics

Threads
473,769
Messages
2,569,580
Members
45,054
Latest member
TrimKetoBoost

Latest Threads

Top