[David W]

Since this split.h C code needs to include several other custom header files, the recommendation from KYA at DIC was to make this into a tutorial ... so here goes my first attempt at a DIC tut...

The goal here is to emulate in C ... several features available in C++

STL string
STL list

and also to emulate in C, the Python split function ...

so that you can then EASILY split a line into a CList of CStrings ...
(each CString in the CList is a 'word' in that line)


Note: files split.h, ClistOfString.h and readLine.h
used by this demo program below, are provided
following this split_demo_2.c

/* split_demo_2.c */ /* this version 2010-05-23 */

/* http://developers-heaven.net/forum/index.php/topic,46.0.html */

/*
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
*/

#include <ctype.h> /* re. tolower ... */

#define DELIMITS "* .?!,;:\t-" /* if don't define ... becomes "\t " */

#include "split.h"  /*
                        includes ClistOfString.h ... that includes ...
                        stdio.h, stdlib.h, string.h ... and adds ...
                        readLine, myAssert
                    */

/* returns '1' for 'Yes more' or '0' for 'No more' ... */
int more() /*  defaults to 'yes' ... i.e. must enter 'n' or 'N' for 'No' */
{
    int c, reply;
    printf("\nMore ... y/n ? ");
    reply = c = tolower( getchar() );
    while( c != '\n' ) c = getchar(); /* flush stdin ... */
    if(reply == 'n')
        return 0; /* No more ... */

    /* else ...*/
    return 1; /* Yes more ... */
}


int main() /* ********************** BEGIN MAIN ***************************** */
{
    char* s, * t; /* (pointers) C strings ... to hold a line of 'words' ... */
    Clist myCList;
    init( &myCList ); /* Note: MUST initial list for it to work properly ... */

    do
    {
        fputs( "Enter a line of words: ", stdout );
        s = readLine( stdin );

        printf( "For delimits '%s', \n", DELIMITS );
        printf( "splitting string '%s' \n", s );
        split( &myCList, s );
        showAll( &myCList );

        msort( &myCList );
        puts( "\nAfter msort ... " );
        showAll( &myCList );
        printf( "... and after msort ... the original string is still: \n"
              "'%s'\n", s );
              
        fputs( "Enter some more words: ", stdout );
        t = readLine( stdin );
        split( &myCList, t );
        showAll( &myCList );

        msort( &myCList );
        puts( "\nAfter msort ... " );
        showAll( &myCList );
        printf( "... and after msort ... the original 2nd string is still: \n"
              "'%s'\n", t );
        
        free( t );
        free( s );
        freeAll( &myCList );
        
    }while( more() );

    return 0;
} /* ******************************** END MAIN ****************************** */

Here is split.h

/* split.h */ /* this version: 2010-05-11 */

/* http://developers-heaven.net/forum/index.php/topic,46.0.html */

#ifndef dwSPLIT_H
#define dwSPLIT_H

#ifndef DELIMITS
#define DELIMITS  " \t"
#endif

#define NUM_DLMTS  sizeof(DELIMITS) -1


#ifndef dwClistOfString_H
#define dwClistOfString_H
#include "ClistOfString.h" /* adds stdio, stdlib, string, readLine, myAssert */
#endif


char* createNewString( int len )
{
	char* n;
    if( len < 0 ) len = 0;
    n = malloc(len+1);
    myAssert( (n!=NULL), "Error: malloc failed to allocate memory." );
    n[0] = 0;
    return n;
}

char* newCopy( const char* s )
{
    int slen = strlen(s);
    char* ncopy = createNewString(slen);
    strcpy(ncopy, s);
    return ncopy;
}

char* substr( const char* start, const char* end )
{
    int len = end-start+1;
    char* newCpy = createNewString(len);
    strncpy( newCpy, start, len );
    newCpy[len] = 0;
    return newCpy;
}

/* returns POSITION 1..len if in string ... otherwise, returns 0 */

int chrInString( const char* s, char c )
{
    int i;
    for( i =0; s[i] != 0; ++i )
        if( c ==  s[i] )
            return i+1;
    return 0;
}

