streamdb.c

`smith.motif.tar.Z includes the source code for the book "Designing X clients with Xt/Motif," by Je

	}
	else if (position == streamdb_CURRENT) {
		entry = sObject->current->previous;
		entry->next = new_entry;
		new_entry->next = sObject->current;
		new_entry->previous = entry;
		sObject->current->previous = new_entry;
	}
	else {
		while (entry->next && position > 1) {	/* count down to position	*/
			entry = entry->next;				/* just prior to insert pt.	*/
			position--;
		}
		new_entry->next = entry->next;
		entry->next->previous = new_entry;
		entry->next = new_entry;
		new_entry->previous = entry;
	}
	sObject->num_entries++;
	return new_entry;
}	/* streamdb_insert */


/*
streamdb_delete() oversees the deletion of a text entry
from stream-oriented database.  It returns a pointer to the
next entry, i.e., the entry after the deleted entry.  The
position specification should be zero-based.
*/

EntryDB streamdb_delete(sObject, position)
StreamDB sObject;
int position;
{
	EntryDB entry;

	if (!sObject->first || !sObject->num_entries ||
			position >= sObject->num_entries)
		return NULL;
	if (position == streamdb_CURRENT && !sObject->current)
		return NULL;
	sObject->file_modified = TRUE;
	entry = sObject->first;
	sObject->num_entries--;
	if (position == 0 ||
	(position == streamdb_CURRENT && sObject->first == sObject->current)) {
		if (sObject->first == sObject->current)
			sObject->current = NULL;
		sObject->first = entry->next;		/* could be NULL */
		if (!sObject->first)
			sObject->current = sObject->last = NULL;
		if (entry->text)
			free(entry->text);
		free(entry);
		if (sObject->first)
			sObject->first->previous = NULL;/* could be NULL already */
		return sObject->first;
	}
	else {
		EntryDB next_entry;

		if (position == streamdb_CURRENT)
			entry = sObject->current->previous;
		else
			while (position > 1) {			/* count down to position	*/
				entry = entry->next;		/* just prior to delete pt.	*/
				position--;
			}
		next_entry = entry->next->next;
		if (!next_entry)
			sObject->last = entry;
		if (entry->next->text)
			free(entry->next->text);
		free(entry->next);
		entry->next = next_entry;
		if (next_entry)
			next_entry->previous = entry;
		return next_entry;
	}
}	/* streamdb_delete */


/*
streamdb_search_forward() traverses the list beginning at the
current entry for the next entry with text that matches the
search string.
*/

EntryDB streamdb_search_forward(sObject, search_text, mode)
StreamDB sObject;
char *search_text;
int mode;
{
	EntryDB entry = sObject->current;

	if (!sObject->current)
		return NULL;
	if (mode == string_INSENSITIVE)
		while (entry) {
			if (string_search_insensitive(entry->text, search_text, 0) !=
					string_NO_MATCH)
				return entry;
			entry = entry->next;
		}
	else
		while (entry) {
			if (string_search(entry->text, search_text, 0) != string_NO_MATCH)
				return entry;
			entry = entry->next;
		}
	return NULL;
}	/* streamdb_search_forward */


/*
streamdb_search_backward() traverses the list beginning at the
current entry for the next entry with text that matches the
search string.
*/

EntryDB streamdb_search_backward(sObject, search_text, mode)
StreamDB sObject;
char *search_text;
int mode;
{
	EntryDB entry = sObject->current;

	if (!sObject->current)
		return NULL;
	if (mode == string_INSENSITIVE)
		while (entry) {
			if (string_search_insensitive(entry->text, search_text, 0) !=
					string_NO_MATCH)
				return entry;
			entry = entry->previous;
		}
	else
		while (entry) {
			if (string_search(entry->text, search_text, 0) != string_NO_MATCH)
				return entry;
			entry = entry->previous;
		}
	return NULL;
}	/* streamdb_search_backward */


/*
streamdb_sort() builds a binary tree of pointers to the database
entries.  An inorder traversal is used to retrieve the entries in
sorted order.
*/

EntryDB streamdb_sort(sObject, order)
StreamDB sObject;
int order;
{
	TreeNode root;

	first_entry = NULL;
	root = NULL;
	num_nodes = sObject->num_entries;
	if (build_search_tree(&root, sObject->first, order)) {
		sObject->file_modified = TRUE;
		traverse_tree(root);
		sObject->first = first_entry;
		sObject->last = last_entry;
	}
	destroy_tree(root);
	return sObject->first;
}	/* streamdb_sort */


/*
streamdb_print() traverses the list and prints the text for each entry.
*/

void streamdb_print(sObject, spacing)
StreamDB sObject;
char *spacing;	/* e.g., add extra newline */
{
	if (sObject->first) {
		EntryDB entry = sObject->first;

		while (entry) {
			printf("%s%s", entry->text, spacing);
			entry = entry->next;
		}
	}
}	/* streamdb_print */


/*
file_exists() determines whether or not a file exists.
*/

int file_exists(file_spec)
char *file_spec;
{
	return (file_size(file_spec) != streamdb_NO_FILE);
}   /* file_exists */


/*
Private support functions:
*/

/*
build_list_from_buffer() constructs a linked list of the
entries in the byte stream, based on the specified delimiter.
*/

static int build_list_from_buffer(sObject, buffer, size)
StreamDB sObject;
char *buffer;
int size;
{
	int first_time = TRUE, next = 0;
	int current, i, text_len;
	EntryDB new_entry, prev_entry;

	sObject->num_entries = 0;
	sObject->first = sObject->last = NULL;
	do {
		current = offset_without_delimiter(sObject, buffer, next);
		next = scan_for_next_entry(sObject, buffer, current);
		if (next == string_NO_MATCH)
			next = size;						/* end of file */
		if ((text_len = next - current) > 0) {
			if ((new_entry = get_new_node()) == NULL)
				return FALSE;
			if (first_time) {
				first_time = FALSE;
				sObject->first = new_entry;
			}
			else {
				/*
				`prev_entry' is set at the end of the first cycle:
				*/
				prev_entry->next = new_entry;
				new_entry->previous = prev_entry;
			}
			new_entry->text = (char *) malloc((unsigned) (next - current + 1));
			for (i = 0; i < text_len; )
				new_entry->text[i++] = buffer[current++];
			new_entry->text[i] = EOS;
			prev_entry = new_entry;
			sObject->num_entries++;
		}
	} while (current < size);
	sObject->last = new_entry;
	return TRUE;
}	/* build_list_from_buffer */


