The String Table

You will need to use strings quite a bit in the implementation, and you will not want to worry about memory management for them. A good idea is to create a table with all of the strings that you have seen stored in it.

Create such a table. Define function intern(s) that looks up string s in the table and returns the string stored for s. If s is not in the table, it should be inserted and the inserted string returned. By using intern, you will only have one copy of each string.

Choose a very simple implementation of the string table. For example, use an array, and do a linear search of the array to perform an intern operation. Do not try to be fancy.

Directories and files

Create three directories: src, obj and bin. Directory src will hold your source files. Directory obj will hold your compiled object files. Directory bin will hold executable files.

Create files stringtable.c and stringtable.h that implement the intern function, plus file allocate.h for basic memory allocation, putting all three in directory src. File stringtable.c holds an implementation of intern. File stringtable.h holds a prototype for intern, as follows.

const char* intern(const char* s);

Now create a file teststringtable.c to test the string table. It should say

#include "stringtable.h"

When you are satisfied that it works, submit your three files (excluding the tester) as assignment stringtable by logging into xlogin.cs.ecu.edu and doing the following command.

cd src
~abrahamsonk/5220/bin/submit stringtable allocate.h stringtable.h stringtable.c

Suggestions

Put the following memory-allocation macros in allocate.h.

#include <stdlib.h>

/*=====================================================
 * NEW(T) yields a pointer to memory that can be set to 
 * hold one object of type T.  For example,
 *   Node* t = NEW(Node);
 * allocates one new Node.
 *=====================================================*/

#define NEW(T) ((T*)(malloc(sizeof(T))))

/*==================================================
 * NEWARRAY(T,N) yields a pointer to memory for an
 * array of N objects of type T.  For example,
 *   char* s = NEWARRAY(char, 10);
 * allocates an array of 10 characters.
 *==================================================*/

#define NEWARRAY(T,N) ((T*)(malloc((N)*sizeof(T))))

Include "allocate.h" in stringtable.c.

Here is a function that creates a permanent copy of a string, suitable for storing in the string table.

char* perm(const char* s)
{
  char* result = NEWARRAY(char, strlen(s) + 1);
  strcpy(result, s);
  return result;
}

Loggin in

Log into xlogin.cs.ecu.edu. See notes on logging into xlogin.

Using xlogin

See notes on using xlogin.

A makefile

You will want a makefile for building your software. Here is a start. Paste it into a file called Makefile.

CC     = gcc
LINK   = gcc
CFLAGS = -Wall
RM     = rm

CFILES = src/stringtable.c\
         src/teststringtable.c

OFILES = $(patsubst src/%.c,obj/%.o,$(CFILES))

EFILES = bin/teststringtable

STRINGTABLE_OFILES = obj/stringtable.o\
                     obj/teststringtable.o

bin/teststringtable: $(STRINGTABLE_OFILES)
	$(LINK) -o bin/teststringtable $(STRINGTABLE_OFILES)

obj/%.o: src/%.c
	$(CC) $(CFLAGS) -c $< -o $@

clean:
	$(RM) $(OFILES) $(EFILES)

Now command

make teststringtable

./bin/teststringtable

Important

I am not interested in something that you have thrown together and not tested. I expect you to test everything that you write. If you submit something that does not compile, I know that you have not tested it even once. Accordingly,

Work that does not compile automatically receives a score of 0.

Submitting your work

After you have the string table working, submit it as follows. I assume that you file are called stringtable.h and stringtable.c.

1. Log into xlogin.cs.ecu.edu.

2. Change to the directory that contains your files and run command

     ~abrahamsonk/5220/bin/submit stringtable stringtable.h stringtable.c allocate.h
   

   Include any other files that are needed.