void split( Clist* lst, char* s )
{
    char *p1 = s, *p2;
    List ml;
    //int i =0;
    for( ; ; ) // loop forever ... until break
    {
        while( *p1 != 0 && strchr(DELIMITS, *p1) ) ++p1;
        if( *p1 == 0 )
			break; // i.e. if empty or all delimits

        p2 = p1+1;
        while( *p2 != 0 && !strchr(DELIMITS, *p2) ) ++p2;
        ml.line = substr( p1, p2-1 );
        push_back( lst, &ml );
        //printf( "%d  %s\n", i++, pd->line );
        p1 = p2;
    }
}

/*
void split( Clist* lst, char* s )
{
    char* p;
    pList pd = malloc(sizeof(List) );
	myAssert( (pd!=NULL), "Error: malloc failed to allocate memory." );

	p = strtok(s, DELIMITS);
	while(p != NULL)
	{
		pd->line = newCopy( p );
		push_back( lst, pd );
		p = strtok(NULL, DELIMITS);
	}
	free( pd );
}
*/

#endif

And here is ClistOfString.h

/* ClistOfString.h */ /* this version: 2010-05-11 */

#ifndef dwClistOfString
#define dwClistOfString

#ifndef dwReadLine_H
#define dwReadLine_H
/* using readLine here ... instead of gets and fgets */
#include "readLine.h" /* includes stdio.h, stdlib.h  ... also myAssert( ... ) */
#endif

/* Note: stdio.h, stdlib.h and myAssert were included in "readLine.h" above */
#ifndef dwSTRING_H
#define dwSTRING_H
#include <string.h> /* re. memcpy */
#endif

typedef struct ClistOfString
{
    char* line;     /* since CStrings are '\0' terminated ... can get strlen */
    struct ClistOfString* next;
} List ;

typedef List* pList;

typedef struct myClist
{
    pList start;
    pList end;
    int size;
    int isSorted;
} Clist;

/* with these, an address is passed, so NO copy made and/or original updated */
void init( Clist* ); /* sets start to NULL, size to 0. isSorted to 1 */
void push_front( Clist*, List* );
void push_back( Clist*, List* );
void freeAll( Clist* );
void show( pList );
void showAll( Clist* );

void msort( Clist* );
void mergesort( Clist* );
pList merge( Clist*, Clist* );
void update_end( Clist* );


void init( Clist* list )
{
    list->start = list->end = NULL;
    list->size = 0;
    list->isSorted = 1;
}

void push_front( Clist* list, List* d )
{
    pList p = malloc( sizeof(List) );
    if( p == NULL )
    {
        freeAll( list );
        myAssert( 0, "Error: malloc failed to allocate memory." );
    }

    /* now add in ALL new dat ... (assuming next pointer is last of dat) */
    memcpy( p, d, sizeof(List)-sizeof(pList) ); /* -sizeof(any_pointer) is ok */
    /* and set pointers to next ... and start ...*/
    p->next = list->start;
    list->start = p;

    ++ list->size;
    if( list->size > 1 ) list->isSorted = 0;
    else list->end = list->start;
}

void push_back( Clist* list, List* d )
{
    pList p = malloc( sizeof(List) );
    if( p == NULL )
    {
        freeAll( list );
        myAssert( 0, "Error: malloc failed to allocate memory." );
    }

    /* now add in ALL new dat ... (assuming next pointer is last of dat) */
    memcpy( p, d, sizeof(List)-sizeof(pList) ); /* -sizeof(any_pointer) is ok */
    /* and set pointers to next ... and start ...*/

    p->next = NULL;
    ++ list->size;
    if( list->size > 1 )
    {
        list->end->next = p;
        list->end = p;
        list->isSorted = 0;
    }
    else
        list->start = list->end = p;
}

void freeAll( Clist* list )
{
    //printf( "\nFreeing list->size  of %d ... \n", list->size );
    if( list->size > 0 )
    {
        pList cur = list->start;
        for( ; cur != NULL; cur = list->start  )
        {
            list->start = cur->next;
            free( cur->line );
            free( cur );
        }
        init( list );
    }
}