/*
get_new_node() allocates a new node and initializes its storage.
*/

static EntryDB get_new_node()
{
	EntryDB new_entry;

	if ((new_entry = (EntryDB) malloc(sizeof(_EntryDB))) == NULL)
		return NULL;
	new_entry->text = NULL;
	new_entry->previous = new_entry->next = NULL;
	return new_entry;
}	/* get_new_node */


/*
offset_without_delimiter() is used to "get at" the real entry,
not counting the arbitrary delimiter.
*/

static int offset_without_delimiter(sObject, buffer, offset)
StreamDB sObject;
char *buffer;
int offset;
{
	/*
	simply skip over the delimiter if it's there:
	*/
	if (strncmp(&buffer[offset], sObject->delimiter, sObject->delimiter_len)
			== 0)
		offset += sObject->delimiter_len;
	return offset;
}	/* offset_without_delimiter */


/*
load_buffer() loads text into a character buffer.
For efficiency, it assumes that the application has
already determined that the file is NOT too large for
the buffer.  It returns the length of the buffer/string.
*/

static int load_buffer(sObject, buffer)
StreamDB sObject;
char *buffer;
{
	int len;

	if ((len = read_from_disk(buffer, sObject->filename)) ==
				streamdb_CANT_READ) {
		return FALSE;
	}
	return len;
}    /* load_buffer */


/*
read_from_disk() loads a buffer from a disk file.  It
null-terminates the buffer/string and returns the number
of bytes read, not counting the end-of-string marker.
You may want to use fread() here.
*/

static int read_from_disk(buffer, file_spec)
register char *buffer;
char *file_spec;
{
	FILE *db_file;
	register int len;

	if ((db_file = fopen(file_spec, "r")) == NULL) {
		*buffer = EOS;
		return streamdb_CANT_READ;
	}
	for (len = 0; (buffer[len] = fgetc(db_file)) != (char) EOF; len++)
		;
	buffer[len] = EOS;
	fclose(db_file);
	return len;
}   /* read_from_disk */


/*
write_to_disk() writes a buffer to disk and returns TRUE,
if no errors occur.  You may want to use fwrite() here.
*/

