/** \file partcatalog.c
* Manage the catalog of track parameter files
*/
/* XTrkCad - Model Railroad CAD
* Copyright (C) 2019 Martin Fischer
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#include <assert.h>
#include <ctype.h>
#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif
#include <search.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#ifdef WINDOWS
#include "include/dirent.h"
#else
#include <dirent.h>
#endif
#include "fileio.h"
#include "misc.h"
#include "include/paramfile.h"
#include "include/partcatalog.h"
#include "paths.h"
#include "include/stringxtc.h"
#include "include/utf8convert.h"
#if _MSC_VER > 1300
#define strnicmp _strnicmp
#define strdup _strdup
#endif
#define PUNCTUATION "+-*/.,&%=#"
/**
* Create and initialize the linked list for the catalog entries
*
* \return pointer to first element
*/
CatalogEntry *
InitCatalog(void)
{
CatalogEntry *head;
CatalogEntry *tail;
/* allocate two pseudo nodes for beginning and end of list */
head = (CatalogEntry *)malloc(sizeof(CatalogEntry));
tail = (CatalogEntry *)malloc(sizeof(CatalogEntry));
head->next = tail;
tail->next = tail;
return (head);
}
/**
* Create a new CatalogEntry and add it to the linked list. The newly
* created entry is inserted into the list after the given position
*
* \param entry IN insertion point
* \return pointer to new entry
*/
static CatalogEntry *
InsertIntoCatalogAfter(CatalogEntry *entry)
{
CatalogEntry *newEntry = (CatalogEntry *)malloc(sizeof(CatalogEntry));
newEntry->next = entry->next;
entry->next = newEntry;
newEntry->files = 0;
newEntry->contents = NULL;
return (newEntry);
}
/**
* Count the elements in the linked list ignoring dummy elements
*
* \param listHeader IN the linked list
* \return the numberof elements
*/
unsigned
CountCatalogEntries(CatalogEntry *listHeader)
{
CatalogEntry *currentEntry = listHeader->next;
unsigned count = 0;
while (currentEntry != currentEntry->next) {
count++;
currentEntry = currentEntry->next;
}
return (count);
}
/**
* Empty a catalog. All data nodes including their allocated memory are freed. On
*
* \param listHeader IN the list
*/
void
EmptyCatalog(CatalogEntry *listHeader)
{
CatalogEntry *current = listHeader;
while (current->next != current->next->next) {
CatalogEntry *removedElement;
removedElement = current->next;
current->next = current->next->next;
if (removedElement->contents) {
free(removedElement->contents);
}
for (unsigned int i = 0; i < removedElement->files; i++) {
free(removedElement->fullFileName[i]);
}
free(removedElement);
}
}
/**
* Find the position in the list and add
*
* \param listHeader IN start of list
* \param contents IN contents to include
*
* \return CatalogEntry if found, NULL otherwise
*/
static CatalogEntry *
InsertInOrder(CatalogEntry *listHeader, const char *contents)
{
CatalogEntry *currentEntry = listHeader;
while (currentEntry->next != currentEntry->next->next) {
CatalogEntry *nextEntry = currentEntry->next;
if (XtcStricmp(nextEntry->contents, contents)>0) {
return InsertIntoCatalogAfter(currentEntry);
}
currentEntry = nextEntry;
}
return InsertIntoCatalogAfter(currentEntry);
}
/**
* Get the existing list element for a content
*
* \param listHeader IN start of list
* \param contents IN contents to search
* \param Do we log error messages or not
*
* \return CatalogEntry if found, NULL otherwise
*/
static CatalogEntry *
IsExistingContents(CatalogEntry *listHeader, const char *contents, BOOL_T silent)
{
CatalogEntry *currentEntry = listHeader->next;
while (currentEntry != currentEntry->next) {
if (!XtcStricmp(currentEntry->contents, contents)) {
if (!silent)
printf("%s already exists in %s\n", contents, currentEntry->fullFileName[0]);
return (currentEntry);
}
currentEntry = currentEntry->next;
}
return (NULL);
}
/**
* Store information about a parameter file. The filename is added to the array
* of files with identical content. If not already present, in addition
* the content is stored
*
* \param entry existing entry to be updated
* \param path filename to add
* \param contents contents description
*/
static void
UpdateCatalogEntry(CatalogEntry *entry, char *path, char *contents)
{
if (!entry->contents) {
entry->contents = strdup(contents);
}
if (entry->files < MAXFILESPERCONTENT) {
entry->fullFileName[entry->files++] = strdup(path);
} else {
AbortProg("Number of file with same content too large!", NULL);
}
}
/**
* Create the list for the catalog entries
*
* \return
*/
static CatalogEntry *
CreateCatalog()
{
CatalogEntry *catalog = InitCatalog();
return (catalog);
}
static IndexEntry *
CreateIndexTable(unsigned int capacity)
{
IndexEntry *index = (IndexEntry *)malloc(capacity * sizeof(IndexEntry));
return (index);
}
/**
* Scan opened directory for the next parameter file
*
* \param dir IN opened directory handle
* \param dirName IN name of directory
* \param fileName OUT fully qualified filename
*
* \return TRUE if file found, FALSE if not
*/
static bool
GetNextParameterFile(DIR *dir, const char *dirName, char **fileName)
{
bool done = false;
bool res = false;
/*
* get all files from the directory
*/
while (!done) {
struct stat fileState;
struct dirent *ent;
ent = readdir(dir);
if (ent) {
if (!XtcStricmp(FindFileExtension(ent->d_name), "xtp")) {
/* create full file name and get the state for that file */
MakeFullpath(fileName, dirName, ent->d_name, NULL);
if (stat(*fileName, &fileState) == -1) {
fprintf(stderr, "Error getting file state for %s\n", *fileName);
continue;
}
/* ignore any directories */
if (!(fileState.st_mode & S_IFDIR)) {
done = true;
res = true;
}
}
} else {
done = true;
res = false;
}
}
return (res);
}
/**
* Scan a directory for parameter files. For each file found the CONTENTS is
* read and added to the list *
*
* \param insertAfter IN starting point for the list of files
* \param dirName IN directory to be scanned
*
* \return pointer to the last element(?)
*/
static CatalogEntry *
ScanDirectory(CatalogEntry *catalog, const char *dirName)
{
DIR *d;
CatalogEntry *newEntry = catalog;
d = opendir(dirName);
if (d) {
char *fileName = NULL;
while (GetNextParameterFile(d, dirName, &fileName)) {
CatalogEntry *existingEntry;
char *contents = GetParameterFileContent(fileName);
if ((existingEntry = IsExistingContents(catalog, contents,FALSE))) {
printf("Duplicate CONTENTS record in parameter file %s\n", fileName);
if (strcmp(existingEntry->fullFileName[existingEntry->files-1],fileName))
UpdateCatalogEntry(existingEntry, fileName, contents);
} else {
newEntry = InsertInOrder(catalog,contents);
UpdateCatalogEntry(newEntry, fileName, contents);
}
free(contents);
free(fileName);
fileName = NULL;
}
closedir(d);
}
return (newEntry);
}
/**
* Comparison function for IndexEntries used by qsort()
*
* \param entry1 IN
* \param entry2 IN
* \return per C runtime conventions
*/
static int
CompareIndex(const void *entry1, const void *entry2)
{
IndexEntry index1 = *(IndexEntry *)entry1;
IndexEntry index2 = *(IndexEntry *)entry2;
return (strcoll(index1.keyWord, index2.keyWord));
}
/*!
* Filter keywords. Current rules:
* - single character string that only consist of a punctuation char
*
* \param word IN keyword
* \return true if any rule applies, false otherwise
*/
bool
FilterKeyword(char *word)
{
if (strlen(word) == 1 && strpbrk(word, PUNCTUATION )) {
return(true);
}
return(false);
}
/**
* Create the keyword index from a list of parameter files
*
* \param catalog IN list of parameter files
* \param index IN index table to be filled
* \param pointer IN/OUT array of words that are indexed
* \param capacityOfIndex IN total maximum of keywords
* \return number of indexed keywords
*/
static unsigned
CreateContentsIndex(CatalogEntry *catalog, IndexEntry *index, void** words_array,
unsigned capacityOfIndex)
{
CatalogEntry *currentEntry = catalog->next;
unsigned totalMemory = 0;
size_t wordCount = 0;
char *wordList;
char *wordListPtr;
while (currentEntry != currentEntry->next) {
totalMemory += strlen(currentEntry->contents) + 1;
currentEntry = currentEntry->next;
}
wordList = malloc((totalMemory + 1) * sizeof(char));
*words_array = (void*)wordList;
wordListPtr = wordList;
currentEntry = catalog->next;
while (currentEntry != currentEntry->next) {
char *word;
char *content = strdup(currentEntry->contents);
word = strtok(content, " \t\n\r");
while (word && wordCount < capacityOfIndex) {
strcpy(wordListPtr, word);
char *p = wordListPtr;
for (; *p; ++p) {
*p = tolower(*p);
}
if (!FilterKeyword(wordListPtr)) {
index[wordCount].value = currentEntry;
index[wordCount].keyWord = wordListPtr;
wordListPtr += strlen(word) + 1;
wordCount++;
if (wordCount >= capacityOfIndex) {
AbortProg("Too many keywords were used!", NULL);
}
}
word = strtok(NULL, " \t\n\r");
}
free(content);
currentEntry = currentEntry->next;
}
*wordListPtr = '\0';
qsort((void*)index, wordCount, sizeof(IndexEntry), CompareIndex);
return (wordCount);
}
/**
* A recursive binary search function. It returns location of x in
* given array arr[l..r] is present, otherwise -1
* Taken from http://www.geeksforgeeks.org/binary-search/ and modified
*
* \param arr IN array to search
* \param l IN starting index
* \param r IN highest index in array
* \param key IN key to search
* \return index if found, -1 otherwise
*/
static int SearchInIndex(IndexEntry arr[], int l, int r, char *key)
{
if (r >= l) {
int mid = l + (r - l) / 2;
int res = XtcStricmp(key, arr[mid].keyWord);
// If the element is present at the middle itself
if (!res) {
return mid;
}
// If the array size is 1
if (r == 0) {
return -1;
}
// If element is smaller than mid, then it can only be present
// in left subarray
if (res < 0) {
return SearchInIndex(arr, l, mid - 1, key);
}
// Else the element can only be present in right subarray
return SearchInIndex(arr, mid + 1, r, key);
}
// We reach here when element is not present in array
return -1;
}
/**
* Inserts a key in arr[] of given capacity. n is current
* size of arr[]. This function returns n+1 if insertion
* is successful, else n.
* Taken from http ://www.geeksforgeeks.org/search-insert-and-delete-in-a-sorted-array/ and modified
*/
int InsertSorted(CatalogEntry *arr[], int n, CatalogEntry *key, int capacity)
{
// Cannot insert more elements if n is already
// more than or equal to capcity
if (n >= capacity) {
return n;
}
int i;
for (i = n - 1; (i >= 0 && arr[i] > key); i--) {
arr[i + 1] = arr[i];
}
arr[i + 1] = key;
return (n + 1);
}
/**
* Comparison function for CatalogEntries used by qsort()
*
* \param entry1 IN
* \param entry2 IN
* \return per C runtime conventions
*/
static int
CompareResults(const void *entry1, const void *entry2)
{
CatalogEntry * index1 = *(CatalogEntry **)entry1;
CatalogEntry * index2 = *(CatalogEntry **)entry2;
return (strcoll(index1->contents, index2->contents));
}
/**
* Search the index for a keyword. The index is assumed to be sorted. So after one entry
* is found, neighboring entries up and down are checked as well. The total result set
* is placed into an array and returned. This array has to be free'd by the caller.
*
* \param index IN index list
* \param length IN number of entries index
* \param search IN search string
* \param resultCount OUT count of found entries
* \return array of found catalog entries, NULL if none found
*/
static int findAll = 1;
unsigned int
FindWord(IndexEntry *index, int length, char *search, CatalogEntry ***entries)
{
CatalogEntry **result; //Array of pointers to Catalog Entries
int found;
int foundElements = 0;
*entries = NULL;
//Get all the entries back for generic search or if "generic find"
if (findAll || !search || (search[0] == '*') || (search[0] == '\0')) {
result = malloc((length) * sizeof(CatalogEntry *));
for (int i = 0; i < length; i++) {
result[i] = index[i].value;
}
*entries = result;
return length;
}
found = SearchInIndex(index, 0, length, search);
if (found >= 0) {
int lower = found;
int upper = found;
int i;
while (lower > 0 && !XtcStricmp(index[lower-1].keyWord, search)) {
lower--;
}
while (upper < length - 1 && !XtcStricmp(index[upper + 1].keyWord, search)) {
upper++;
}
foundElements = 1 + upper - lower;
result = malloc((foundElements) * sizeof(CatalogEntry *));
for (i = 0; i < foundElements; i++) {
result[i] = index[i+lower].value;
}
qsort((void*)result, foundElements, sizeof(void *), CompareResults);
*entries = result;
}
return (foundElements);
}
/**
* Create and initialize the data structure for the track library
*
* \param trackLibrary OUT the newly allocated track library
* \return TRUE on success
*/
TrackLibrary *
InitLibrary(void)
{
TrackLibrary *trackLib = malloc(sizeof(TrackLibrary));
if (trackLib) {
trackLib->catalog = CreateCatalog();
trackLib->index = NULL;
trackLib->wordCount = 0;
trackLib->trackTypeCount = 0;
}
return (trackLib);
}
/**
* Scan directory and all parameter files found to the catalog
*
* \param trackLib IN the catalog
* \param directory IN directory to scan
* \return number of files found
*/
bool
GetTrackFiles(TrackLibrary *trackLib, char *directory)
{
ScanDirectory(trackLib->catalog, directory);
trackLib->trackTypeCount = CountCatalogEntries(trackLib->catalog);
return (trackLib->trackTypeCount);
}
/**
* Add a list of parameters files to a catalog. This function is
* called when the user selects files in the file selector.
*
* \param files IN count of files
* \param fileName IN array of filenames
* \param data IN pointer to the catalog
* \return alwqys TRUE
*/
int GetParameterFileInfo(
int files,
char ** fileName,
void * data)
{
CatalogEntry *catalog = (CatalogEntry *)data;
assert(fileName != NULL);
assert(files > 0);
assert(data != NULL);
for (int i = 0; i < files; i++) {
CatalogEntry *newEntry;
char *contents = GetParameterFileContent(fileName[i]);
if (!(newEntry = IsExistingContents(catalog, contents,TRUE))) {
newEntry = InsertIntoCatalogAfter(catalog);
}
UpdateCatalogEntry(newEntry, fileName[i], contents);
free(contents);
}
return (TRUE);
}
/**
* Create the search index from the contents description for the whole catalog.
* A fixed number of words are added to the index. See ESTIMATED_CONTENTS_WORDS
*
* \param trackLib IN the catalog
* \return the number of words indexed
*/
unsigned
CreateLibraryIndex(TrackLibrary *trackLib)
{
trackLib->index = CreateIndexTable(trackLib->trackTypeCount *
ESTIMATED_CONTENTS_WORDS);
trackLib->wordCount = CreateContentsIndex(trackLib->catalog, trackLib->index,
&trackLib->words_array,
ESTIMATED_CONTENTS_WORDS * trackLib->trackTypeCount);
return (trackLib->wordCount);
}
void
DeleteLibraryIndex(TrackLibrary *trackLib)
{
free(trackLib->index);
trackLib->index = NULL;
free(trackLib->words_array);
trackLib->wordCount = 0;
}
/**
* Create the library and index of parameter files in a given directory.
*
* \param directory IN directory to scan
* \return NULL if error or empty directory, else library handle
*/
TrackLibrary *
CreateLibrary(char *directory)
{
TrackLibrary *library;
library = InitLibrary();
if (library) {
if (!GetTrackFiles(library, directory)) {
return (NULL);
}
CreateLibraryIndex(library);
}
return (library);
}
void
DeleteLibrary(TrackLibrary* library)
{
DeleteLibraryIndex(library);
free(library);
}
// Case insensitive comparison
char* stristr( const char* haystack, const char* needle )
{
int c = tolower((unsigned char)*needle);
if (c == '\0')
return (char *)haystack;
for (; *haystack; haystack++) {
if (tolower((unsigned char)*haystack) == c) {
for (size_t i = 0;;) {
if (needle[++i] == '\0')
return (char *)haystack;
if (tolower((unsigned char)haystack[i]) != tolower((unsigned char)needle[i]))
break;
}
}
}
return NULL;
}
/**
* Search the library for a keyword string and return the result list
*
* First the index is searched for the first word and then each "hit" is matched
* to the entire search string
*
* Null, Blank and "*" match all entries
*
* The list is de-duped of repeat of filenames as the same file might appear in
* more than once
*
* \param library IN the library
* \param searchExpression IN keyword to search for
* \param resultEntries IN list header for result list
* \return number of found entries
*/
unsigned
SearchLibrary(TrackLibrary *library, char *searchExpression,
CatalogEntry *resultEntries)
{
CatalogEntry **entries;
CatalogEntry * newEntry = resultEntries;
unsigned entryCount;
char * word;
word = strdup(searchExpression);
//word = strtok(word," \t");
if (library->index == NULL || library->wordCount == 0) {
return (0);
}
entryCount = FindWord(library->index, library->wordCount, word,
&entries);
int count= 0;
if (entryCount) {
unsigned int i = 0;
while (i < entryCount) {
char * match;
//Check if entire String Matches
if (!searchExpression || !word || (word[0] == '*') || (word[0] == '\0') ||
(match = stristr(entries[i]->contents,searchExpression))) {
CatalogEntry * existingEntry;
existingEntry = IsExistingContents(resultEntries, entries[i]->contents, TRUE);
//Same FileName already in one of the entries?
BOOL_T found = FALSE;
if (existingEntry) {
for (unsigned int j=0;j<existingEntry->files;j++) {
if (!strcmp(existingEntry->fullFileName[j],entries[i]->fullFileName[entries[i]->files-1])) {
found=TRUE;
break;
}
}
if (found == TRUE ) {
i++;
continue;
}
UpdateCatalogEntry(existingEntry, entries[i]->fullFileName[(entries[i]->files- 1)],
entries[i]->contents);
} else {
newEntry = InsertInOrder(resultEntries,entries[i]->contents);
UpdateCatalogEntry(newEntry, entries[i]->fullFileName[(entries[i]->files- 1)],
entries[i]->contents);
}
count++;
}
i++;
}
}
free(word);
if (entries)
free(entries); //Clean-up after search
return (count);
}
/**
* Get the contents description from a parameter file. Returned string has to be freed after use.
*
* \param file IN xtpfile
* \return pointer to found contents or NULL if not present
*/
char *
GetParameterFileContent(char *file)
{
FILE *fh;
char *result = NULL;
fh = fopen(file, "rt");
if (fh) {
bool found = false;
while (!found) {
char buffer[512];
if (fgets(buffer, sizeof(buffer), fh)) {
char *ptr = strtok(buffer, " \t");
if (!XtcStricmp(ptr, CONTENTSCOMMAND)) {
/* if found, store the rest of the line and the filename */
ptr = ptr+strlen(CONTENTSCOMMAND)+1;
ptr = strtok(ptr, "\r\n");
result = strdup(ptr);
#ifdef WINDOWS
ConvertUTF8ToSystem(result);
#endif // WINDOWS
found = true;
}
} else {
fprintf(stderr, "Nothing found in %s\n", file);
found = true;
}
}
fclose(fh);
}
return(result);
}