void show( pList pd )
{
    printf( "%s\n", pd->line );
}
void showAll( Clist* list )
{
    if( list->size )
    {
		pList p = list->start;
		for( ; p != NULL; p = p->next )
			show( p );
		printf( "List size = %d\n", list->size );
    }
    else puts( "The list is empty ... " );
}


/* a recursive mergesort ... */
void mergesort(Clist* list)
{
    pList cur = list->start;
    Clist a, b;

    /* base case is a Clist of length 0 or 1 ... */
    if ((cur == NULL) || (cur->next == NULL))  return;

    /* split Clist into 'a' and 'b' sublists ... */
    a.start = cur;
    b.start = cur->next;
    while((b.start != NULL) && (b.start->next != NULL))
    {
        cur = cur->next;
        b.start = b.start->next->next;
    }
    b.start = cur->next;
    cur->next = NULL; /* Clist divided into 2 roughly equal parts now ... */

    /* recursively sort the sublists ... */
    mergesort(&a);
    mergesort(&B)/>;

    /* merge the two sorted Clists together ... */
    list->start = merge(&a, &B)/>;
    list->isSorted = 0;
}


/* merge two sorted Clists with heads 'a' and 'b' ... in sorted order */
pList merge(Clist* a, Clist* b )
{
    pList sorted, new_merged_head;

    if( a->start == NULL ) return b->start;
    if( b->start == NULL ) return a->start;

    if( strcmp( a->start->line, b->start->line ) <= 0 )
    {
        sorted = a->start;
        a->start = a->start->next;
    }
    else
    {
        sorted = b->start;
        b->start = b->start->next;
    }
    new_merged_head = sorted;

    /* now ... */
    while( a->start != NULL && b->start != NULL )
    {
        if( strcmp( a->start->line, b->start->line ) <= 0 )
        {
            sorted->next = a->start;
            sorted = a->start;
            a->start = a->start->next;
        }
        else
        {
            sorted->next = b->start;
            sorted = b->start;
            b->start = b->start->next;
        }
    }

    /* and finally ... */
    if( a->start != NULL )
        sorted->next = a->start;
    else if( b->start != NULL )
        sorted->next = b->start;

    return new_merged_head;
}

void update_end( Clist* list ) /* after sort */
{
    if( list->size > 1 )
    {
        pList cur;
        for( cur = list->start; cur->next != NULL; cur = cur->next ) ;
        list->end = cur;
        list->end->next = NULL;
    }
}

void msort( Clist* clst )
{
    mergesort( clst );
    update_end( clst );
}

#endif /* end of ifndef dwSTRING_H ... */

And, finally, here is readLine.h

/* readLine.h */ /* this version 2010-03-28 */

/* http://developers-heaven.net/forum/index.php/topic,46.0.html */

/*
    Safe string data entry from file ... to replace gets and fgets
    BUT free new memory ... when done! Don't forget that C strings are
    pointers to a block of char, with a '\0' char at the terminal end ...

    Call like this:

        char* line = readLine( stdin );

        or ...

        while( (line = readLine( FILEp )) )
        {
            // process line ...
        }
*/

#ifndef dwREADLINE
#define dwREADLINE

/* can re-set/adjust here to best match your line-length */
#define LINECHUNK 256

#ifndef dwSTDIO_H
#define dwSTDIO_H
#include <stdio.h>
#endif
#ifndef dwSTDLIB_H
#define dwSTDLIB_H
#include <stdlib.h>
#endif

#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, char text[] )
{
    if( !condition )
    {
        fprintf(stderr, "%s\n", text );
        fputs( "Press 'Enter' to exit program ... ", stderr );
        getchar();
        exit(1);
    }
}
#endif