static int write_to_disk(sObject, file_spec)
StreamDB sObject;
char *file_spec;
{
	FILE *db_file;
	register int i, status = TRUE;

	if (*file_spec == EOS)
		return FALSE;
	if ((db_file = fopen(file_spec, "w")) == NULL) {
		status = streamdb_CANT_WRITE;
		return status;
	}
	if (sObject->first) {
		EntryDB entry = sObject->first;

		while (entry) {
			if (entry->text && *entry->text) {
				fputs(sObject->delimiter, db_file);
				for (i = 0; entry->text[i] && status == TRUE; i++)
					status = (fputc(entry->text[i], db_file) != EOF);
			}
			entry = entry->next;
		}
	}
	fclose(db_file);
	return status;
}   /* write_to_disk */


/*
file_size() checks for the existence of a file using stat(),
returning `streamdb_NO_FILE' for a nonexistent file, and the
file size otherwise.
*/

static int file_size(file_spec)
char *file_spec;
{
	struct stat	statbuf;

	if (stat(file_spec, &statbuf) < 0)
		return streamdb_NO_FILE;
	else
		return (int) statbuf.st_size;
}    /* file_size */


/*
scan_for_next_entry() finds the offset of the entry that's
one position closer to the end of the byte stream than the
current entry.
*/

static int scan_for_next_entry(sObject, buffer, offset)
StreamDB sObject;
char *buffer;
int offset;
{
	return string_search(buffer, sObject->delimiter,
		offset_without_delimiter(sObject, buffer, offset));
}	/* scan_for_next_entry */


/*
build_search_tree() traverses the linked list of database entries
building a binary tree with pointers to the database entries in
the data fields.
*/

static int build_search_tree(root, entry, order)
TreeNode *root;
EntryDB entry;
int order;
{
	while (entry) {
		if (!insert_into_tree(root, entry, order))
			return FALSE;
		entry = entry->next;
	}
	return TRUE;
}	/* build_search_tree */


/*
insert_into_tree() adds the next node.
*/

static int insert_into_tree(root, entry, order)
TreeNode *root;
EntryDB entry;
int order;
{
	TreeNode new_node, previous_node, next_node;

	next_node = *root;
	previous_node = NULL;
	while (next_node) {
		previous_node = next_node;
		next_node = go_left(entry, next_node, order) ?
			next_node->left : next_node->right;
	}
	if ((new_node = (TreeNode) malloc(sizeof(_TreeNode))) == NULL)
		return FALSE;
	new_node->database_entry = entry;
	new_node->left = NULL;
	new_node->right = NULL;
	if (!previous_node)
		*root = new_node;
	else {
		if (go_left(entry, previous_node, order))
			previous_node->left = new_node;
		else
			previous_node->right = new_node;
	}
	return TRUE;
}	/* insert_into_tree */


/*
go_left() tests the data to determine if the next entry should be
placed in the left subtree.
*/

static int go_left(entry, node, order)
EntryDB entry;
TreeNode node;
int order;
{
	if (order == streamdb_ASCEND)
		return (strcmp(entry->text, node->database_entry->text) <= 0);
	else
		return (strcmp(entry->text, node->database_entry->text) >= 0);
}	/* go_left */


/*
traverse_tree() traverses a binary tree of database entries,
using an inorder traversal to update the pointers in the
database entries.
*/

static void traverse_tree(node)
TreeNode node;
{
	if (node) {
		traverse_tree(node->left);
		update_linked_list(node);
		traverse_tree(node->right);
	}
}	/* traverse_tree */


/*
destroy_tree() traverses a tree and frees each node.
*/

static void destroy_tree(node)
TreeNode node;
{
	if (node) {
		destroy_tree(node->left);
		destroy_tree(node->right);
		free(node);
	}
}	/* destroy_tree */


/*
update_linked_list() sets the previous and next pointers in each
database entry.  The previous entry is held in a local static
variable.  It sets to file-level global variables for the first
and last entries in the list.
*/

static void update_linked_list(node)
TreeNode node;
{
	static EntryDB prev_entry;

	/*
	if `first_entry' is NULL, traversal has descended to the
	first entry	in the database, not the first node in the tree:
	*/
	if (!first_entry) {
		first_entry = node->database_entry;
		prev_entry = NULL;
	}
	node->database_entry->previous = prev_entry;
	if (prev_entry)
		prev_entry->next = node->database_entry;
	prev_entry = node->database_entry;
	/*
	`num_nodes' is set in streamdb_sort() to the total number of
	entries.  When it equals 1, all tree nodes have been visited.
	*/
	if (num_nodes-- == 1) {
		last_entry = node->database_entry;
		last_entry->next = NULL;
	}
}	/* update_linked_list */