/* returns a string in new memory holding each word ... or NULL if EOF */
char* readLine( FILE* fp  )
{
    int c, i = 0; /* c to hold each char, i for index in string ... */
    int lineLen = LINECHUNK;
    void* tmp;
    char* strData = (char*) calloc( lineLen, 1 ); /* cast for C++ compilers */
    myAssert( (strData != NULL), "Error: calloc failed to allocate memory (1)" );
    while( (c = fgetc(fp)) != EOF  &&  c != '\n' )
    {
        if( i == lineLen-2 ) /* get more memory now (for word or line) */
        {
            lineLen += LINECHUNK; /* enlarge memory */
            if( (tmp = realloc(strData, lineLen)) == NULL )
            {
                free(strData);
                myAssert( 0, "Error: realloc failed to allocate memory (2)" );
            }
            strData  = (char*) tmp; /* good realloc above, so update pointer */
        }   
        strData[i] = c;
        ++i;
    }
    strData[i] = 0; /* confirm termination */

    if( c == EOF  && strData[0] == 0 ) { free( strData); return NULL; }
    /* else ... since didn't return NULL above, adjust string to right-size */
    if( (tmp = realloc(strData, i+1)) == NULL )
    {
        free(strData);
        myAssert( 0, "Error: realloc failed to allocate memory (3)" );
    }
    return (char*) tmp; /* return the right-sized string ... */
}

#endif

[David W]

NOTE!!! the 'b' below somehow was changed into a 'B' ...

THUS ... you need to fix this to compile that code ok ...
(so ... see below ... or see this next link for latest updates:
http://developers-he...index.php/topic,106.msg592.html#msg592
)

133	/* a recursive mergesort ... */
134	void mergesort(Clist* list)
135	{
136	    pList cur = list->start;
137	    Clist a, b;
138	 
139	    /* base case is a Clist of length 0 or 1 ... */
140	    if ((cur == NULL) || (cur->next == NULL))  return;
141	 
142	    /* split Clist into 'a' and 'b' sublists ... */
143	    a.start = cur;
144	    b.start = cur->next;
145	    while((b.start != NULL) && (b.start->next != NULL))
146	    {
147	        cur = cur->next;
148	        b.start = b.start->next->next;
149	    }
150	    b.start = cur->next;
151	    cur->next = NULL; /* Clist divided into 2 roughly equal parts now ... */
152	 
153	    /* recursively sort the sublists ... */
154	    mergesort(&a);
155	    mergesort( & b );  /* NOT: & B */
156	 
157	    /* merge the two sorted Clists together ... */
158	    list->start = merge(&a, & b ); /* NOT: & B */
159	    list->isSorted = 0;
160	}

/* ClistOfString.h */ /* this version: 2010-05-11 */

#ifndef dwClistOfString
#define dwClistOfString

#ifndef dwReadLine_H
#define dwReadLine_H
/* using readLine here ... instead of gets and fgets */
#include "readLine.h" /* includes stdio.h, stdlib.h  ... also myAssert( ... ) */
#endif

/* Note: stdio.h, stdlib.h and myAssert were included in "readLine.h" above */
#ifndef dwSTRING_H
#define dwSTRING_H
#include <string.h> /* re. memcpy */
#endif

typedef struct ClistOfString
{
    char* line;     /* since CStrings are '\0' terminated ... can get strlen */
    struct ClistOfString* next;
} List ;

typedef List* pList;

typedef struct myClist
{
    pList start;
    pList end;
    int size;
    int isSorted;
} Clist;

/* with these, an address is passed, so NO copy made and/or original updated */
void init( Clist* ); /* sets start to NULL, size to 0. isSorted to 1 */
void push_front( Clist*, List* );
void push_back( Clist*, List* );
void freeAll( Clist* );
void show( pList );
void showAll( Clist* );

void msort( Clist* );
void mergesort( Clist* );
pList merge( Clist*, Clist* );
void update_end( Clist* );


void init( Clist* list )
{
    list->start = list->end = NULL;
    list->size = 0;
    list->isSorted = 1;
}

void push_front( Clist* list, List* d )
{
    pList p = malloc( sizeof(List) );
    if( p == NULL )
    {
        freeAll( list );
        myAssert( 0, "Error: malloc failed to allocate memory." );
    }

    /* now add in ALL new dat ... (assuming next pointer is last of dat) */
    memcpy( p, d, sizeof(List)-sizeof(pList) ); /* -sizeof(any_pointer) is ok */
    /* and set pointers to next ... and start ...*/
    p->next = list->start;
    list->start = p;

    ++ list->size;
    if( list->size > 1 ) list->isSorted = 0;
    else list->end = list->start;
}

void push_back( Clist* list, List* d )
{
    pList p = malloc( sizeof(List) );
    if( p == NULL )
    {
        freeAll( list );
        myAssert( 0, "Error: malloc failed to allocate memory." );
    }

    /* now add in ALL new dat ... (assuming next pointer is last of dat) */
    memcpy( p, d, sizeof(List)-sizeof(pList) ); /* -sizeof(any_pointer) is ok */
    /* and set pointers to next ... and start ...*/

    p->next = NULL;
    ++ list->size;
    if( list->size > 1 )
    {
        list->end->next = p;
        list->end = p;
        list->isSorted = 0;
    }
    else
        list->start = list->end = p;
}

void freeAll( Clist* list )
{
    //printf( "\nFreeing list->size  of %d ... \n", list->size );
    if( list->size > 0 )
    {
        pList cur = list->start;
        for( ; cur != NULL; cur = list->start  )
        {
            list->start = cur->next;
            free( cur->line );
            free( cur );
        }
        init( list );
    }
}

void show( pList pd )
{
    printf( "%s\n", pd->line );
}
void showAll( Clist* list )
{
    if( list->size )
    {
		pList p = list->start;
		for( ; p != NULL; p = p->next )
			show( p );
		printf( "List size = %d\n", list->size );
    }
    else puts( "The list is empty ... " );
}


/* a recursive mergesort ... */
void mergesort(Clist* list)
{
    pList cur = list->start;
    Clist a, b;

    /* base case is a Clist of length 0 or 1 ... */
    if ((cur == NULL) || (cur->next == NULL))  return;

    /* split Clist into 'a' and 'b' sublists ... */
    a.start = cur;
    b.start = cur->next;
    while((b.start != NULL) && (b.start->next != NULL))
    {
        cur = cur->next;
        b.start = b.start->next->next;
    }
    b.start = cur->next;
    cur->next = NULL; /* Clist divided into 2 roughly equal parts now ... */

    /* recursively sort the sublists ... */
    mergesort(&a);
    mergesort( & b );

    /* merge the two sorted Clists together ... */
    list->start = merge(&a, & b );
    list->isSorted = 0;
}


/* merge two sorted Clists with heads 'a' and 'b' ... in sorted order */
pList merge(Clist* a, Clist* b )
{
    pList sorted, new_merged_head;

    if( a->start == NULL ) return b->start;
    if( b->start == NULL ) return a->start;

    if( strcmp( a->start->line, b->start->line ) <= 0 )
    {
        sorted = a->start;
        a->start = a->start->next;
    }
    else
    {
        sorted = b->start;
        b->start = b->start->next;
    }
    new_merged_head = sorted;

    /* now ... */
    while( a->start != NULL && b->start != NULL )
    {
        if( strcmp( a->start->line, b->start->line ) <= 0 )
        {
            sorted->next = a->start;
            sorted = a->start;
            a->start = a->start->next;
        }
        else
        {
            sorted->next = b->start;
            sorted = b->start;
            b->start = b->start->next;
        }
    }

    /* and finally ... */
    if( a->start != NULL )
        sorted->next = a->start;
    else if( b->start != NULL )
        sorted->next = b->start;

    return new_merged_head;
}

void update_end( Clist* list ) /* after sort */
{
    if( list->size > 1 )
    {
        pList cur;
        for( cur = list->start; cur->next != NULL; cur = cur->next ) ;
        list->end = cur;
        list->end->next = NULL;
    }
}

void msort( Clist* clst )
{
    mergesort( clst );
    update_end( clst );
}

#endif /* end of ifndef dwSTRING_H ... */

This post has been edited by JackOfAllTrades: 01 December 2010 - 09:52 AM

[KYA]

The BBcode parser tries to make it a smiley face B + )so a lower case 'b' next to an end parentheses will make it an capital 'B' but no smiley.

[David W]

KYA, on 13 July 2010 - 07:24 PM, said:

The BBcode parser tries to make it a smiley face B + )so a lower case 'b' next to an end parentheses will make it an capital 'B' but no smiley.

Thanks for that info KYA ... I supposed it might have been something like that ... So ... an other reason to have spaces in my code ...

1. after every (
and
2. before every )

[drhowarddrfine]

Since this is C code to emulate C++, shouldn't this be in C Tutorials?

Oh. There isn't one. Why isn't there since C is used far more than C++ according to Tiobe? (Call me a troll)

[David W]

drhowarddrfine, on 29 July 2010 - 05:48 AM, said:

Since this is C code to emulate C++, shouldn't this be in C Tutorials?

Oh. There isn't one. Why isn't there since C is used far more than C++ according to Tiobe? (Call me a troll)

Perhaps ... it's like the C/C++ forum at DIC

(and one may find there tut's re. C++ and C)

This post has been edited by David W: 29 July 2010 - 11:33 AM

[macosxnerd101]

drhowarddrfine, on 29 July 2010 - 07:48 AM, said:

Since this is C code to emulate C++, shouldn't this be in C Tutorials?

Oh. There isn't one. Why isn't there since C is used far more than C++ according to Tiobe? (Call me a troll)

If you have a C tutorial, you should submit it in the C++ Tutorials section. As alti pointed out a while ago, the MySQL snippets section is improperly named, as it is for SQL snippets in general. I'm not exactly sure about the naming conventions here, but those are the appropriate categories for the respective topics.

[David W]

You may like to see this new extension to this tutorial ... that shows other examples of using split.h and gives an updated ClistOfString.h ... where the main engine of ClistOfSring... the core CList ... is separated out into its own file Clist.h ... to facilitate reuse ..

Note: the PC I'm at presently, will not permit me to insert a link without chopping the middle out ... thus the link is here inside a code block so the whole link can be seen ...

http://developers-heaven.net/forum/index.php/topic,466.0.html

This post has been edited by David W: 07 August 2010 - 12:22 AM

[David W]

David W, on 07 August 2010 - 12:57 AM, said:

You may like to see this new extension to this tutorial ... that shows other examples of using split.h and gives an updated ClistOfString.h ... where the main engine of ClistOfSring... the core CList ... is separated out into its own file Clist.h ... to facilitate reuse ..

...

see new examples linked at end ...
http://developers-he...opic,466.0.html

This post has been edited by David W: 07 September 2010 - 11:35 PM

[David W]

Guest, on 05 February 2011 - 09:58 PM, said:

Has any one used this container in a program?

Well ... I don't really know of anyone else who does use split.h except me. But some time ago, when I was doing a Google search of links to my name, I came across a software library site that linked to several snippets I had posted at DIC. But, it would be nice to hear from people who use C and might like some more enhancements. I have already further enhanced ClistOfString.h and added ClistOfInt.h (that adapts to any other known type like float or double).

'split.h' could also be easily modified to use my Cvec.h ... (instead of Clist.h)

[David W]

You may like to see these updates to the related files that split.h uses ... ClistOfString.h and Clist.h ... and the new functions they now include ... isortClist and insert_sortedClist (still has msort) ... also added isSortedUp, unique, join, showClist, findClist, eraseClist

join Clist is an emulation of the Python join function that joins a list of strings with your choice of separator in between adjacent elements in the list of strings ... into one long dynamic memory C string that you can later free when done with it ...

http://developers-he...index.php/topic,2473.msg2746.html#msg2746

or copy/paste below link into your browser ... and go there ...

http://developers-heaven.net/forum/index.php/topic,2473.msg2746.html#msg2746

and/or ...

http://developers-he...index.php/topic,2022.0.html

This post has been edited by David W: 15 April 2011 - 02:20 PM