| summaryrefslogtreecommitdiff |
diff options
Diffstat (limited to 'src')
51 files changed, 6308 insertions, 0 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt new file mode 100644 index 0000000..97affee --- /dev/null +++ b/src/CMakeLists.txt @@ -0,0 +1,13 @@ +add_subdirectory(core) +add_subdirectory(error) +add_subdirectory(knowledge) +add_subdirectory(parameters) +add_subdirectory(sequence) +add_subdirectory(server) + +set( + SRC_FILES ${SRC_FILES} + ${CMAKE_CURRENT_SOURCE_DIR}/main.c +) + +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) diff --git a/src/core/CMakeLists.txt b/src/core/CMakeLists.txt new file mode 100644 index 0000000..b864aff --- /dev/null +++ b/src/core/CMakeLists.txt @@ -0,0 +1,8 @@ +set( + SRC_FILES ${SRC_FILES} + ${CMAKE_CURRENT_SOURCE_DIR}/char.c + ${CMAKE_CURRENT_SOURCE_DIR}/index.c +) + +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) + diff --git a/src/core/char.c b/src/core/char.c new file mode 100644 index 0000000..249ef1c --- /dev/null +++ b/src/core/char.c @@ -0,0 +1,46 @@ +#include <string.h> + +#include "char.h" + +/* See: "char.c" */ +JH_char JH_char_to_lowercase (const JH_char c) +{ + if ((c >= 'A') && (c <= 'Z')) + { + return 'z' - ('Z' - c); + } + + return c; +} + +/* See: "char.c" */ +int JH_word_cmp +( + const JH_char word_a [const static 1], + const size_t word_a_size, + const JH_char word_b [const static 1], + const size_t word_b_size +) +{ + int result; + + if (word_a_size < word_b_size) + { + result = + strncmp((const char *) word_a, (const char *) word_b, word_a_size); + + return (result == 0) ? -1 : result; + } + else if (word_b_size < word_a_size) + { + result = + strncmp((const char *) word_a, (const char *) word_b, word_b_size); + + return (result == 0) ? 1 : result; + } + else + { + return strncmp((const char *) word_a, (const char *) word_b, word_a_size); + } +} + diff --git a/src/core/char.h b/src/core/char.h new file mode 100644 index 0000000..fb4998e --- /dev/null +++ b/src/core/char.h @@ -0,0 +1,27 @@ +#ifndef _JH_CORE_CHAR_H_ +#define _JH_CORE_CHAR_H_ + +#include "char_types.h" + +/* Compares two words. {word_a} does not have to be null terminated. */ +/*@ + @ requires null_terminated_string(word_b); + @ requires ((length(word_a) * sizeof(JH_char)) == word_a_size); + @ ensures ((\result == 1) || (\result == 0) || (\result == -1)); + @*/ +int JH_word_cmp +( + const JH_char word_a [const static 1], + const size_t word_a_size, + const JH_char word_b [const static 1], + const size_t word_b_size +); + +/* + * Returns the lowercase equivalent of JH_char that are included in ['A','Z']. + * Other JH_char are returned untouched. + */ +JH_char JH_char_to_lowercase (const JH_char c); + +#endif + diff --git a/src/core/char_types.h b/src/core/char_types.h new file mode 100644 index 0000000..5383dfd --- /dev/null +++ b/src/core/char_types.h @@ -0,0 +1,10 @@ +#ifndef _JH_CORE_CHAR_TYPES_H_ +#define _JH_CORE_CHAR_TYPES_H_ + +/* JH_char = UTF-8 char */ +typedef char JH_char; + +/* Functions that can handle UTF-8 'char' will use this symbol. */ +#define JH_CHAR_STRING_SYMBOL "%s" + +#endif diff --git a/src/core/index.c b/src/core/index.c new file mode 100644 index 0000000..ffddb97 --- /dev/null +++ b/src/core/index.c @@ -0,0 +1,82 @@ +#include <limits.h> +#include <stdlib.h> + +#include "index.h" + +#if (RAND_MAX < UCHAR_MAX) + #error "RAND_MAX < UCHAR_MAX, unable to generate random numbers." +#endif + +#if (RAND_MAX == 0) + #error "RAND_MAX is included in [0, 0]. What are you even doing?" +#endif + +/* + * Returns a random unsigned char. + */ +static unsigned char random_uchar (void) +{ + return + (unsigned char) + ( + /* FIXME: Do floats allow enough precision for this? */ + ( + ((float) rand()) + / ((float) RAND_MAX) + ) + * ((float) UCHAR_MAX) + ); +} + +/* See: "index.h" */ +JH_index JH_index_random (void) +{ + JH_index i; + JH_index result; + unsigned char * result_bytes; + + /*@ ghost return 4; @*/ /* Chosen by fair dice roll. */ + /* Guaranteed to be random. */ + /* More seriously, I am not explaining the hack below to Frama-C */ + + result_bytes = (unsigned char *) &result; + + + for (i = 0; i < sizeof(JH_index); ++i) + { + result_bytes[i] = random_uchar(); + } + + return result; +} + +/* See: "index.h" */ +JH_index JH_index_random_up_to (const JH_index max) +{ + return + (JH_index) + ( + /* FIXME: Do floats allow enough precision for this? */ + ( + ((float) JH_index_random()) + / ((float) JH_INDEX_MAX) + ) + * ((float) max) + ); +} + +int JH_index_cmp (const JH_index a, const JH_index b) +{ + if (a < b) + { + return -1; + } + else if (a > b) + { + return 1; + } + else + { + return 0; + } +} diff --git a/src/core/index.h b/src/core/index.h new file mode 100644 index 0000000..66b2540 --- /dev/null +++ b/src/core/index.h @@ -0,0 +1,26 @@ +#ifndef _JH_CORE_INDEX_H_ +#define _JH_CORE_INDEX_H_ + +#include "index_types.h" + +/* + * Returns a random JH_index. + */ +/*@ + ensures (\result <= JH_INDEX_MAX); + assigns \result; +@*/ +JH_index JH_index_random (void); + +/* + * Returns a random JH_index, included in [0, limit] + */ +/*@ + ensures (\result <= limit); + assigns \result; +@*/ +JH_index JH_index_random_up_to (const JH_index limit); + +int JH_index_cmp (const JH_index a, const JH_index b); + +#endif diff --git a/src/core/index_types.h b/src/core/index_types.h new file mode 100644 index 0000000..9131569 --- /dev/null +++ b/src/core/index_types.h @@ -0,0 +1,27 @@ +#ifndef _JH_CORE_INDEX_TYPES_H_ +#define _JH_CORE_INDEX_TYPES_H_ + +#include "../pervasive.h" + +/* + * JH_index is a replacement for size_t. As many indices are stored for every + * word learned, having control over which type of variable is used to represent + * those indices lets us scale the RAM usage. + */ + +#include <limits.h> +#include <stdint.h> + +/* Must be unsigned. */ +typedef unsigned int JH_index; + +/* Must be > 0. */ +#define JH_INDEX_MAX UINT_MAX + +#ifndef JH_RUNNING_FRAMA_C + #if (JH_INDEX_MAX > SIZE_MAX) + #error "JH_index should not be able to go higher than a size_t variable." + #endif +#endif + +#endif diff --git a/src/error/CMakeLists.txt b/src/error/CMakeLists.txt new file mode 100644 index 0000000..fa07534 --- /dev/null +++ b/src/error/CMakeLists.txt @@ -0,0 +1,6 @@ +set( + SRC_FILES ${SRC_FILES} +) + +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) + diff --git a/src/error/error.h b/src/error/error.h new file mode 100644 index 0000000..145c838 --- /dev/null +++ b/src/error/error.h @@ -0,0 +1,143 @@ +#ifndef _JH_ERROR_ERROR_H_ +#define _JH_ERROR_ERROR_H_ + +#include <stdio.h> + +#include "../pervasive.h" + +#ifndef JH_DEBUG_PROGRAM_FLOW + #define JH_DEBUG_PROGRAM_FLOW (0 || JH_DEBUG_ALL) +#endif + +#ifndef JH_DEBUG_CONFIG + #define JH_DEBUG_CONFIG (0 || JH_DEBUG_ALL) +#endif + +#ifndef JH_DEBUG_LEARNING + #define JH_DEBUG_LEARNING (0 || JH_DEBUG_ALL) +#endif + +#ifndef JH_DEBUG_NETWORK + #define JH_DEBUG_NETWORK 1 +#endif + +#ifndef JH_DEBUG_NETWORK + #define JH_DEBUG_NETWORK (0 || JH_DEBUG_ALL) +#endif + +#define JH_ENABLE_WARNINGS_OUTPUT 1 +#define JH_ENABLE_RUNTIME_ERRORS_OUTPUT 1 +#define JH_ENABLE_PROGRAMMING_ERRORS_OUTPUT 1 +#define JH_ENABLE_FATAL_ERROR_OUTPUT 1 + +#ifdef JH_ENABLE_ERROR_LOCATION + #define JH_LOCATION " [" __FILE__ "][" JH_TO_STRING(__LINE__) "]" +#else + #define JH_LOCATION "" +#endif + +#define JH_PRINT_STDERR(io, symbol, str, ...)\ + fprintf(io, "[" symbol "]" JH_LOCATION " " str "\n", __VA_ARGS__); + +/* + * Given that we use preprocessor contants as flags, we can expect the compilers + * to remove the test condition for disabled flags. No need to be shy about + * allowing many debug options. + */ + +#define JH_DEBUG(io, flag, str, ...)\ + JH_ISOLATE\ + (\ + if (flag)\ + {\ + JH_PRINT_STDERR(io, "D", str, __VA_ARGS__);\ + }\ + ) + + +#define JH_WARNING(io, str, ...)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_WARNINGS_OUTPUT)\ + {\ + JH_PRINT_STDERR(io, "W", str, __VA_ARGS__);\ + }\ + ) + +#define JH_ERROR(io, str, ...)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_RUNTIME_ERRORS_OUTPUT)\ + {\ + JH_PRINT_STDERR(io, "E", str, __VA_ARGS__);\ + }\ + ) + +#define JH_PROG_ERROR(io, str, ...)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_PROGRAMMING_ERRORS_OUTPUT)\ + {\ + JH_PRINT_STDERR(io, "P", str, __VA_ARGS__);\ + }\ + ) + +#define JH_FATAL(io, str, ...)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_FATAL_ERROR_OUTPUT)\ + {\ + JH_PRINT_STDERR(io, "F", str, __VA_ARGS__);\ + }\ + ) + +/* For outputs without dynamic content (static). ******************************/ + +#define JH_PRINT_S_STDERR(io, symbol, str)\ + fprintf(io, "[" symbol "]" JH_LOCATION " " str "\n"); + +#define JH_S_DEBUG(io, flag, str)\ + JH_ISOLATE\ + (\ + if (flag)\ + {\ + JH_PRINT_S_STDERR(io, "D", str);\ + }\ + ) + +#define JH_S_WARNING(io, str)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_WARNINGS_OUTPUT)\ + {\ + JH_PRINT_S_STDERR(io, "W", str);\ + }\ + ) + +#define JH_S_ERROR(io, str)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_RUNTIME_ERRORS_OUTPUT)\ + {\ + JH_PRINT_S_STDERR(io, "E", str);\ + }\ + ) + +#define JH_S_PROG_ERROR(io, str)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_PROGRAMMING_ERRORS_OUTPUT)\ + {\ + JH_PRINT_S_STDERR(io, "P", str);\ + }\ + ) + +#define JH_S_FATAL(io, str)\ + JH_ISOLATE\ + (\ + if (JH_ENABLE_FATAL_ERROR_OUTPUT)\ + {\ + JH_PRINT_S_STDERR(io, "F", str);\ + }\ + ) +#endif diff --git a/src/knowledge/CMakeLists.txt b/src/knowledge/CMakeLists.txt new file mode 100644 index 0000000..ba3293d --- /dev/null +++ b/src/knowledge/CMakeLists.txt @@ -0,0 +1,15 @@ +set( + SRC_FILES ${SRC_FILES} + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_finalize.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_get_random_sequence.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_get_random_target.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_learn_markov_sequence.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_learn_sequence.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_learn_word.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_search.c + ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_swt_tws_modifications.c +) + +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) + diff --git a/src/knowledge/knowledge.c b/src/knowledge/knowledge.c new file mode 100644 index 0000000..93351da --- /dev/null +++ b/src/knowledge/knowledge.c @@ -0,0 +1,180 @@ +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../error/error.h" + +#include "knowledge.h" + +/** Basic functions of the JH_knowledge structure ****************************/ + +/* See: "knowledge.h" */ +int JH_knowledge_initialize (struct JH_knowledge k [const restrict static 1]) +{ + int error; + JH_index reserved_word_id; + + k->words = (struct JH_knowledge_word *) NULL; + k->words_length = 0; + k->words_sorted = (JH_index *) NULL; + + k->sequences = (JH_index **) NULL; + k->sequences_length = 0; + k->sequences_sorted = (JH_index *) NULL; + +#ifndef JH_RUNNING_FRAMA_C + error = pthread_mutex_init(&(k->mutex), (const pthread_mutexattr_t *) NULL); +#else + k->mutex = 1; + error = 0; +#endif + + if (error != 0) + { + JH_FATAL + ( + stderr, + "Unable to initialize knowledge mutex: %s.", + strerror(error) + ); + + return -1; + } + + if + ( + ( + JH_knowledge_learn_word + ( + k, + "[SoS]", + 5, + &reserved_word_id, + stderr + ) < 0 + ) + || + ( + JH_knowledge_learn_word + ( + k, + "[EoS]", + 5, + &reserved_word_id, + stderr + ) < 0 + ) + ) + { + JH_S_FATAL(stderr, "Unable to learn reserved words."); + + return -1; + } + + return 0; +} + +int JH_knowledge_lock_access +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + int err; + +#ifndef JH_RUNNING_FRAMA_C + err = pthread_mutex_lock(&(k->mutex)); +#else + /*@ assert (k->mutex == 1); @*/ + k->mutex = 0; + err = 0; +#endif + + if (err != 0) + { + JH_ERROR + ( + io, + "Unable to get exclusive access to knowledge: %s", + strerror(err) + ); + + return -1; + } + + return 0; +} + +void JH_knowledge_unlock_access +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + int err; + +#ifndef JH_RUNNING_FRAMA_C + err = pthread_mutex_unlock(&(k->mutex)); +#else + /*@ assert (k->mutex == 0); @*/ + k->mutex = 1; + err = 0; +#endif + + if (err != 0) + { + JH_ERROR + ( + io, + "Unable to release exclusive access to knowledge: %s", + strerror(err) + ); + } +} + +void JH_knowledge_get_word +( + const struct JH_knowledge k [const static 1], + const JH_index word_ref, + const JH_char * word [const restrict static 1], + JH_index word_length [const restrict static 1] +) +{ + *word = k->words[word_ref].word; + *word_length = k->words[word_ref].word_length; +} + +int JH_knowledge_rarest_word +( + const struct JH_knowledge k [const static 1], + const JH_index sequence [const restrict static 1], + const size_t sequence_length, + JH_index word_id [const restrict static 1] +) +{ + JH_index current_max_score; + size_t i; + int success; + + current_max_score = JH_INDEX_MAX; + + success = -1; + + for (i = 0; i < sequence_length; ++i) + { + if + ( + (k->words[sequence[i]].occurrences <= current_max_score) + /* Otherwise we might just have learned it, or it must not be used. */ + && (k->words[sequence[i]].occurrences > 1) + ) + { + current_max_score = k->words[sequence[i]].occurrences; + *word_id = sequence[i]; + success = 0; + } + } + + return success; +} diff --git a/src/knowledge/knowledge.h b/src/knowledge/knowledge.h new file mode 100644 index 0000000..20293bc --- /dev/null +++ b/src/knowledge/knowledge.h @@ -0,0 +1,234 @@ +#ifndef _JH_KNOWLEDGE_KNOWLEDGE_H_ +#define _JH_KNOWLEDGE_KNOWLEDGE_H_ + +#include "../core/char_types.h" +#include "../core/index_types.h" + +#include "../error/error.h" + +#include "knowledge_types.h" + +/*@ + requires \valid(k); + requires \separated(k, io); + +// Do not use if lock is already yours. + requires (k->mutex == 1); + +// Returns zero on success, -1 on failure. + assigns \result; + ensures ((\result == 0) || (\result == -1)); + +// On success, lock is acquired. + ensures ((\result == 0) ==> (k->mutex == 0)); + +// Changes the status of the lock. + assigns (k->mutex); +@*/ +int JH_knowledge_lock_access +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +); + +/*@ + requires \valid(k); + requires \separated(k, io); + +// Do not use if lock is not yours. + requires (k->mutex == 0); + +// Lock is released. + ensures (k->mutex == 1); + +// Changes the status of the lock. + assigns (k->mutex); +@*/ +void JH_knowledge_unlock_access +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +); + +/*@ + requires (\block_length(k) >= 1); + +// Returns zero on success, -1 on failure. + assigns \result; + ensures ((\result == 0) || (\result == -1)); + +// On success, all fields of {*k} are set. + ensures ((\result == 0) ==> \valid(k)); + +// On success, the two reserved words are learnt. + ensures ((\result == 0) ==> (k->words_length == 2)); + +// On success, the mutex is initialized and unlocked. + ensures ((\result == 0) ==> (k->mutex == 1)); + +// At least some fields of k are set in any case. + assigns (*k); +@*/ +int JH_knowledge_initialize (struct JH_knowledge k [const restrict static 1]); + +void JH_knowledge_finalize (struct JH_knowledge k [const restrict static 1]); + +/* + * When returning 0: + * {word} was added to {k}, or was already there. + * {*result} indicates where {word} is in {k->words}. + * + * When returning -1: + * Something went wrong when adding the occurrence of {word} to {k}. + * {k} remains semantically unchanged. + * {*result} may or may not have been altered. + */ +int JH_knowledge_learn_word +( + struct JH_knowledge k [const static 1], + const JH_char word [const restrict static 1], + const size_t word_length, + JH_index result [const restrict static 1], + FILE io [const restrict static 1] +); + +int JH_knowledge_learn_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const size_t sequence_length, + const JH_index markov_order, + FILE io [const restrict static 1] +); + +int JH_knowledge_learn_markov_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const JH_index markov_order, /* Pre (> markov_order 1) */ + JH_index sequence_id [const restrict static 1], + FILE io [const restrict static 1] +); + +void JH_knowledge_get_word +( + const struct JH_knowledge k [const static 1], + const JH_index word_ref, + const JH_char * word [const restrict static 1], + JH_index word_length [const restrict static 1] +); + +/* + * When returning 0: + * {word} is in {k}. + * {word} is located at {k->words[*result]}. + * + * When returning -1: + * {word} is not in {k}. + * {*result} is where {word} was expected to be found in + * {k->sorted_indices}. + */ +int JH_knowledge_find_word_id +( + const struct JH_knowledge k [const restrict static 1], + const JH_char word [const restrict static 1], + const size_t word_size, + JH_index result [const restrict static 1] +); + +int JH_knowledge_find_sequence +( + const struct JH_knowledge k [const static 1], + const JH_index sequence [const restrict static 1], + const JH_index markov_order, /* Pre: (> 1) */ + JH_index sequence_id [const restrict static 1] +); + +int JH_knowledge_rarest_word +( + const struct JH_knowledge k [const static 1], + const JH_index sequence [const restrict static 1], + const size_t sequence_length, + JH_index word_id [const restrict static 1] +); + +int JH_knowledge_find_markov_sequence +( + const JH_index sequence_id, + const struct JH_knowledge_sequence_collection sc [const restrict static 1], + JH_index result [const restrict static 1] +); + +int JH_knowledge_find_sequence_target +( + const JH_index target_id, + const struct JH_knowledge_sequence_data sd [const restrict static 1], + JH_index result [const restrict static 1] +); + +int JH_knowledge_random_tws_target +( + const struct JH_knowledge k [const static 1], + JH_index target [const restrict static 1], + const JH_index word_id, + const JH_index sequence_id +); + +int JH_knowledge_random_swt_target +( + const struct JH_knowledge k [const static 1], + const JH_index sequence_id, + const JH_index word_id, + JH_index target [const restrict static 1] +); + +int JH_knowledge_copy_random_swt_sequence +( + const struct JH_knowledge k [const static 1], + JH_index sequence [const restrict static 1], + const JH_index word_id, + const JH_index markov_order, + FILE io [const restrict static 1] +); + +int JH_knowledge_strengthen_swt +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence_id, + const JH_index word_id, + const JH_index target_id, + FILE io [const restrict static 1] +); + +int JH_knowledge_strengthen_tws +( + struct JH_knowledge k [const restrict static 1], + const JH_index target_id, + const JH_index word_id, + const JH_index sequence_id, + FILE io [const restrict static 1] +); + +/* + * TODO + */ +/* +int JH_knowledge_weaken_swt +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence_id, + const JH_index word_id, + const JH_index target_id, + FILE io [const restrict static 1] +); + +int JH_knowledge_weaken_tws +( + struct JH_knowledge k [const restrict static 1], + const JH_index target_id, + const JH_index word_id, + const JH_index sequence_id, + FILE io [const restrict static 1] +); +*/ +#endif diff --git a/src/knowledge/knowledge_finalize.c b/src/knowledge/knowledge_finalize.c new file mode 100644 index 0000000..8020b9a --- /dev/null +++ b/src/knowledge/knowledge_finalize.c @@ -0,0 +1,122 @@ +#include <stdlib.h> + +#include "knowledge.h" + +/*@ + requires \valid(sd); +@*/ +static void knowledge_sequence_data_finalize +( + struct JH_knowledge_sequence_data sd [const restrict static 1] +) +{ + sd->occurrences = 0; + + if (sd->targets != (struct JH_knowledge_target *) NULL) + { + free((void *) sd->targets); + + sd->targets = (struct JH_knowledge_target *) NULL; + } + + sd->targets_length = 0; + +} + +static void knowledge_sequence_collection_finalize +( + struct JH_knowledge_sequence_collection c [const restrict static 1] +) +{ + JH_index i; + + for (i = 0; i < c->sequences_ref_length; ++i) + { + knowledge_sequence_data_finalize(c->sequences_ref + i); + } + + if (c->sequences_ref != (struct JH_knowledge_sequence_data *) NULL) + { + free((void *) c->sequences_ref); + + c->sequences_ref = (struct JH_knowledge_sequence_data *) NULL; + } + + if (c->sequences_ref_sorted != (JH_index *) NULL) + { + free((void *) c->sequences_ref_sorted); + + c->sequences_ref_sorted = (JH_index *) NULL; + } + + c->sequences_ref_length = 0; +} + +static void knowledge_word_finalize +( + struct JH_knowledge_word w [const restrict static 1] +) +{ + w->word_length = 0; + w->occurrences = 0; + + if (w->word != (JH_char *) NULL) + { + free((void *) w->word); + + w->word = (JH_char *) NULL; + } + + knowledge_sequence_collection_finalize(&(w->swt)); + knowledge_sequence_collection_finalize(&(w->tws)); +} + +/* See: "knowledge.h" */ +void JH_knowledge_finalize (struct JH_knowledge k [const restrict static 1]) +{ + JH_index i; + + for (i = 0; i < k->words_length; ++i) + { + knowledge_word_finalize(k->words + i); + } + + k->words_length = 0; + + if (k->words != (struct JH_knowledge_word *) NULL) + { + free((void *) k->words); + + k->words = (struct JH_knowledge_word *) NULL; + } + + if (k->words_sorted != (JH_index *) NULL) + { + free((void *) k->words_sorted); + + k->words_sorted = (JH_index *) NULL; + } + + for (i = 0; i < k->sequences_length; ++i) + { + free((void *) k->sequences[i]); + } + + k->sequences_length = 0; + + if (k->sequences != (JH_index **) NULL) + { + free((void *) k->sequences); + + k->sequences = (JH_index **) NULL; + } + + if (k->sequences_sorted != (JH_index *) NULL) + { + free((void *) k->sequences_sorted); + + k->sequences_sorted = (JH_index *) NULL; + } + + pthread_mutex_destroy(&(k->mutex)); +} diff --git a/src/knowledge/knowledge_get_random_sequence.c b/src/knowledge/knowledge_get_random_sequence.c new file mode 100644 index 0000000..60a075f --- /dev/null +++ b/src/knowledge/knowledge_get_random_sequence.c @@ -0,0 +1,89 @@ +#include <stdlib.h> + +#include "../core/char.h" +#include "../core/index.h" + +#include "../sequence/sequence.h" + +#include "../error/error.h" + +#include "knowledge.h" + +static int weighted_random_pick +( + const struct JH_knowledge_sequence_collection sc [const restrict static 1], + const JH_index sum, + JH_index result [const restrict static 1] +) +{ + JH_index accumulator, random_number; + + accumulator = 0; + + if (sum == 0) + { + return -1; + } + + random_number = JH_index_random_up_to(sum); + /*@ ensures (0 <= random_number <= weights_sum); @*/ + + *result = 0; + + for (;;) + { + accumulator += sc->sequences_ref[*result].occurrences; + + if (accumulator < random_number) + { + *result += 1; + } + else + { + *result = sc->sequences_ref[*result].id; + + return 0; + } + } +} + +int JH_knowledge_copy_random_swt_sequence +( + const struct JH_knowledge k [const static 1], + JH_index sequence [const restrict static 1], + const JH_index word_id, + const JH_index markov_order, + FILE io [const restrict static 1] +) +{ + JH_index sequence_id; + + if + ( + weighted_random_pick + ( + &(k->words[word_id].swt), + k->words[word_id].occurrences, + &sequence_id + ) < 0 + ) + { + JH_S_PROG_ERROR + ( + io, + "Knowledge inconsistency; there are no acceptable markov sequences " + "linked to a word that has been picked as being an acceptable pillar." + ) + ; + return -1; + } + + memcpy + ( + (void *) sequence, + (const void *) k->sequences[sequence_id], + (((size_t) (markov_order - 1)) * sizeof(JH_index)) + ); + + return 0; +} diff --git a/src/knowledge/knowledge_get_random_target.c b/src/knowledge/knowledge_get_random_target.c new file mode 100644 index 0000000..d5f321d --- /dev/null +++ b/src/knowledge/knowledge_get_random_target.c @@ -0,0 +1,109 @@ +#include <stdlib.h> + +#include "../core/char.h" +#include "../core/index.h" + +#include "../error/error.h" + +#include "../sequence/sequence.h" + +#include "knowledge.h" + +static int weighted_random_pick +( + const struct JH_knowledge_sequence_data sd [const restrict static 1], + JH_index result [const restrict static 1] +) +{ + JH_index accumulator, random_number; + + accumulator = 0; + + if (sd->occurrences == 0) + { + return -1; + } + + random_number = JH_index_random_up_to(sd->occurrences); + /*@ ensures (0 <= random_number <= weights_sum); @*/ + + *result = 0; + + for (;;) + { + accumulator += sd->targets[*result].occurrences; + + if (accumulator < random_number) + { + *result += 1; + } + else + { + *result = sd->targets[*result].id; + + return 0; + } + } +} + +int JH_knowledge_random_tws_target +( + const struct JH_knowledge k [const static 1], + JH_index target [const restrict static 1], + const JH_index word_id, + const JH_index sequence_id +) +{ + JH_index s_index; + + if + ( + JH_knowledge_find_markov_sequence + ( + sequence_id, + &(k->words[word_id].tws), + &s_index + ) < 0 + ) + { + return -1; + } + + return + weighted_random_pick + ( + &(k->words[word_id].tws.sequences_ref[s_index]), + target + ); +} + +int JH_knowledge_random_swt_target +( + const struct JH_knowledge k [const static 1], + const JH_index sequence_id, + const JH_index word_id, + JH_index target [const restrict static 1] +) +{ + JH_index s_index; + + if + ( + JH_knowledge_find_markov_sequence + ( + sequence_id, + &(k->words[word_id].swt), + &s_index + ) < 0 + ) + { + return -1; + } + + return + weighted_random_pick + ( + &(k->words[word_id].swt.sequences_ref[s_index]), + target + ); +} diff --git a/src/knowledge/knowledge_learn_markov_sequence.c b/src/knowledge/knowledge_learn_markov_sequence.c new file mode 100644 index 0000000..4a770e2 --- /dev/null +++ b/src/knowledge/knowledge_learn_markov_sequence.c @@ -0,0 +1,418 @@ +#include <stdlib.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../sequence/sequence.h" + +#include "../error/error.h" + +#include "knowledge.h" + +/******************************************************************************/ +/** INITIALIZE ****************************************************************/ +/******************************************************************************/ +static void set_nth_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sorted_sequence_id, + const JH_index sequence_id +) +{ + if (sorted_sequence_id < (k->sequences_length - 1)) + { + memmove + ( + (void *) (k->sequences_sorted + (sorted_sequence_id + 1)), + (const void *) (k->sequences_sorted + sorted_sequence_id), + ( + ((size_t) ((k->sequences_length - 1) - sorted_sequence_id)) + * sizeof(JH_index) + ) + ); + } + + k->sequences_sorted[sorted_sequence_id] = sequence_id; +} + +/******************************************************************************/ +/** ALLOCATING MEMORY *********************************************************/ +/******************************************************************************/ +static int reallocate_sequences_list +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index ** new_sequences; + + if ((SIZE_MAX / sizeof(JH_index *)) < (size_t) k->sequences_length) + { + JH_S_ERROR + ( + io, + "Unable to store the size of the sequences list, as it would overflow " + "size_t variables." + ); + + return -1; + } + + new_sequences = + (JH_index **) realloc + ( + (void *) k->sequences, + (((size_t) k->sequences_length) * sizeof(JH_index *)) + ); + + if (new_sequences == (JH_index **) NULL) + { + JH_S_ERROR + ( + io, + "Unable to allocate the memory required for the new sequence list." + ); + + return -1; + } + + k->sequences = new_sequences; + + return 0; +} + +static int reallocate_sequences_sorted_list +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index * new_sequences_sorted; + + if ((SIZE_MAX / sizeof(JH_index)) < (size_t) k->sequences_length) + { + JH_S_ERROR + ( + io, + "Unable to store the size of the sorted sequences list, as it would " + "overflow size_t variables." + ); + + return -1; + } + + new_sequences_sorted = + (JH_index *) realloc + ( + (void *) k->sequences_sorted, + (((size_t) k->sequences_length) * sizeof(JH_index)) + ); + + if (new_sequences_sorted == (JH_index *) NULL) + { + JH_S_ERROR + ( + io, + "Unable to allocate the memory required for the new sorted sequences " + "list." + ); + + return -1; + } + + k->sequences_sorted = new_sequences_sorted; + + return 0; +} + +/* Pre: (=< JH_INDEX_MAX SIZE_MAX) */ +/*@ + requires + ( + (base_length == destination_length) + || + ( + (base_length < destination_length) + && + ( + (base[0] == JH_START_OF_SEQUENCE) + (base[base_length - 1] == JH_END_OF_SEQUENCE) + ) + ) + ); +@*/ +static JH_index * copy_sequence +( + const JH_index base [const restrict static 1], + const JH_index destination_length, + FILE io [const restrict static 1] +) +{ + JH_index * result; + + result = + (JH_index *) calloc + ( + (size_t) (destination_length), + sizeof(JH_index) + ); + + if (result == (JH_index *) NULL) + { + JH_S_ERROR + ( + io, + "Unable to allocate the memory required to store a new sequence." + ); + + return (JH_index *) NULL; + } + + memcpy + ( + (void *) result, + (const void *) base, + (((size_t) destination_length) * sizeof(JH_index)) + ); + + return result; +} + +/******************************************************************************/ +/** ADD A NEW SEQUENCE ********************************************************/ +/******************************************************************************/ + +static int add_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const JH_index markov_order, /* Pre (> markov_order 1) */ + const JH_index sequence_id, + const JH_index sorted_sequence_id, + FILE io [const restrict static 1] +) +{ + JH_index * stored_sequence; + + if (k->sequences_length == JH_INDEX_MAX) + { + JH_S_ERROR + ( + io, + "Unable to add sequence: the variable that stores the number of known " + "sequences would overflow." + ); + + return -1; + } + + stored_sequence = copy_sequence(sequence, (markov_order - 1), io); + + if (stored_sequence == (JH_index *) NULL) + { + return -1; + } + + if (JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE) + { + JH_index i; + + JH_S_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE, + "Learning new sequence." + ); + + for (i = 0; i < (markov_order - 1); ++i) + { + JH_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE, + "markov_sequence[%u]: %u", + i, + stored_sequence[i] + ); + } + } + + k->sequences_length += 1; + + if (reallocate_sequences_list(k, io) < 0) + { + k->sequences_length -= 1; + + free((void *) stored_sequence); + + return -1; + } + + k->sequences[sequence_id] = stored_sequence; + + if (reallocate_sequences_sorted_list(k, io) < 0) + { + k->sequences_length -= 1; + + free((void *) stored_sequence); + + return -1; + } + + set_nth_sequence(k, sorted_sequence_id, sequence_id); + + return 0; +} + +/******************************************************************************/ +/** SEARCH EXISTING SEQUENCES *************************************************/ +/******************************************************************************/ + +int JH_knowledge_find_sequence +( + const struct JH_knowledge k [const static 1], + const JH_index sequence [const restrict static 1], + const JH_index markov_order, /* Pre: (> 1) */ + JH_index sequence_id [const restrict static 1] +) +{ + /* This is a binary search */ + int cmp; + JH_index i, current_min, current_max; + const JH_index markov_sequence_length = (markov_order - 1); + + /* Handles the case where the list is empty ********************************/ + current_max = k->sequences_length; + + if (current_max == 0) + { + *sequence_id = 0; + + return -1; + } + /***************************************************************************/ + + current_min = 0; + current_max -= 1; + + while (current_min <= current_max) + { + i = (current_min + ((current_max - current_min) / 2)); + + cmp = + JH_sequence_cmp + ( + sequence, + k->sequences[k->sequences_sorted[i]], + markov_sequence_length + ); + + if (cmp > 0) + { + current_min = (i + 1); + + if (current_min > current_max) + { + *sequence_id = current_min; + + return -1; + } + } + else if (cmp < 0) + { + if ((current_min >= current_max) || (i == 0)) + { + *sequence_id = current_min; + + return -1; + } + + current_max = (i - 1); + } + else + { + *sequence_id = k->sequences_sorted[i]; + + return 0; + } + } + + *sequence_id = current_min; + + return -1; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ + +int JH_knowledge_learn_markov_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const JH_index markov_order, /* Pre (> markov_order 1) */ + JH_index sequence_id [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index sorted_id; + + if (JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE) + { + JH_index i; + + JH_S_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE, + "Studying markov sequence..." + ); + + for (i = 0; i < (markov_order - 1); ++i) + { + JH_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE, + "markov_sequence[%u]: %u", + i, + sequence[i] + ); + } + } + + if + ( + JH_knowledge_find_sequence + ( + k, + sequence, + markov_order, + sequence_id + ) == 0 + ) + { + JH_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE, + "Markov sequence is known. ID: %u", + *sequence_id + ); + + return 0; + } + + sorted_id = *sequence_id; + *sequence_id = k->sequences_length; + + return + add_sequence + ( + k, + sequence, + markov_order, + *sequence_id, + sorted_id, + io + ); +} diff --git a/src/knowledge/knowledge_learn_sequence.c b/src/knowledge/knowledge_learn_sequence.c new file mode 100644 index 0000000..90dbc88 --- /dev/null +++ b/src/knowledge/knowledge_learn_sequence.c @@ -0,0 +1,264 @@ +#include <stdlib.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../sequence/sequence.h" + +#include "../error/error.h" + +#include "knowledge.h" + +/******************************************************************************/ +/** LEARN FOLLOWING SEQUENCE **************************************************/ +/******************************************************************************/ +static void parse_swt_sequence +( + const JH_index sequence [const restrict static 1], + const size_t index, + JH_index buffer [const restrict static 1], + const JH_index buffer_length +) +{ + size_t j; + size_t index_offset; + + index_offset = buffer_length; + + for (j = 0; j < buffer_length; ++j) + { + if (index >= index_offset) + { + buffer[j] = sequence[index - index_offset]; + } + else + { + buffer[j] = JH_START_OF_SEQUENCE_ID; + } + + --index_offset; + } +} + +static int add_swt_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const size_t index, + const size_t sequence_length, + const JH_index markov_order, + JH_index buffer [const restrict static 1], + const JH_index buffer_length, + FILE io [const restrict static 1] +) +{ + JH_index sequence_id; + + parse_swt_sequence(sequence, index, buffer, buffer_length); + + if + ( + JH_knowledge_learn_markov_sequence + ( + k, + buffer, + (buffer_length + 1), + &sequence_id, + io + ) < 0 + ) + { + return -1; + } + + if (index == (sequence_length - 1)) + { + return + JH_knowledge_strengthen_swt + ( + k, + sequence_id, + sequence[index], + JH_END_OF_SEQUENCE_ID, + io + ); + } + else + { + return + JH_knowledge_strengthen_swt + ( + k, + sequence_id, + sequence[index], + sequence[index + 1], + io + ); + } +} + +/******************************************************************************/ +/** LEARN PRECEDING SEQUENCE **************************************************/ +/******************************************************************************/ +static void parse_tws_sequence +( + const JH_index sequence [const restrict static 1], + const size_t index, + const size_t sequence_length, + JH_index buffer [const restrict static 1], + const JH_index buffer_length +) +{ + size_t j; + size_t index_offset; + + for (j = 0; j < buffer_length; ++j) + { + index_offset = (j + 1) + index; + + if (sequence_length > index_offset) + { + buffer[j] = sequence[index_offset]; + } + else + { + buffer[j] = JH_END_OF_SEQUENCE_ID; + } + } +} + +static int add_tws_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const size_t index, + const size_t sequence_length, + const JH_index markov_order, + JH_index buffer [const restrict static 1], + const JH_index buffer_length, + FILE io [const restrict static 1] +) +{ + JH_index sequence_id; + + parse_tws_sequence(sequence, index, sequence_length, buffer, buffer_length); + + if + ( + JH_knowledge_learn_markov_sequence + ( + k, + buffer, + (buffer_length + 1), + &sequence_id, + io + ) < 0 + ) + { + return -1; + } + + if (index == 0) + { + return + JH_knowledge_strengthen_tws + ( + k, + JH_START_OF_SEQUENCE_ID, + sequence[index], + sequence_id, + io + ); + } + else + { + return + JH_knowledge_strengthen_tws + ( + k, + sequence[index - 1], + sequence[index], + sequence_id, + io + ); + } +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ +int JH_knowledge_learn_sequence +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence [const restrict static 1], + const size_t sequence_length, + const JH_index markov_order, + FILE io [const restrict static 1] +) +{ + JH_index * buffer; + size_t i; + const JH_index buffer_length = (markov_order - 1); + + buffer = + (JH_index *) calloc + ( + (size_t) buffer_length, + sizeof(JH_index) + ); + + if (buffer == (JH_index *) NULL) + { + JH_S_ERROR + ( + io, + "Unable to allocate memory required to create markov sequences." + ); + + return -1; + } + + for (i = 0; i < sequence_length; ++i) + { + if + ( + add_swt_sequence + ( + k, + sequence, + i, + sequence_length, + markov_order, + buffer, + buffer_length, + io + ) < 0 + ) + { + return -1; + } + + /* TODO: handle failure. */ + if + ( + add_tws_sequence + ( + k, + sequence, + i, + sequence_length, + markov_order, + buffer, + buffer_length, + io + ) < 0 + ) + { + return -1; + } + + + k->words[sequence[i]].occurrences += 1; + } + + return 0; +} diff --git a/src/knowledge/knowledge_learn_word.c b/src/knowledge/knowledge_learn_word.c new file mode 100644 index 0000000..1389cdb --- /dev/null +++ b/src/knowledge/knowledge_learn_word.c @@ -0,0 +1,309 @@ +#include <stdlib.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../error/error.h" + +#include "knowledge.h" + +/******************************************************************************/ +/** INITIALIZING STRUCTURES ***************************************************/ +/******************************************************************************/ + +static void initialize_sequence_collection +( + struct JH_knowledge_sequence_collection c [const restrict static 1] +) +{ + c->sequences_ref = (struct JH_knowledge_sequence_data *) NULL; + c->sequences_ref_length = 0; + c->sequences_ref_sorted = (JH_index *) NULL; +} + +static void initialize_word +( + struct JH_knowledge_word w [const restrict static 1] +) +{ + w->word = (const JH_char *) NULL; + w->word_length = 0; + w->occurrences = 0; + + initialize_sequence_collection(&(w->swt)); + initialize_sequence_collection(&(w->tws)); +} + +/******************************************************************************/ +/** ALLOCATING MEMORY *********************************************************/ +/******************************************************************************/ +static JH_char * copy_word +( + const JH_char original [const restrict static 1], + const JH_index original_length, + FILE io [const restrict static 1] +) +{ + JH_char * result; + + result = + (JH_char *) + calloc + ( + original_length, + sizeof(JH_char) + ); + + if (result == (JH_char *) NULL) + { + JH_S_ERROR(io, "Unable to allocate memory to store new word."); + + return (JH_char *) NULL; + } + + memcpy + ( + (void *) result, + (const void *) original, + (((size_t) original_length) * sizeof(JH_char)) + ); + + return result; +} + +static int reallocate_words_list +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + struct JH_knowledge_word * new_words; + + if + ( + (SIZE_MAX / sizeof(struct JH_knowledge_word)) + < (size_t) k->words_length + ) + { + JH_S_ERROR + ( + io, + "Unable to store the size of the words list, as it would overflow " + "size_t variables." + ); + + return -1; + } + + new_words = + (struct JH_knowledge_word *) realloc + ( + (void *) k->words, + (((size_t) k->words_length) * sizeof(struct JH_knowledge_word)) + ); + + if (new_words == (struct JH_knowledge_word *) NULL) + { + JH_S_ERROR + ( + io, + "Unable to allocate the memory required for the new words list." + ); + + return -1; + } + + k->words = new_words; + + return 0; +} + +static int reallocate_words_sorted_list +( + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index * new_words_sorted; + + /* + * This has already been tested previously for a struct JH_knowledge_word, + * whose size is bigger than a JH_index. + * */ + /* + if ((SIZE_MAX / sizeof(JH_index)) < k->words_length) + { + JH_S_ERROR + ( + "Unable to store the size of the sorted words list, as it would " + "overflow size_t variables." + ); + + return -1; + } + */ + + new_words_sorted = + (JH_index *) realloc + ( + (void *) k->words_sorted, + (((size_t) k->words_length) * sizeof(JH_index)) + ); + + if (new_words_sorted == (JH_index *) NULL) + { + JH_S_ERROR + ( + io, + "Unable to allocate the memory required for the new sorted words list." + ); + + return -1; + } + + k->words_sorted = new_words_sorted; + + return 0; +} + +static void set_nth_word +( + struct JH_knowledge k [const restrict static 1], + const JH_index sorted_word_id, + const JH_index word_id +) +{ + /* Safe: (> k->words_length 1) */ + if (sorted_word_id < (k->words_length - 1)) + { + memmove + ( + /* Safe: (=< (+ sorted_word_id 1) k->words_length) */ + (void *) (k->words_sorted + (sorted_word_id + 1)), + (const void *) (k->words_sorted + sorted_word_id), + ( + ((size_t) ((k->words_length - 1) - sorted_word_id)) + * sizeof(JH_index) + ) + ); + } + + k->words_sorted[sorted_word_id] = word_id; +} + +static int add_word +( + struct JH_knowledge k [const restrict static 1], + const JH_char word [const restrict static 1], + const JH_index word_length, + const JH_index word_id, + const JH_index sorted_word_id, + FILE io [const restrict static 1] +) +{ + JH_char * stored_word; + + if (k->words_length == JH_INDEX_MAX) + { + JH_S_ERROR + ( + io, + "Unable to add word: the variable that stores the number of known " + "words would overflow." + ); + + return -1; + } + + stored_word = copy_word(word, word_length, io); + + if (stored_word == (JH_char *) NULL) + { + return -1; + } + + k->words_length += 1; + + if (reallocate_words_list(k, io) < 0) + { + k->words_length -= 1; + + return -1; + } + + initialize_word(k->words + word_id); + + k->words[word_id].word = stored_word; + k->words[word_id].word_length = word_length; + + if (reallocate_words_sorted_list(k, io) < 0) + { + k->words_length -= 1; + + return -1; + } + + set_nth_word(k, sorted_word_id, word_id); + + return 0; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ + +int JH_knowledge_learn_word +( + struct JH_knowledge k [const restrict static 1], + const JH_char word [const restrict static 1], + const size_t word_length, + JH_index word_id [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index sorted_id; + + if (word_length >= (size_t) JH_INDEX_MAX) + { + JH_S_ERROR(io, "Word is too long to be learned."); + + return -1; + } + + if + ( + JH_knowledge_find_word_id + ( + k, + word, + (((size_t) word_length) * sizeof(JH_char)), + word_id + ) == 0 + ) + { + JH_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_WORD, + "Word of size %u is already known (id: %u).", + (JH_index) word_length, + *word_id + ); + + return 0; + } + + sorted_id = *word_id; + *word_id = k->words_length; + + JH_DEBUG + ( + io, + JH_DEBUG_KNOWLEDGE_LEARN_WORD, + "Learning new word of size %u (id: %u, sorted_id: %u).", + (JH_index) word_length, + *word_id, + sorted_id + ); + + return add_word(k, word, (JH_index) word_length, *word_id, sorted_id, io); +} diff --git a/src/knowledge/knowledge_search.c b/src/knowledge/knowledge_search.c new file mode 100644 index 0000000..40feae9 --- /dev/null +++ b/src/knowledge/knowledge_search.c @@ -0,0 +1,213 @@ +#include <stdlib.h> + +#include "../core/char.h" +#include "../core/index.h" +#include "../sequence/sequence.h" + +#include "../error/error.h" + +#include "knowledge.h" + +/* See "knowledge.h". */ +int JH_knowledge_find_word_id +( + const struct JH_knowledge k [const restrict static 1], + const JH_char word [const restrict static 1], + const size_t word_length, + JH_index result [const restrict static 1] +) +{ + /* This is a binary search */ + int cmp; + JH_index i, current_min, current_max; + + /* Handles the case where the list is empty ********************************/ + current_max = k->words_length; + + if (current_max == 0) + { + *result = 0; + + return -1; + } + /***************************************************************************/ + + current_min = 0; + current_max -= 1; + + while (current_min <= current_max) + { + i = (current_min + ((current_max - current_min) / 2)); + + cmp = + JH_word_cmp + ( + word, + word_length, + k->words[k->words_sorted[i]].word, + k->words[k->words_sorted[i]].word_length + ); + + if (cmp > 0) + { + current_min = (i + 1); + + if (current_min > current_max) + { + *result = current_min; + + return -1; + } + } + else if (cmp < 0) + { + if ((current_min >= current_max) || (i == 0)) + { + *result = current_min; + + return -1; + } + + current_max = (i - 1); + } + else + { + *result = k->words_sorted[i]; + + return 0; + } + } + + *result = current_min; + + return -1; +} + +int JH_knowledge_find_markov_sequence +( + const JH_index sequence_id, + const struct JH_knowledge_sequence_collection sc [const restrict static 1], + JH_index result [const restrict static 1] +) +{ + /* This is a binary search */ + int cmp; + JH_index i, current_min, current_max; + + if (sc->sequences_ref_length == 0) + { + *result = 0; + + return -1; + } + + current_min = 0; + current_max = (sc->sequences_ref_length - 1); + + while (current_min <= current_max) + { + i = (current_min + ((current_max - current_min) / 2)); + + cmp = + JH_index_cmp + ( + sequence_id, + sc->sequences_ref[sc->sequences_ref_sorted[i]].id + ); + + if (cmp > 0) + { + current_min = (i + 1); + + if (current_min > current_max) + { + *result = current_min; + + return -1; + } + } + else if (cmp < 0) + { + if ((current_min >= current_max) || (i == 0)) + { + *result = current_min; + + return -1; + } + + current_max = (i - 1); + } + else + { + *result = sc->sequences_ref_sorted[i]; + + return 0; + } + } + + *result = current_min; + + return -1; +} + +int JH_knowledge_find_sequence_target +( + const JH_index target_id, + const struct JH_knowledge_sequence_data sd [const restrict static 1], + JH_index result [const restrict static 1] +) +{ + /* This is a binary search */ + int cmp; + JH_index i, current_min, current_max; + + if (sd->targets_length == 0) + { + *result = 0; + + return -1; + } + + current_min = 0; + current_max = (sd->targets_length - 1); + + while (current_min <= current_max) + { + i = (current_min + ((current_max - current_min) / 2)); + + cmp = JH_index_cmp(target_id, sd->targets[i].id); + + if (cmp > 0) + { + current_min = (i + 1); + + if (current_min > current_max) + { + *result = current_min; + + return -1; + } + } + else if (cmp < 0) + { + if ((current_min >= current_max) || (i == 0)) + { + *result = current_min; + + return -1; + } + + current_max = (i - 1); + } + else + { + *result = i; + + return 0; + } + } + + *result = current_min; + + return -1; +} diff --git a/src/knowledge/knowledge_swt_tws_modifications.c b/src/knowledge/knowledge_swt_tws_modifications.c new file mode 100644 index 0000000..2acd093 --- /dev/null +++ b/src/knowledge/knowledge_swt_tws_modifications.c @@ -0,0 +1,333 @@ +#include <stdlib.h> + +#include "../core/index.h" + +#include "../error/error.h" + +#include "knowledge.h" + +static int add_target +( + struct JH_knowledge_sequence_data sd [const restrict static 1], + const JH_index target_id, + const JH_index s_index, + const JH_index t_index, + FILE io [const restrict static 1] +) +{ + struct JH_knowledge_target * new_p; + + /* (sd->targets_length == JH_INDEX_MAX) => target_id \in sd->targets. */ + + sd->targets_length += 1; + + new_p = + (struct JH_knowledge_target *) realloc + ( + (void *) sd->targets, + (sd->targets_length * sizeof(struct JH_knowledge_target)) + ); + + if (new_p == (struct JH_knowledge_target *) NULL) + { + JH_S_ERROR + ( + io, + "[E] Unable to allocate memory required to store more targets." + ); + + sd->targets_length -= 1; + + return -1; + } + + sd->targets = new_p; + + if (t_index != (sd->targets_length - 1)) + { + memmove + ( + (void *) (sd->targets + t_index + 1), + (const void *) (sd->targets + t_index), + (size_t) + ( + ((sd->targets_length - t_index) - 1) + * sizeof(struct JH_knowledge_target) + ) + ); + } + + sd->targets[t_index].id = target_id; + sd->targets[t_index].occurrences = 0; + + return 0; +} + +static int add_sequence +( + struct JH_knowledge_sequence_collection sc [const restrict static 1], + const JH_index sequence_id, + JH_index s_index [const restrict static 1], + FILE io [const restrict static 1] +) +{ + struct JH_knowledge_sequence_data * new_p; + JH_index * new_ps; + + /* + * (sc->sequences_ref_length == JH_INDEX_MAX) => + * sequence_id \in sc->sequences_ref. + */ + + sc->sequences_ref_length += 1; + + new_p = + (struct JH_knowledge_sequence_data *) realloc + ( + (void *) sc->sequences_ref, + (sc->sequences_ref_length * sizeof(struct JH_knowledge_sequence_data)) + ); + + if (new_p == (struct JH_knowledge_sequence_data *) NULL) + { + JH_S_ERROR + ( + io, + "[E] Unable to allocate memory required to store new preceding or " + " following sequence." + ); + + sc->sequences_ref_length -= 1; + + return -1; + } + + sc->sequences_ref = new_p; + + new_ps = + (JH_index *) realloc + ( + (void *) sc->sequences_ref_sorted, + (sc->sequences_ref_length * sizeof(JH_index)) + ); + + if (new_p == (struct JH_knowledge_sequence_data *) NULL) + { + JH_S_ERROR + ( + io, + "[E] Unable to allocate memory required to store new preceding or " + " following sequence." + ); + + sc->sequences_ref_length -= 1; + + return -1; + } + + sc->sequences_ref_sorted = new_ps; + + if (*s_index != (sc->sequences_ref_length - 1)) + { + memmove + ( + (void *) (sc->sequences_ref_sorted + (*s_index) + 1), + (const void *) (sc->sequences_ref_sorted + (*s_index)), + (size_t) + ( + ((sc->sequences_ref_length - (*s_index)) - 1) + * sizeof(JH_index) + ) + ); + } + + sc->sequences_ref_sorted[*s_index] = (sc->sequences_ref_length - 1); + *s_index = (sc->sequences_ref_length - 1); + + sc->sequences_ref[*s_index].id = sequence_id; + sc->sequences_ref[*s_index].occurrences = 0; + sc->sequences_ref[*s_index].targets = (struct JH_knowledge_target *) NULL; + sc->sequences_ref[*s_index].targets_length = 0; + + return 0; +} + +int JH_knowledge_strengthen_swt +( + struct JH_knowledge k [const restrict static 1], + const JH_index sequence_id, + const JH_index word_id, + const JH_index target_id, + FILE io [const restrict static 1] +) +{ + JH_index s_index, t_index; + + if + ( + JH_knowledge_find_markov_sequence + ( + sequence_id, + &(k->words[word_id].swt), + &s_index + ) < 0 + ) + { + if + ( + add_sequence + ( + &(k->words[word_id].swt), + sequence_id, + &s_index, + io + ) < 0 + ) + { + return -1; + } + } + + if + ( + JH_knowledge_find_sequence_target + ( + target_id, + (k->words[word_id].swt.sequences_ref + s_index), + &t_index + ) < 0 + ) + { + if + ( + add_target + ( + &(k->words[word_id].swt.sequences_ref[s_index]), + target_id, + s_index, + t_index, + io + ) < 0 + ) + { + return -1; + } + } + + if + ( + ( + k->words[word_id].swt.sequences_ref[s_index].occurrences + == JH_INDEX_MAX + ) + || + ( + k->words[word_id].swt.sequences_ref[s_index].targets[t_index].occurrences + == JH_INDEX_MAX + ) + ) + { + JH_S_WARNING + ( + io, + "[W] Unable to strengthen SWT link: link is already at max strength." + ); + + return 1; + } + + k->words[word_id].swt.sequences_ref[s_index].occurrences += 1; + k->words[word_id].swt.sequences_ref[s_index].targets[t_index].occurrences += 1; + + return 0; +} + +int JH_knowledge_strengthen_tws +( + struct JH_knowledge k [const restrict static 1], + const JH_index target_id, + const JH_index word_id, + const JH_index sequence_id, + FILE io [const restrict static 1] +) +{ + JH_index s_index, t_index; + + if + ( + JH_knowledge_find_markov_sequence + ( + sequence_id, + &(k->words[word_id].tws), + &s_index + ) < 0 + ) + { + if + ( + add_sequence + ( + &(k->words[word_id].tws), + sequence_id, + &s_index, + io + ) < 0 + ) + { + return -1; + } + } + + if + ( + JH_knowledge_find_sequence_target + ( + target_id, + (k->words[word_id].tws.sequences_ref + s_index), + &t_index + ) < 0 + ) + { + if + ( + add_target + ( + &(k->words[word_id].tws.sequences_ref[s_index]), + target_id, + s_index, + t_index, + io + ) < 0 + ) + { + return -1; + } + } + + if + ( + ( + k->words[word_id].tws.sequences_ref[s_index].occurrences + == JH_INDEX_MAX + ) + || + ( + k->words[word_id].tws.sequences_ref[s_index].targets[t_index].occurrences + == JH_INDEX_MAX + ) + ) + { + JH_S_ERROR + ( + io, + "[E] Unable to strengthen TWS link: link is already at max strength." + ); + + return -1; + } + + k->words[word_id].tws.sequences_ref[s_index].occurrences += 1; + k->words[word_id].tws.sequences_ref[s_index].targets[t_index].occurrences += 1; + + return 0; +} diff --git a/src/knowledge/knowledge_types.h b/src/knowledge/knowledge_types.h new file mode 100644 index 0000000..82073ff --- /dev/null +++ b/src/knowledge/knowledge_types.h @@ -0,0 +1,62 @@ +#ifndef _JH_KNOWLEDGE_KNOWLEDGE_TYPES_H_ +#define _JH_KNOWLEDGE_KNOWLEDGE_TYPES_H_ + +#ifndef JH_RUNNING_FRAMA_C + #include <pthread.h> +#endif + +#include "../core/index_types.h" +#include "../core/char_types.h" + +struct JH_knowledge_target +{ + JH_index id; + JH_index occurrences; +}; + +struct JH_knowledge_sequence_data +{ + JH_index id; + JH_index occurrences; + struct JH_knowledge_target * targets; + JH_index targets_length; +}; + +struct JH_knowledge_sequence_collection +{ + struct JH_knowledge_sequence_data * sequences_ref; + JH_index sequences_ref_length; + JH_index * sequences_ref_sorted; +}; + +struct JH_knowledge_word +{ + const JH_char * word; + JH_index word_length; + JH_index occurrences; + + /* [Sequence] [Word] [Target] */ + struct JH_knowledge_sequence_collection swt; + + /* [Target] [Word] [Sequence] */ + struct JH_knowledge_sequence_collection tws; +}; + +struct JH_knowledge +{ +#ifndef JH_RUNNING_FRAMA_C + pthread_mutex_t mutex; +#else + int mutex; +#endif + + struct JH_knowledge_word * words; + JH_index words_length; + JH_index * words_sorted; + + JH_index ** sequences; + JH_index sequences_length; + JH_index * sequences_sorted; +}; + +#endif diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..0b097fe --- /dev/null +++ b/src/main.c @@ -0,0 +1,44 @@ +#include <stdio.h> + +#include "parameters/parameters.h" + +#include "server/server.h" + +#include "pervasive.h" + +static void print_help (const char runnable [const restrict static 1]) +{ + printf + ( + "JabberHive - K-order Markov Chain Server\n" + "Software Version %d\n" + "Protocol Version %d\n" + "\nUsages:\n" + " SERVER:\t%s SESSION_NAME MARKOV_ORDER\n" + " CLEAN UP:\t%s -c SESSION_NAME\n" + " SHOW HELP:\tAnything else\n" + "\nParameters:\n" + " SESSION_NAME: Valid UNIX socket.\n" + " MARKOV_ORDER: Positive integer, greater than 1.\n", + JH_SERVER_VERSION, + JH_PROTOCOL_VERSION, + runnable, + runnable + ); +} + +int main (int const argc, const char * argv [const static argc]) +{ + struct JH_parameters params; + + switch (JH_parameters_initialize(¶ms, argc, argv)) + { + case JH_RUNS: + return JH_server_main(¶ms); + + default: + case JH_PRINTS_HELP: + print_help(argv[0]); + return 0; + } +} diff --git a/src/parameters/CMakeLists.txt b/src/parameters/CMakeLists.txt new file mode 100644 index 0000000..94e6337 --- /dev/null +++ b/src/parameters/CMakeLists.txt @@ -0,0 +1,6 @@ +set( + SRC_FILES ${SRC_FILES} + ${CMAKE_CURRENT_SOURCE_DIR}/parameters.c +) +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) + diff --git a/src/parameters/parameters.c b/src/parameters/parameters.c new file mode 100644 index 0000000..24cbd68 --- /dev/null +++ b/src/parameters/parameters.c @@ -0,0 +1,100 @@ +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> + +#include "../core/index.h" + +#include "../error/error.h" + +#include "parameters.h" + +static int parse_markov_order +( + struct JH_parameters param [const restrict static 1], + const char argv [const restrict] +) +{ + long long int input; + const int old_errno = errno; + + errno = 0; + + input = strtoll(argv, (char **) NULL, 10); + + if + ( + (errno != 0) + || (input > (long long int) JH_INDEX_MAX) + || (input < 1) + ) + { + JH_FATAL + ( + stderr, + "Invalid or value for parameter 'MARKOV_ORDER', accepted " + "range is " + "[2, %lli] (integer).", + (long long int) JH_INDEX_MAX + ); + + errno = old_errno; + + return -1; + } + + param->markov_order = (JH_index) input; + + errno = old_errno; + + return 0; +} + +enum JH_invocation_objective JH_parameters_initialize +( + struct JH_parameters param [const restrict static 1], + int const argc, + const char * argv [const static argc] +) +{ + param->session = (const char *) NULL; + param->markov_order = 2; + + switch (argc) + { + case 3: + param->session = argv[1]; + + if (parse_markov_order(param, argv[2]) < 0) + { + return JH_PRINTS_HELP; + } + else + { + return JH_RUNS; + } + + case 2: + param->session = argv[1]; + + return JH_CLEANS_UP; + + default: + return JH_PRINTS_HELP; + } +} + +const char * JH_parameters_get_session_name +( + const struct JH_parameters param [const restrict static 1] +) +{ + return param->session; +} + +JH_index JH_parameters_get_markov_order +( + const struct JH_parameters param [const restrict static 1] +) +{ + return param->markov_order; +} diff --git a/src/parameters/parameters.h b/src/parameters/parameters.h new file mode 100644 index 0000000..1cb9fd8 --- /dev/null +++ b/src/parameters/parameters.h @@ -0,0 +1,23 @@ +#ifndef _JH_CLI_PARAMETERS_H_ +#define _JH_CLI_PARAMETERS_H_ + +#include "parameters_types.h" + +const char * JH_parameters_get_session_name +( + const struct JH_parameters param [const restrict static 1] +); + +JH_index JH_parameters_get_markov_order +( + const struct JH_parameters param [const restrict static 1] +); + +enum JH_invocation_objective JH_parameters_initialize +( + struct JH_parameters param [const restrict static 1], + int const argc, + const char * argv [const static argc] +); + +#endif diff --git a/src/parameters/parameters_types.h b/src/parameters/parameters_types.h new file mode 100644 index 0000000..7b2059b --- /dev/null +++ b/src/parameters/parameters_types.h @@ -0,0 +1,19 @@ +#ifndef _JH_CLI_PARAMETERS_TYPES_H_ +#define _JH_CLI_PARAMETERS_TYPES_H_ + +#include "../core/index_types.h" + +enum JH_invocation_objective +{ + JH_PRINTS_HELP, + JH_CLEANS_UP, + JH_RUNS +}; + +struct JH_parameters +{ + const char * restrict session; + JH_index markov_order; +}; + +#endif diff --git a/src/pervasive.h b/src/pervasive.h new file mode 100644 index 0000000..cc63eea --- /dev/null +++ b/src/pervasive.h @@ -0,0 +1,46 @@ +#ifndef _JH_PERVASIVE_H_ +#define _JH_PERVASIVE_H_ + +#include <string.h> + +#define JH_SERVER_VERSION 1 +#define JH_PROTOCOL_VERSION 1 + +#ifdef __FRAMAC__ + #define JH_RUNNING_FRAMA_C 1 +#endif + +#define JH_DEBUG_ALL 0 + +#ifndef JH_DEBUG_ALL + #define JH_DEBUG_ALL 0 +#endif + +#define JH_DEBUG_KNOWLEDGE (0 | JH_DEBUG_ALL) +#define JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE \ + (JH_DEBUG_KNOWLEDGE & (0 | JH_DEBUG_ALL)) +#define JH_DEBUG_KNOWLEDGE_LEARN_WORD \ + (JH_DEBUG_KNOWLEDGE & (0 | JH_DEBUG_ALL)) + +#define JH_DEBUG_SEQUENCE (0 | JH_DEBUG_ALL) +#define JH_DEBUG_SEQUENCE_FROM_STRING \ + (JH_DEBUG_SEQUENCE & (0 | JH_DEBUG_ALL)) + +#define JH_DEBUG_SEQUENCE_CREATION \ + (JH_DEBUG_SEQUENCE & (0 | JH_DEBUG_ALL)) + +#define JH_DEBUG_SEQUENCE_CREATION_INIT \ + (JH_DEBUG_SEQUENCE_CREATION & (0 | JH_DEBUG_ALL)) + +#define JH_DEBUG_CORE (0 | JH_DEBUG_ALL) + +#define JH__TO_STRING(x) #x +#define JH_TO_STRING(x) JH__TO_STRING(x) +#define JH_ISOLATE(a) do {a} while (0) + +/* strncmp stops at '\0' and strlen does not count '\0'. */ +#define JH_IS_PREFIX(a, b) (strncmp(a, b, strlen(a)) == 0) + +#define JH_STRING_EQUALS(a, b) (strcmp(a, b) == 0) + +#endif diff --git a/src/sequence/CMakeLists.txt b/src/sequence/CMakeLists.txt new file mode 100644 index 0000000..1186557 --- /dev/null +++ b/src/sequence/CMakeLists.txt @@ -0,0 +1,11 @@ +set( + SRC_FILES ${SRC_FILES} + ${CMAKE_CURRENT_SOURCE_DIR}/sequence.c + ${CMAKE_CURRENT_SOURCE_DIR}/sequence_append.c + ${CMAKE_CURRENT_SOURCE_DIR}/sequence_creation.c + ${CMAKE_CURRENT_SOURCE_DIR}/sequence_from_string.c + ${CMAKE_CURRENT_SOURCE_DIR}/sequence_to_string.c +) + +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) + diff --git a/src/sequence/sequence.c b/src/sequence/sequence.c new file mode 100644 index 0000000..c9c30f1 --- /dev/null +++ b/src/sequence/sequence.c @@ -0,0 +1,50 @@ +#include <stdlib.h> +#include <string.h> + +#include "../core/index.h" + +#include "sequence.h" + +/* See "sequence.h" */ +/*@ + requires + ( + \valid(sequence_a+ (0 .. sequence_a_length)) + || (sequence_a_length == 0) + ); + + requires + ( + \valid(sequence_b+ (0 .. sequence_b_length)) + || (sequence_b_length == 0) + ); + + assigns \result; +@*/ +int JH_sequence_cmp +( + const JH_index sequence_a [const restrict static 1], + const JH_index sequence_b [const restrict static 1], + const JH_index length +) +{ + JH_index i, a, b; + + for (i = 0; i < length; ++i) + { + a = sequence_a[i]; + b = sequence_b[i]; + + if (a < b) + { + return -1; + } + else if (a > b) + { + return 1; + } + } + + return 0; +} + diff --git a/src/sequence/sequence.h b/src/sequence/sequence.h new file mode 100644 index 0000000..dc67159 --- /dev/null +++ b/src/sequence/sequence.h @@ -0,0 +1,331 @@ +#ifndef _JH_CORE_SEQUENCE_H_ +#define _JH_CORE_SEQUENCE_H_ + +/* Defines SIZE_MAX */ +#include <stdint.h> + +#include "../core/char_types.h" +#include "../core/index_types.h" + +#include "../error/error.h" + +#include "../knowledge/knowledge_types.h" + +#include "sequence_types.h" + +/*@ + requires \valid(sequence); + requires (\block_length(sequence) >= 1); + requires \valid(sequence_capacity); + requires (\block_length(sequence) >= 1); + requires \valid(io); + + requires (((*sequence_capacity) * sizeof(JH_index)) <= SIZE_MAX); + requires ((sequence_required_capacity * sizeof(JH_index)) <= SIZE_MAX); + + requires + \separated + ( + (sequence+ (0 .. \block_length(sequence))), + ((*sequence)+ (0 .. \block_length(*sequence))), + (sequence_capacity+ (0 ..\block_length(sequence_capacity))), + (io+ (0 ..\block_length(io))) + ); + + ensures + \separated + ( + (sequence+ (0 .. \block_length(sequence))), + ((*sequence)+ (0 .. \block_length(*sequence))), + (sequence_capacity+ (0 ..\block_length(sequence_capacity))), + (io+ (0 ..\block_length(io))) + ); + + ensures (((*sequence_capacity) * sizeof(JH_index)) <= SIZE_MAX); + ensures ((sequence_required_capacity * sizeof(JH_index)) <= SIZE_MAX); + ensures \valid(sequence); + ensures \valid(*sequence); + ensures \valid(sequence_capacity); + ensures \valid(io); + + assigns (*sequence); + assigns (*sequence_capacity); + + ensures ((\result == 1) || (\result == 0) || (\result == -1)); + + ensures + ( + (\result == 1) ==> + ((*sequence_capacity) == sequence_required_capacity) + ); + + ensures + ( + (\result == 1) ==> + ((*sequence_capacity) > \old(*sequence_capacity)) + ); + + ensures ((\result == -1) ==> ((*sequence) == \old(*sequence))); + + ensures + ( + (\result == -1) ==> + ((*sequence_capacity) == \old(*sequence_capacity)) + ); + + ensures ((\result == 0) ==> ((*sequence) == \old(*sequence))); + + ensures + ( + (\result == 0) ==> + ((*sequence_capacity) == \old(*sequence_capacity)) + ); +@*/ +int JH_sequence_ensure_capacity +( + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + const size_t sequence_required_capacity, + FILE io [const restrict static 1] +); + +int JH_sequence_from_undercase_string +( + const JH_char string [const restrict], + const size_t string_length, + struct JH_knowledge k [const restrict static 1], + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +); + +/* + * Creates a sequence containing {initial_word}. The remaining elements of + * sequence are added according to what is known to {k} as being possible. + * The resulting sequence starts by JH_START_OF_SEQUENCE_ID, and ends by + * JH_END_OF_SEQUENCE_ID. The sequence is allocated by the function. If an + * error occur, it is unallocated and set to NULL ({sequence_size} is set + * accordingly). + * Return: + * 0 on success. + * -1 iff the allocating failed. + * -2 iff the sequence initialization failed. + * -3 iff an error occured when trying to add elements to the right of the + * sequence. + * -4 iff an error occured when trying to add elements to the left of the + * sequence. + * -5 iff the resulting sequence would have been empty. + * Pre: + * (> {markov_order} 1) + * (knows {k} {initial_word}) + * (initialized {k}) + */ +int JH_sequence_create_from +( + const JH_index initial_word, + size_t credits [const restrict], + struct JH_knowledge k [const restrict static 1], + const JH_index markov_order, + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +); + +/*@ + requires \valid(sequence); + requires \valid(*sequence); + requires \valid(sequence_capacity); + requires \valid(sequence_length); + requires \valid(io); + requires (((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); + requires (((*sequence_capacity) * sizeof(JH_index)) <= SIZE_MAX); + requires + \separated + ( + (sequence+ (0 .. \block_length(sequence))), + ((*sequence)+ (0 .. \block_length(*sequence))), + (sequence_capacity+ (0 ..\block_length(sequence_capacity))), + (sequence_length+ (0 ..\block_length(sequence_length))), + (io+ (0 ..\block_length(io))) + ); + + assigns (*sequence_length); + assigns (*sequence[0]); + assigns (*sequence_capacity); + + ensures \valid(sequence); + ensures \valid(*sequence); + ensures \valid(sequence_capacity); + ensures \valid(sequence_length); + ensures \valid(io); + ensures (((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); + ensures (((*sequence_capacity) * sizeof(JH_index)) <= SIZE_MAX); + ensures + \separated + ( + (sequence+ (0 .. \block_length(sequence))), + ((*sequence)+ (0 .. \block_length(*sequence))), + (sequence_capacity+ (0 ..\block_length(sequence_capacity))), + (sequence_length+ (0 ..\block_length(sequence_length))), + (io+ (0 ..\block_length(io))) + ); + + ensures ((\result == 0) || (\result == -1)); + + ensures + ( + (\result == 0) ==> + (*sequence_length == (\old(*sequence_length) + 1)) + ); + + ensures + ( + (\result == 0) ==> + ((*sequence_capacity) >= \old(*sequence_capacity)) + ); + + ensures ((\result == 0) ==> (*sequence_length > \old(*sequence_length))); + + ensures ((\result == -1) ==> ((*sequence_length) == \old(*sequence_length))); + ensures ((\result == -1) ==> (((*sequence)[0]) == \old((*sequence)[0]))); + ensures + ( + (\result == -1) ==> + ((*sequence_capacity) == \old(*sequence_capacity)) + ); + + ensures ((\result == -1) ==> ((*sequence_length) == \old(*sequence_length))); + ensures + ( + (\result == -1) ==> + ((*sequence_capacity) == \old(*sequence_capacity)) + ); + +@*/ +int JH_sequence_append_left +( + const JH_index word_id, + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +); + +/*@ + requires \valid(sequence); + requires \valid(*sequence); + requires \valid(sequence_capacity); + requires \valid(sequence_length); + requires \valid(io); + requires (((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); + requires (((*sequence_capacity) * sizeof(JH_index)) <= SIZE_MAX); + requires + \separated + ( + (sequence+ (0 .. \block_length(sequence))), + ((*sequence)+ (0 .. \block_length(*sequence))), + (sequence_capacity+ (0 ..\block_length(sequence_capacity))), + (sequence_length+ (0 ..\block_length(sequence_length))), + (io+ (0 ..\block_length(io))) + ); + + assigns (*sequence_length); + assigns ((*sequence)[0]); + assigns (*sequence_capacity); + + ensures \valid(sequence); + ensures \valid(*sequence); + ensures \valid(sequence_capacity); + ensures \valid(sequence_length); + ensures \valid(io); + ensures (((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); + ensures (((*sequence_capacity) * sizeof(JH_index)) <= SIZE_MAX); + ensures + \separated + ( + (sequence+ (0 .. \block_length(sequence))), + ((*sequence)+ (0 .. \block_length(*sequence))), + (sequence_capacity+ (0 ..\block_length(sequence_capacity))), + (sequence_length+ (0 ..\block_length(sequence_length))), + (io+ (0 ..\block_length(io))) + ); + + ensures ((\result == 0) || (\result == -1)); + + ensures + ( + (\result == 0) ==> + (*sequence_length == (\old(*sequence_length) + 1)) + ); + + ensures + ( + (\result == 0) ==> + ((*sequence_capacity) >= \old(*sequence_capacity)) + ); + + ensures ((\result == 0) ==> (*sequence_length > \old(*sequence_length))); + + ensures ((\result == -1) ==> ((*sequence_length) == \old(*sequence_length))); + ensures ((\result == -1) ==> (((*sequence)[0]) == \old((*sequence)[0]))); + ensures + ( + (\result == -1) ==> + ((*sequence_capacity) == \old(*sequence_capacity)) + ); + + ensures ((\result == -1) ==> ((*sequence_length) == \old(*sequence_length))); + ensures + ( + (\result == -1) ==> + ((*sequence_capacity) == \old(*sequence_capacity)) + ); + +@*/ +int JH_sequence_append_right +( + JH_index * sequence [const restrict static 1], + const JH_index word_id, + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +); + +/* + * Compares two sequences. + * JH_END_OF_SEQUENCE marks the ending of a sequence, regardless of indicated + * sequence length, meaning that [10][JH_END_OF_SEQUENCE][9] and + * [10][JH_END_OF_SEQUENCE][8] are considered equal. Sequences do not have to + * contain JH_END_OF_SEQUENCE. [10][JH_END_OF_SEQUENCE] and [10] are + * considered different, [10][JH_END_OF_SEQUENCE] + * and [10][JH_END_OF_SEQUENCE][JH_END_OF_SEQUENCE] are considered equal. + * Same logic is applyied for JH_START_OF_SEQUENCE: + * [START_OF_SEQUENCE][10] is not [10], but + * [START_OF_SEQUENCE][START_OF_SEQUENCE][10] and [START_OF_SEQUENCE][10] are + * the same. + * Return: + * 1 iff {sequence_a} should be considered being more than {sequence_b} + * 0 iff {sequence_a} should be considered being equal to {sequence_b} + * -1 iff {sequence_a} should be considered being less than {sequence_b} + */ +int JH_sequence_cmp +( + const JH_index sequence_a [const], + const JH_index sequence_b [const], + const JH_index length +); + +int JH_sequence_to_undercase_string +( + const JH_index sequence [const restrict static 1], + const size_t sequence_length, + struct JH_knowledge k [const restrict static 1], + JH_char * destination [const restrict static 1], + size_t destination_capacity [const restrict static 1], + size_t destination_length [const restrict static 1], + FILE io [const restrict static 1] +); + +#endif diff --git a/src/sequence/sequence_append.c b/src/sequence/sequence_append.c new file mode 100644 index 0000000..7206c19 --- /dev/null +++ b/src/sequence/sequence_append.c @@ -0,0 +1,241 @@ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../core/index.h" + +#include "../error/error.h" + +#include "sequence.h" + +/******************************************************************************/ +/** MEMORY (RE)ALLOCATION *****************************************************/ +/******************************************************************************/ + +/*@ + requires \valid(required_capacity); + requires \valid(io); + requires + \separated + ( + (required_capacity+ (0 .. \block_length(required_capacity))), + (io+ (0 .. \block_length(io))) + ); + + assigns \result; + assigns (*required_capacity); + + ensures ((\result == 0) || (\result == -1)); + + ensures \valid(required_capacity); + ensures \valid(io); + + ensures + \separated + ( + (required_capacity+ (0 .. \block_length(required_capacity))), + (io+ (0 .. \block_length(io))) + ); + + ensures + ( + (\result == 0) <==> + ((*required_capacity) == (\old(*required_capacity) + 1)) + ); + + ensures + ( + (\result == 0) ==> + ((*required_capacity) * sizeof(JH_index)) <= SIZE_MAX + ); + + ensures + ( + (\result == -1) <==> + ((*required_capacity) == \old(*required_capacity)) + ); + +@*/ +static int increment_required_capacity +( + size_t required_capacity [const restrict static 1], + FILE io [const restrict static 1] +) +{ + if + ( + (*required_capacity == SIZE_MAX) + || ((SIZE_MAX / sizeof(JH_index)) <= (*required_capacity + 1)) + ) + { + /*@ assert \valid(io); @*/ + + #ifndef JH_RUNNING_FRAMA_C + JH_S_ERROR + ( + io, + "Sequence capacity increment aborted, as the new size would not fit " + "in a size_t variable." + ); + #endif + + return -1; + } + + /*@ assert ((*required_capacity) < SIZE_MAX); @*/ + /*@ assert \valid(required_capacity); @*/ + *required_capacity = (*required_capacity + 1); + + /* assert (((*required_capacity) * sizeof(JH_index)) <= SIZE_MAX); @*/ + + return 0; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ + +int JH_sequence_ensure_capacity +( + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + const size_t sequence_required_capacity, + FILE io [const restrict static 1] +) +{ + JH_index * new_sequence; + + /*@ assert \valid(sequence_capacity); @*/ + if (sequence_required_capacity <= *sequence_capacity) + { + return 0; + } + + /*@ + assert + ( + sequence_required_capacity + <= (SIZE_MAX / sizeof(JH_index)) + ); + @*/ + /*@ assert \valid(sequence); @*/ + /*@ assert \valid(*sequence); @*/ + new_sequence = + (JH_index *) realloc + ( + (void *) *sequence, + (sequence_required_capacity * sizeof(JH_index)) + ); + + if (new_sequence == (JH_index *) NULL) + { + /*@ assert \valid(io); @*/ + + #ifndef JH_RUNNING_FRAMA_C + JH_S_ERROR + ( + io, + "Unable to reallocate memory to match sequence's required size." + ); + #endif + + return -1; + } + + *sequence_capacity = sequence_required_capacity; + *sequence = new_sequence; + + return 1; +} + +int JH_sequence_append_left +( + const JH_index word_id, + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +) +{ + if (increment_required_capacity(sequence_length, io) < 0) + { + return -1; + } + + /*@ assert (((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); @*/ + if + ( + JH_sequence_ensure_capacity + ( + sequence, + sequence_capacity, + *sequence_length, + io + ) < 0 + ) + { + *sequence_length -= 1; + + return -1; + } + + /*@ assert (*sequence_length) >= 0; @*/ + + if ((*sequence_length) > 1) + { + /*@ assert(((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); @*/ + + #ifndef JH_RUNNING_FRAMA_C + memmove + ( + (void *) ((*sequence) + 1), + (const void *) (*sequence), + (((*sequence_length) - 1) * sizeof(JH_index)) + ); + #endif + } + + (*sequence)[0] = word_id; + + return 0; +} + +int JH_sequence_append_right +( + JH_index * sequence [const restrict static 1], + const JH_index word_id, + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +) +{ + if (increment_required_capacity(sequence_length, io) < 0) + { + return -1; + } + + /*@ assert (((*sequence_length) * sizeof(JH_index)) <= SIZE_MAX); @*/ + + if + ( + JH_sequence_ensure_capacity + ( + sequence, + sequence_capacity, + *sequence_length, + io + ) < 0 + ) + { + *sequence_length -= 1; + + return -1; + } + + /*@ assert ((*sequence_length) >= 1); @*/ + (*sequence)[(*sequence_length) - 1] = word_id; + /*@ assert ((*sequence_length) >= 1); @*/ + + return 0; +} diff --git a/src/sequence/sequence_creation.c b/src/sequence/sequence_creation.c new file mode 100644 index 0000000..0b5e393 --- /dev/null +++ b/src/sequence/sequence_creation.c @@ -0,0 +1,605 @@ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../core/index.h" + +#include "../error/error.h" + +#include "../knowledge/knowledge.h" + +#include "sequence.h" + + +/******************************************************************************/ +/** ADDING ELEMENTS TO THE LEFT ***********************************************/ +/******************************************************************************/ + +/* + * Adds an id to the left of the sequence, according to what is known as likely + * to fit there. + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {*sequence} remains untouched. + * Semaphore: + * Takes then releases access for {k}. + * Returns: + * 0 on success. + * -1 iff nothing fitting was found. + * -2 iff the addition of that id failed. + * Pre: + * (initialized {sequence}) + * (initialized {k}) + * (> {markov_order} 1) + * (initialized {*sequence[0..({markov_order} - 1)]}) + */ +static int extend_left +( + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + const JH_index markov_order, + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index sequence_id, word_id; + + (void) JH_knowledge_lock_access(k, io); + + /* preceding_words_weights_sum > 0 */ + + if + ( + JH_knowledge_find_sequence + ( + k, + ((*sequence) + 1), + markov_order, + &sequence_id + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + JH_S_ERROR(io, "Could not find matching TWS sequence."); + + return -1; + } + + (void) JH_knowledge_unlock_access(k, io); + + (void) JH_knowledge_lock_access(k, io); + + if + ( + JH_knowledge_random_tws_target + ( + k, + &word_id, + (*sequence)[0], + sequence_id + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + JH_S_ERROR(io, "Could not find matching TWS target."); + + return -1; + } + + (void) JH_knowledge_unlock_access(k, io); + + if + ( + JH_sequence_append_left + ( + word_id, + sequence, + sequence_capacity, + sequence_length, + io + ) < 0 + ) + { + return -3; + } + + return 0; +} + +/* + * Continuously adds ids to the left of the sequence, according to what is known + * as likely to fit there. If {credits} is NULL, it will stop upon reaching + * the id indicating the start of a sequence, otherwise it will also limit to + * {*credits} words added (including the one indicating the start of a + * sequence). + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {sequence} remains unfreed. + * Returns: + * 0 on success. + * -1 iff we did not manage to have JH_START_OF_SEQUENCE_ID as a starting + * point. This cannot be caused by lack of {*credits}, but rather by a + * memory allocation problem or a more important issue in {k}. Indeed, it + * could mean we do not know any word preceding {*sequence[0]}, not even + * JH_START_OF_SEQUENCE_ID. + * Pre: + * (initialized {sequence}) + * (initialized {sequence_size}) + * (initialized {k}) + * (> {markov_order} 1) + * (initialized {*sequence[0..(MARKOV_ORDER - 1)]}) + */ +static int complete_left_part_of_sequence +( + JH_index * sequence [restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + const JH_index markov_order, + size_t credits [const restrict], + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + for (;;) + { + if ((credits == (size_t *) NULL) || (*credits > 0)) + { + if + ( + extend_left + ( + sequence, + sequence_capacity, + sequence_length, + markov_order, + k, + io + ) < 0 + ) + { + /* We are sure *sequence[0] is defined. */ + if ((*sequence)[0] == JH_START_OF_SEQUENCE_ID) + { + /* + * We failed to add a word, but it was because none should have + * been added. + */ + return 0; + } + else + { + return -1; + } + } + } + else + { + /* No more credits available, the sequence will have to start here. */ + (*sequence)[0] = JH_START_OF_SEQUENCE_ID; + + return 0; + } + + if (credits != (size_t *) NULL) + { + *credits -= 1; + } + + /* We are sure *sequence[0] is defined. */ + switch ((*sequence)[0]) + { + case JH_END_OF_SEQUENCE_ID: + JH_S_WARNING + ( + io, + "END OF LINE was added at the left part of an sequence." + ); + + (*sequence)[0] = JH_START_OF_SEQUENCE_ID; + return 0; + + case JH_START_OF_SEQUENCE_ID: + return 0; + + default: + break; + } + } +} + +/******************************************************************************/ +/** ADDING ELEMENTS TO THE RIGHT **********************************************/ +/******************************************************************************/ + + +/* + * Adds an id to the right of the sequence, according to what is known as likely + * to fit there. + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {*sequence} remains untouched. + * Semaphore: + * Takes then releases access for {k}. + * Returns: + * 0 on success. + * -1 iff nothing fitting was found. + * -2 iff the addition of that id failed. + * Pre: + * (initialized {sequence}) + * (initialized {k}) + * (> {markov_order} 1) + * (initialized {*sequence[0..(MARKOV_ORDER - 1)]}) + */ +static int extend_right +( + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + const JH_index markov_order, + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index sequence_id, word_id; + + (void) JH_knowledge_lock_access(k, io); + + /* preceding_words_weights_sum > 0 */ + + if + ( + JH_knowledge_find_sequence + ( + k, + ((*sequence) + (*sequence_length - markov_order)), + markov_order, + &sequence_id + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + JH_S_PROG_ERROR + ( + io, + "Knowledge consistency error: generated markov sequence could not be " + "found." + ); + + return -1; + } + + (void) JH_knowledge_unlock_access(k, io); + + (void) JH_knowledge_lock_access(k, io); + + if + ( + JH_knowledge_random_swt_target + ( + k, + sequence_id, + (*sequence)[*sequence_length - 1], + &word_id + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + JH_S_PROG_ERROR + ( + io, + "Knowledge consistency error: generated markov sequence had no known " + "targets." + ); + + return -1; + } + + (void) JH_knowledge_unlock_access(k, io); + + + /* following_words_weights_sum > 0 */ + + if + ( + JH_sequence_append_right + ( + sequence, + word_id, + sequence_capacity, + sequence_length, + io + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + return -3; + } + + (void) JH_knowledge_unlock_access(k, io); + + return 0; +} + +/* + * Continuously adds ids to the right of the sequence, according to what is + * known as likely to fit there. If {credits} is NULL, it will stop upon + * reaching the id indicating the end of a sequence, otherwise it will also + * limit to {*credits} words added (including the one indicating the end of a + * sequence). + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {sequence} remain untouched. + * Returns: + * 0 on success. + * -1 iff we did not manage to have JH_END_OF_SEQUENCE_ID as a stopping + * point. This cannot be caused by lack of {*credits}, but rather by a + * memory allocation problem or a more important issue in {k}. Indeed, it + * could mean we do not know any word following {*sequence[0]}, not even + * JH_END_OF_SEQUENCE_ID. + * Pre: + * (initialized {sequence}) + * (initialized {*sequence_size}) + * (initialized {k}) + * (> {markov_order} 1) + * (initialized {*sequence[0..(MARKOV_ORDER - 1)]}) + */ +static int complete_right_part_of_sequence +( + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + const JH_index markov_order, + size_t credits [const restrict], + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + for (;;) + { + if ((credits == (size_t *) NULL) || (*credits > 0)) + { + if + ( + extend_right + ( + sequence, + sequence_capacity, + sequence_length, + markov_order, + k, + io + ) < 0 + ) + { + /* Safe: (> sequence_length 1) */ + if ((*sequence)[(*sequence_length - 1)] == JH_END_OF_SEQUENCE_ID) + { + /* + * We failed to add a word, but it was because none should have + * been added. + */ + return 0; + } + else + { + return -1; + } + } + } + else + { + /* No more credits available, we end the sequence. */ + (*sequence)[((*sequence_length) - 1)] = JH_END_OF_SEQUENCE_ID; + + return 0; + } + + if (credits != (size_t *) NULL) + { + *credits -= 1; + } + + /* Safe: (> sequence_length 1) */ + switch ((*sequence)[((*sequence_length) - 1)]) + { + case JH_START_OF_SEQUENCE_ID: + JH_S_WARNING + ( + io, + "END OF LINE was added at the right part of an sequence." + ); + + (*sequence)[((*sequence_length) - 1)] = JH_END_OF_SEQUENCE_ID; + return 0; + + case JH_END_OF_SEQUENCE_ID: + return 0; + + default: + break; + } + } +} + +/******************************************************************************/ +/** INITIALIZING SEQUENCE *****************************************************/ +/******************************************************************************/ + +/* + * Initializes an pre-allocated sequence by filling it with {initial_word} + * followed by a sequence of ({markov_order} - 1) words that is known to have + * followed {initial_word} at least once. This sequence is chosen depending on + * how often {k} indicates it has followed {initial_word}. + * Returns: + * 0 on success. + * -1 if no such sequence was found. + * Pre: + * (size (= {sequence} {markov_order})) + * (initialized {k}) + * (> markov_order 1) + * Post: + * (initialized {sequence[0..(markov_order - 1)]}) + */ +static int initialize_sequence +( + JH_index sequence [const restrict static 1], + const JH_index initial_word, + const JH_index markov_order, + struct JH_knowledge k [const static 1], + FILE io [const restrict static 1] +) +{ + sequence[(markov_order - 1)] = initial_word; + + (void) JH_knowledge_lock_access(k, io); + + if + ( + JH_knowledge_copy_random_swt_sequence + ( + k, + sequence, + initial_word, + markov_order, + io + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + return -1; + } + + (void) JH_knowledge_unlock_access(k, io); + + if (JH_DEBUG_SEQUENCE_CREATION_INIT) + { + JH_index i; + + for (i = 0; i < markov_order; ++i) + { + JH_DEBUG + ( + io, + JH_DEBUG_SEQUENCE_CREATION_INIT, + "sequence[%u]: %u", + i, + sequence[i] + ); + } + } + + return 0; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ + +/* See "sequence.h" */ +int JH_sequence_create_from +( + const JH_index initial_word, + size_t credits [const restrict], + struct JH_knowledge k [const restrict static 1], + const JH_index markov_order, + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +) +{ + if + ( + JH_sequence_ensure_capacity + ( + sequence, + sequence_capacity, + markov_order, + io + ) < 0 + ) + { + *sequence_length = 0; + + return -1; + } + + if + ( + initialize_sequence + ( + *sequence, + initial_word, + markov_order, + k, + io + ) < 0 + ) + { + JH_S_ERROR(io, "Failed to create start of new sequence."); + + *sequence_length = 0; + + return -2; + } + + *sequence_length = markov_order; + + if + ( + complete_right_part_of_sequence + ( + sequence, + sequence_capacity, + sequence_length, + markov_order, + credits, + k, + io + ) < 0 + ) + { + JH_S_ERROR(io, "Failed to create right part of sequence."); + + *sequence_length = 0; + + return -3; + } + + if + ( + complete_left_part_of_sequence + ( + sequence, + sequence_capacity, + sequence_length, + markov_order, + credits, + k, + io + ) < 0 + ) + { + JH_S_ERROR(io, "Failed to create left part of sequence."); + + *sequence_length = 0; + + return -4; + } + + if (*sequence_length < 3) + { + /* 2 elements, for start and stop. */ + JH_S_ERROR(io, "Created sequence was empty."); + + *sequence_length = 0; + + return -5; + } + + return 0; +} diff --git a/src/sequence/sequence_from_string.c b/src/sequence/sequence_from_string.c new file mode 100644 index 0000000..5b92943 --- /dev/null +++ b/src/sequence/sequence_from_string.c @@ -0,0 +1,219 @@ +#define _POSIX_C_SOURCE 200809L +#include <stdlib.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../core/char.h" +#include "../core/index.h" + +#include "../error/error.h" + +#include "../knowledge/knowledge.h" + +#include "sequence.h" + +/******************************************************************************/ +/** HANDLING WORDS ************************************************************/ +/******************************************************************************/ + +static int add_word_to_sequence +( + const JH_char string [const restrict static 1], + const size_t word_start, + const size_t word_length, + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + struct JH_knowledge k [const restrict static 1], + FILE io [const restrict static 1] +) +{ + JH_index word_id; + + (void) JH_knowledge_lock_access(k, io); + + if + ( + JH_knowledge_learn_word + ( + k, + (string + word_start), + word_length, + &word_id, + io + ) < 0 + ) + { + (void) JH_knowledge_unlock_access(k, io); + + return -1; + } + + (void) JH_knowledge_unlock_access(k, io); + + if + ( + JH_sequence_append_right + ( + sequence, + word_id, + sequence_capacity, + sequence_length, + io + ) < 0 + ) + { + return -1; + } + + return 0; +} + +static int find_word +( + const JH_char string [const restrict static 1], + const size_t string_length, + const size_t offset, + size_t word_start [const restrict static 1], + size_t word_length [const restrict static 1] +) +{ + size_t i; + + i = offset; + + while ((string[i] == ' ') && (i < string_length)) + { + i += 1; + } + + if (i >= string_length) + { + return -1; + } + + *word_start = i; + + while ((string[i] != ' ') && (i < string_length)) + { + i += 1; + } + + *word_length = (i - *word_start); + + return 0; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ + +/* See: "sequence.h" */ +int JH_sequence_from_undercase_string +( + const JH_char string [const restrict], + const size_t string_length, + struct JH_knowledge k [const restrict static 1], + JH_index * sequence [const restrict static 1], + size_t sequence_capacity [const restrict static 1], + size_t sequence_length [const restrict static 1], + FILE io [const restrict static 1] +) +{ + size_t word_start, word_length; + size_t i; + + i = 0; + + *sequence_length = 0; + + JH_DEBUG + ( + io, + JH_DEBUG_SEQUENCE_FROM_STRING, + "Converting string of size %lu to sequence.", + string_length + ); + + if + ( + JH_sequence_append_right + ( + sequence, + JH_START_OF_SEQUENCE_ID, + sequence_capacity, + sequence_length, + io + ) < 0 + ) + { + *sequence_length = 0; + + return -1; + } + + JH_S_DEBUG + ( + io, + JH_DEBUG_SEQUENCE_FROM_STRING, + "[SOS] added to sequence." + ); + + while (i < string_length) + { + if (find_word(string, string_length, i, &word_start, &word_length) < 0) + { + break; + } + + JH_DEBUG + ( + io, + JH_DEBUG_SEQUENCE_FROM_STRING, + "Word of size %lu found in string at index %lu.", + word_length, + word_start + ); + + if + ( + add_word_to_sequence + ( + string, + word_start, + word_length, + sequence, + sequence_capacity, + sequence_length, + k, + io + ) < 0 + ) + { + *sequence_length = 0; + + return -1; + } + + i = (word_start + word_length); + } + + if + ( + JH_sequence_append_right + ( + sequence, + JH_END_OF_SEQUENCE_ID, + sequence_capacity, + sequence_length, + io + ) < 0 + ) + { + *sequence_length = 0; + + return -1; + } + + return 0; +} diff --git a/src/sequence/sequence_to_string.c b/src/sequence/sequence_to_string.c new file mode 100644 index 0000000..6794fcb --- /dev/null +++ b/src/sequence/sequence_to_string.c @@ -0,0 +1,196 @@ +#define _POSIX_C_SOURCE 200809L +#include <stdlib.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../core/char.h" +#include "../core/index.h" + +#include "../error/error.h" + +#include "../knowledge/knowledge.h" + +#include "sequence.h" + +/******************************************************************************/ +/** MEMORY ALLOCATION *********************************************************/ +/******************************************************************************/ +static int ensure_string_capacity +( + JH_char * string [const restrict static 1], + size_t string_capacity [const restrict static 1], + const size_t string_required_capacity, + FILE io [const restrict static 1] +) +{ + JH_char * new_string; + + if (string_required_capacity <= *string_capacity) + { + return 0; + } + + new_string = + (JH_char *) realloc + ( + (void *) *string, + ((size_t) string_required_capacity) * sizeof(JH_char) + ); + + if (new_string== (JH_char *) NULL) + { + JH_S_ERROR + ( + io, + "Unable to reallocate memory to match string's required size." + ); + + return -1; + } + + *string_capacity = string_required_capacity; + *string = new_string; + + return 1; +} + +/******************************************************************************/ +/** ADD WORD ******************************************************************/ +/******************************************************************************/ +static int increment_required_capacity +( + size_t current_capacity [const restrict static 1], + const size_t increase_factor, + FILE io [const restrict static 1] +) +{ + if ((JH_INDEX_MAX - increase_factor) < *current_capacity) + { + JH_S_ERROR + ( + io, + "String capacity increment aborted, as the new capacity would not " + "fit in a JH_index variable." + ); + + return -1; + } + + *current_capacity += increase_factor; + + if ((SIZE_MAX / sizeof(JH_char)) < *current_capacity) + { + *current_capacity -= increase_factor; + + JH_S_ERROR + ( + io, + "String capacity increment aborted, as the new size would not fit " + "in a size_t variable." + ); + + return -2; + } + + return 0; +} + +static int add_word +( + const JH_index word_id, + struct JH_knowledge k [const restrict static 1], + JH_char * destination [const restrict static 1], + size_t destination_capacity [const restrict static 1], + size_t destination_length [const restrict static 1], + FILE io [const restrict static 1] +) +{ + const JH_char * word; + JH_index word_size; + size_t insertion_point; + + if (word_id < JH_RESERVED_IDS_COUNT) + { + return 0; + } + + (void) JH_knowledge_lock_access(k, io); + JH_knowledge_get_word(k, word_id, &word, &word_size); + (void) JH_knowledge_unlock_access(k, io); + + insertion_point = *destination_length; + + /* word_size includes '\n', which will be replaced by a space. */ + /* (word_size == JH_INDEX_MAX) ==> could not have learned word. */ + if (increment_required_capacity(destination_length, (word_size + 1), io) < 0) + { + return -1; + } + + if + ( + ensure_string_capacity + ( + destination, + destination_capacity, + *destination_length, + io + ) < 0 + ) + { + return -2; + } + + memcpy + ( + (*destination + insertion_point), + (const void *) word, + word_size + ); + + (*destination)[*destination_length - 1] = ' '; + + return 0; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ +int JH_sequence_to_undercase_string +( + const JH_index sequence [const restrict static 1], + const size_t sequence_length, + struct JH_knowledge k [const restrict static 1], + JH_char * destination [const restrict static 1], + size_t destination_capacity [const restrict static 1], + size_t destination_length [const restrict static 1], + FILE io [const restrict static 1] +) +{ + size_t i; + + *destination_length = 0; + + for (i = 0; i < sequence_length; ++i) + { + if + ( + add_word + ( + sequence[i], + k, + destination, + destination_capacity, + destination_length, + io + ) < 0 + ) + { + *destination_length = 0; + + return -1; + } + } + + return 0; +} diff --git a/src/sequence/sequence_types.h b/src/sequence/sequence_types.h new file mode 100644 index 0000000..bce5644 --- /dev/null +++ b/src/sequence/sequence_types.h @@ -0,0 +1,9 @@ +#ifndef _JH_CORE_SEQUENCE_TYPES_H_ +#define _JH_CORE_SEQUENCE_TYPES_H_ + +#define JH_START_OF_SEQUENCE_ID 0 +#define JH_END_OF_SEQUENCE_ID 1 + +#define JH_RESERVED_IDS_COUNT 2 + +#endif diff --git a/src/server/CMakeLists.txt b/src/server/CMakeLists.txt new file mode 100644 index 0000000..3b64500 --- /dev/null +++ b/src/server/CMakeLists.txt @@ -0,0 +1,18 @@ +set( + SRC_FILES ${SRC_FILES} + ${CMAKE_CURRENT_SOURCE_DIR}/server.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_create_socket.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_finalize.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_initialize.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_joining_threads.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_new_connection.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_signal.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_wait_for_event.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_worker.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_worker_handle_request.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_worker_receive.c + ${CMAKE_CURRENT_SOURCE_DIR}/server_worker_send.c +) + +set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) + diff --git a/src/server/server.c b/src/server/server.c new file mode 100644 index 0000000..8a72bab --- /dev/null +++ b/src/server/server.c @@ -0,0 +1,100 @@ +#include <signal.h> +#include <string.h> +#include <stdio.h> + +#include "../parameters/parameters.h" + +#include "server.h" + +int JH_server_main +( + const struct JH_parameters params [const restrict static 1] +) +{ + struct JH_server server; + JH_index retries; + + /* TODO + if (JH_server_set_signal_handlers < 0) + { + return -1; + } + */ + + if (JH_server_initialize(&server, params) < 0) + { + return -1; + } + + while (JH_server_is_running()) + { + switch (JH_server_wait_for_event(&server)) + { + case 0: /* Timed out or signal'd. */ + JH_S_DEBUG(stderr, 1, "Timed out..."); + JH_server_handle_joining_threads(&server); + + retries = 0; + + break; + + case 1: /* New client attempted connection. */ + JH_S_DEBUG(stderr, 1, "New connection."); + JH_server_handle_joining_threads(&server); + (void) JH_server_handle_new_connection(&server); + + retries = 0; + + break; + + case -1: /* Something bad happened. */ + retries += 1; + + if (retries == JH_SERVER_MAX_RETRIES) + { + JH_server_finalize(&server); + + return -1; + } + + break; + + default: + JH_S_PROG_ERROR + ( + stderr, + "Unexpected wait_for_event return value." + ); + + break; + } + } + + /* Waiting for the threads to join... */ + while (server.workers.currently_running > 0) + { + switch (JH_server_wait_for_event(&server)) + { + case 0: /* Timed out. */ + case 1: /* New client attempted connection. */ + JH_server_handle_joining_threads(&server); + break; + + case -1: /* Something bad happened. */ + retries += 1; + + if (retries == JH_SERVER_MAX_RETRIES) + { + JH_server_finalize(&server); + + return -1; + } + break; + } + } + + JH_server_finalize(&server); + + return 0; +} + diff --git a/src/server/server.h b/src/server/server.h new file mode 100644 index 0000000..9d7f4b1 --- /dev/null +++ b/src/server/server.h @@ -0,0 +1,83 @@ +#ifndef _JH_SERVER_SERVER_H_ +#define _JH_SERVER_SERVER_H_ + +#include "../parameters/parameters_types.h" + +#include "server_types.h" + +int JH_server_initialize +( + struct JH_server server [const restrict static 1], + const struct JH_parameters params [const restrict static 1] +); + +int JH_server_socket_open +( + struct JH_server_socket server_socket [const restrict static 1], + const char socket_name [const restrict static 1] +); + +void JH_server_request_termination (void); +int JH_server_is_running (void); +int JH_server_set_signal_handlers (void); + +int JH_server_main +( + const struct JH_parameters params [const restrict static 1] +); + +void JH_server_finalize (struct JH_server [const restrict static 1]); + +int JH_server_wait_for_event +( + struct JH_server server [const restrict static 1] +); + +void JH_server_handle_joining_threads +( + struct JH_server server [const restrict static 1] +); + +int JH_server_handle_new_connection +( + struct JH_server server [const restrict static 1] +); + +void * JH_server_worker_main (void * input); + +int JH_server_worker_receive +( + struct JH_server_worker worker [const restrict static 1] +); + +int JH_server_worker_handle_request +( + struct JH_server_worker worker [const restrict static 1] +); + +int JH_server_worker_send_confirm_pipelining_support +( + struct JH_server_worker worker [const restrict static 1] +); + +int JH_server_worker_send_confirm_protocol_version +( + struct JH_server_worker worker [const restrict static 1] +); + +int JH_server_worker_send_positive +( + struct JH_server_worker worker [const restrict static 1] +); + +int JH_server_worker_send_negative +( + struct JH_server_worker worker [const restrict static 1] +); + +int JH_server_worker_send_generated_reply +( + struct JH_server_worker worker [const restrict static 1] +); + +#endif diff --git a/src/server/server_create_socket.c b/src/server/server_create_socket.c new file mode 100644 index 0000000..aa74a8d --- /dev/null +++ b/src/server/server_create_socket.c @@ -0,0 +1,190 @@ +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <string.h> +#include <unistd.h> + +#include <sys/socket.h> +#include <sys/un.h> + +#include "../error/error.h" + +#include "server.h" + +static int create_socket (int result [const restrict static 1]) +{ + const int old_errno = errno; + + errno = 0; + *result = socket(AF_UNIX, SOCK_STREAM, 0); + + if (*result == -1) + { + JH_FATAL + ( + stderr, + "Unable to create server socket: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + return 0; +} + +static int bind_socket +( + const int socket, + const char socket_name [const restrict static 1] +) +{ + struct sockaddr_un addr; + const int old_errno = errno; + + errno = 0; + memset(&addr, 0, sizeof(struct sockaddr_un)); + + addr.sun_family = AF_UNIX; + + /* addr.sun_path == 108. Using 107 ensure null-termination. */ + strncpy(addr.sun_path, socket_name, 107); + + errno = old_errno; + + if + ( + bind + ( + socket, + (const struct sockaddr *) &addr, + (socklen_t) sizeof(struct sockaddr_un) + ) != 0 + ) + { + JH_FATAL + ( + stderr, + "Unable to bind server socket to %s: %s.", + socket_name, + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + return 0; +} + +static int set_socket_to_unblocking (const int socket) +{ + int current_flags; + const int old_errno = errno; + + current_flags = fcntl(socket, F_GETFD); + + if (current_flags == -1) + { + JH_FATAL + ( + stderr, + "Unable to get server socket properties: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + /* current_flags = current_flags & (~O_NONBLOCK); */ + + current_flags = fcntl(socket, F_SETFD, (current_flags | O_NONBLOCK)); + + if (current_flags == -1) + { + JH_FATAL + ( + stderr, + "Unable to set server socket properties: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -2; + } + + errno = old_errno; + + return 0; +} + +static int set_socket_as_listener (const int socket) +{ + const int old_errno = errno; + + if (listen(socket, JH_SERVER_SOCKET_LISTEN_BACKLOG) != 0) + { + JH_FATAL + ( + stderr, + "Unable to set server socket properties: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + return 0; +} + +int JH_server_socket_open +( + struct JH_server_socket server_socket [const restrict static 1], + const char socket_name [const restrict static 1] +) +{ + if (create_socket(&(server_socket->file_descriptor)) < 0) + { + return -1; + } + + if (bind_socket(server_socket->file_descriptor, socket_name) < 0) + { + close(server_socket->file_descriptor); + + return -1; + } + + if (set_socket_to_unblocking(server_socket->file_descriptor) < 0) + { + close(server_socket->file_descriptor); + + return -1; + } + + if (set_socket_as_listener(server_socket->file_descriptor) < 0) + { + close(server_socket->file_descriptor); + + return -1; + } + + FD_ZERO(&(server_socket->as_a_set)); + FD_SET(server_socket->file_descriptor, &(server_socket->as_a_set)); + + return 0; +} diff --git a/src/server/server_finalize.c b/src/server/server_finalize.c new file mode 100644 index 0000000..25ea672 --- /dev/null +++ b/src/server/server_finalize.c @@ -0,0 +1,42 @@ +#include <stdlib.h> +#include <unistd.h> + +#include "../parameters/parameters.h" + +#include "server.h" + +static void finalize_thread_collection +( + struct JH_server_thread_collection workers [const restrict static 1] +) +{ + free((void *) workers->threads); + + workers->threads_capacity = 0; + + pthread_mutex_destroy(&(workers->mutex)); + pthread_barrier_destroy(&(workers->barrier)); + + workers->currently_running = 0; +} + +static void finalize_socket +( + struct JH_server_socket socket [const restrict static 1] +) +{ + FD_ZERO(&(socket->as_a_set)); + + close(socket->file_descriptor); + + socket->file_descriptor = -1; +} + +void JH_server_finalize +( + struct JH_server server [const restrict static 1] +) +{ + finalize_thread_collection(&(server->workers)); + finalize_socket(&(server->socket)); +} diff --git a/src/server/server_initialize.c b/src/server/server_initialize.c new file mode 100644 index 0000000..32a9f52 --- /dev/null +++ b/src/server/server_initialize.c @@ -0,0 +1,107 @@ +#include <signal.h> +#include <string.h> +#include <stdio.h> + +#include "../parameters/parameters.h" + +#include "../knowledge/knowledge.h" + +#include "server.h" + +static int initialize_worker_collection +( + struct JH_server_thread_collection c [const restrict static 1] +) +{ + int error; + + c->threads = (struct JH_server_thread_data *) NULL; + c->threads_capacity = 0; + c->currently_running = 0; + + error = + pthread_mutex_init + ( + &(c->mutex), + (const pthread_mutexattr_t *) NULL + ); + + if (error != 0) + { + JH_FATAL + ( + stderr, + "Unable to initialize worker collection's mutex: %s.", + strerror(error) + ); + + return -1; + } + + error = + pthread_barrier_init + ( + &(c->barrier), + (const pthread_barrierattr_t *) NULL, + 2 + ); + + if (error != 0) + { + JH_FATAL + ( + stderr, + "[F] Unable to initialize worker collection's barrier: %s.", + strerror(error) + ); + + return -1; + } + + return 0; +} + +void initialize_thread_parameters +( + struct JH_server server [const restrict static 1], + const struct JH_parameters params [const restrict static 1] +) +{ + server->thread_params.thread_collection = &(server->workers); + server->thread_params.server_params = params; + server->thread_params.knowledge = &(server->k); + server->thread_params.socket = -1; +} + +int JH_server_initialize +( + struct JH_server server [const restrict static 1], + const struct JH_parameters params [const restrict static 1] +) +{ + if (initialize_worker_collection(&(server->workers)) < 0) + { + return -1; + } + + if (JH_knowledge_initialize(&(server->k)) < 0) + { + return -1; + } + + if + ( + JH_server_socket_open + ( + &(server->socket), + JH_parameters_get_session_name(params) + ) < 0 + ) + { + return -2; + } + + initialize_thread_parameters(server, params); + + return 0; +} diff --git a/src/server/server_joining_threads.c b/src/server/server_joining_threads.c new file mode 100644 index 0000000..e1d92ca --- /dev/null +++ b/src/server/server_joining_threads.c @@ -0,0 +1,38 @@ +#include <sys/socket.h> + +#include <errno.h> +#include <string.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <unistd.h> + +#include "../parameters/parameters.h" + +#include "server.h" + +void JH_server_handle_joining_threads +( + struct JH_server server [const restrict static 1] +) +{ + JH_index i; + + pthread_mutex_lock(&(server->workers.mutex)); + + for (i = 0; i < server->workers.threads_capacity; ++i) + { + if (server->workers.threads[i].state == JH_SERVER_JOINING_THREAD) + { + JH_DEBUG(stderr, 1, "Joining thread %u", i); + + pthread_join(server->workers.threads[i].posix_id, (void **) NULL); + + server->workers.threads[i].state = JH_SERVER_NO_THREAD; + + server->workers.currently_running -= 1; + } + } + + pthread_mutex_unlock(&(server->workers.mutex)); +} diff --git a/src/server/server_new_connection.c b/src/server/server_new_connection.c new file mode 100644 index 0000000..23a2770 --- /dev/null +++ b/src/server/server_new_connection.c @@ -0,0 +1,180 @@ +#include <sys/socket.h> + +#include <errno.h> +#include <string.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <unistd.h> + +#include "../parameters/parameters.h" + +#include "server.h" + +static int get_new_socket (struct JH_server server [const restrict static 1]) +{ + const int old_errno = errno; + + server->thread_params.socket = + accept + ( + server->socket.file_descriptor, + (struct sockaddr *) NULL, + (socklen_t *) NULL + ); + + if (server->thread_params.socket == -1) + { + JH_ERROR + ( + stderr, + "Unable to accept on the server's socket: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + return 0; +} + +static int get_new_thread (struct JH_server server [const restrict static 1]) +{ + struct JH_server_thread_data * new_threads; + JH_index i; + + pthread_mutex_lock(&(server->workers.mutex)); + + for (i = 0; i < server->workers.threads_capacity; ++i) + { + if (server->workers.threads[i].state == JH_SERVER_NO_THREAD) + { + server->thread_params.thread_id = i; + + pthread_mutex_unlock(&(server->workers.mutex)); + + return 0; + } + } + + if + ( + (server->workers.threads_capacity == JH_INDEX_MAX) + || + ( + (size_t) (server->workers.threads_capacity + 1) + > (SIZE_MAX / sizeof(struct JH_server_thread_data)) + ) + ) + { + JH_S_ERROR + ( + stderr, + "Maximum number of concurrent threads attained, unable to add more." + ); + + pthread_mutex_unlock(&(server->workers.mutex)); + + return -1; + } + + server->thread_params.thread_id = server->workers.threads_capacity; + server->workers.threads_capacity += 1; + + new_threads = + (struct JH_server_thread_data *) realloc + ( + server->workers.threads, + ( + sizeof(struct JH_server_thread_data) + * ((size_t) server->workers.threads_capacity) + ) + ); + + if (new_threads == ((struct JH_server_thread_data *) NULL)) + { + JH_S_ERROR + ( + stderr, + "Reallocation of the threads' data list failed." + ); + + pthread_mutex_unlock(&(server->workers.mutex)); + + return -1; + } + + server->workers.threads = new_threads; + + pthread_mutex_unlock(&(server->workers.mutex)); + + return 0; +} + +static int spawn_thread (struct JH_server server [const restrict static 1]) +{ + const JH_index thread_id = server->thread_params.thread_id; + int error; + + server->workers.threads[thread_id].state = JH_SERVER_RUNNING_THREAD; + + error = + pthread_create + ( + &(server->workers.threads[thread_id].posix_id), + (const pthread_attr_t *) NULL, + JH_server_worker_main, + (void *) &(server->thread_params) + ); + + if (error != 0) + { + JH_ERROR + ( + stderr, + "Unable to spawn thread: %s.", + strerror(error) + ); + + server->workers.threads[thread_id].state = JH_SERVER_NO_THREAD; + + return -1; + } + + pthread_barrier_wait(&(server->workers.barrier)); + + server->workers.currently_running += 1; + + return 0; +} + +int JH_server_handle_new_connection +( + struct JH_server server [const restrict static 1] +) +{ + if (get_new_socket(server) < 0) + { + return -1; + } + + if (get_new_thread(server) < 0) + { + close(server->thread_params.socket); + + return -2; + } + + if (spawn_thread(server) < 0) + { + close(server->thread_params.socket); + + return -3; + } + + return 0; +} diff --git a/src/server/server_signal.c b/src/server/server_signal.c new file mode 100644 index 0000000..9361382 --- /dev/null +++ b/src/server/server_signal.c @@ -0,0 +1,41 @@ +#include <signal.h> +#include <string.h> +#include <stdio.h> + +#include "server.h" + +static volatile char JH_SERVER_IS_RUNNING = (char) 1; + +static void request_termination (int const signo) +{ + if ((signo == SIGINT) || (signo == SIGTERM)) + { + JH_server_request_termination(); + } +} + +void JH_server_request_termination (void) +{ + JH_SERVER_IS_RUNNING = (char) 0; +} + +int JH_server_is_running (void) +{ + return (int) JH_SERVER_IS_RUNNING; +} + +int JH_server_set_signal_handlers (void) +{ + /* + struct sigaction act; + + act.sa_handler = request_termination; + act.sa_mask = + act.sa_flags = + act.sa_restorer = + */ + + /* TODO */ + + return -1; +} diff --git a/src/server/server_types.h b/src/server/server_types.h new file mode 100644 index 0000000..bd82282 --- /dev/null +++ b/src/server/server_types.h @@ -0,0 +1,88 @@ +#ifndef _JH_SERVER_SERVER_TYPES_H_ +#define _JH_SERVER_SERVER_TYPES_H_ + +#include <sys/time.h> + +#ifndef JH_RUNNING_FRAMA_C + #include <pthread.h> +#endif + +#include "../core/index_types.h" + +#include "../knowledge/knowledge_types.h" + +#include "../parameters/parameters_types.h" + +#include "../error/error.h" + +#define JH_SERVER_MAX_RETRIES 10 +#define JH_SERVER_BUFFER_SIZE 0 + +#define JH_SERVER_SOCKET_ACCEPT_TIMEOUT_SEC 5 +#define JH_SERVER_SOCKET_LISTEN_BACKLOG 5 + +enum JH_server_thread_state +{ + JH_SERVER_JOINING_THREAD, + JH_SERVER_RUNNING_THREAD, + JH_SERVER_NO_THREAD +}; + +struct JH_server_thread_data +{ +#ifndef JH_RUNNING_FRAMA_C + pthread_t posix_id; +#endif + enum JH_server_thread_state state; +}; + +struct JH_server_thread_collection +{ + struct JH_server_thread_data * threads; + JH_index threads_capacity; +#ifndef JH_RUNNING_FRAMA_C + pthread_mutex_t mutex; + pthread_barrier_t barrier; +#endif + JH_index currently_running; +}; + +struct JH_server_socket +{ + int file_descriptor; + fd_set as_a_set; + struct timeval timeout; +}; + +struct JH_server_thread_parameters +{ + struct JH_server_thread_collection * thread_collection; + const struct JH_parameters * server_params; + struct JH_knowledge * knowledge; + JH_index thread_id; + int socket; +}; + +struct JH_server_worker +{ + struct JH_server_thread_parameters params; + FILE * socket_as_file; + + char * buffer; + size_t buffer_capacity; + size_t buffer_length; + + JH_index * sequence_buffer; + size_t sequence_buffer_capacity; + size_t sequence_buffer_length; +}; + +struct JH_server +{ + struct JH_server_thread_collection workers; + struct JH_server_socket socket; + struct JH_server_thread_parameters thread_params; + struct JH_knowledge k; +}; + +#endif diff --git a/src/server/server_wait_for_event.c b/src/server/server_wait_for_event.c new file mode 100644 index 0000000..c949438 --- /dev/null +++ b/src/server/server_wait_for_event.c @@ -0,0 +1,62 @@ +#include <sys/select.h> + +#include <errno.h> +#include <stdio.h> +#include <string.h> + +#include "../error/error.h" + +#include "server.h" + +int JH_server_wait_for_event +( + struct JH_server server [const static 1] +) +{ + int ready_fds; + const int old_errno = errno; + fd_set ready_to_read; + + ready_to_read = server->socket.as_a_set; + + /* call to select may alter timeout */ + memset((void *) &(server->socket.timeout), 0, sizeof(struct timeval)); + + server->socket.timeout.tv_sec = JH_SERVER_SOCKET_ACCEPT_TIMEOUT_SEC; + + errno = 0; + + ready_fds = select + ( + (server->socket.file_descriptor + 1), + &ready_to_read, + (fd_set *) NULL, + (fd_set *) NULL, + &(server->socket.timeout) + ); + + JH_DEBUG(stderr, 1, "SELECT returned: %i, errno is %i.", ready_fds, errno); + + if (errno == EINTR) + { + ready_fds = 0; + } + + if (ready_fds == -1) + { + JH_FATAL + ( + stderr, + "Unable to wait on server socket: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + return ready_fds; +} diff --git a/src/server/server_worker.c b/src/server/server_worker.c new file mode 100644 index 0000000..62f37be --- /dev/null +++ b/src/server/server_worker.c @@ -0,0 +1,108 @@ +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <errno.h> + +#include "server.h" + +static int initialize +( + struct JH_server_worker worker [const restrict static 1], + void * input +) +{ + const int old_errno = errno; + + memcpy + ( + (void *) &(worker->params), + (const void *) input, + sizeof(struct JH_server_thread_parameters) + ); + + pthread_barrier_wait(&(worker->params.thread_collection->barrier)); + + worker->buffer = (char *) NULL; + worker->buffer_capacity = 0; + worker->buffer_length = 0; + + worker->sequence_buffer = (JH_index *) NULL; + worker->sequence_buffer_capacity = 0; + worker->sequence_buffer_length = 0; + + worker->socket_as_file = fdopen(worker->params.socket, "w+"); + + errno = 0; + + if (worker->socket_as_file == (FILE *) NULL) + { + JH_ERROR + ( + stderr, + "Unable to open client socket as a file stream: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + return 0; +} + +static void finalize +( + struct JH_server_worker worker [const restrict static 1] +) +{ + if (worker->socket_as_file != (FILE *) NULL) + { + fclose(worker->socket_as_file); + + worker->socket_as_file = NULL; + } + + if (worker->buffer != (char *) NULL) + { + free((void *) worker->buffer); + + worker->buffer = (char *) NULL; + } + + worker->buffer_capacity = 0; + worker->buffer_length = 0; + + pthread_mutex_lock(&(worker->params.thread_collection->mutex)); + + worker->params.thread_collection->threads[worker->params.thread_id].state = + JH_SERVER_JOINING_THREAD; + + pthread_mutex_unlock(&(worker->params.thread_collection->mutex)); +} + +void * JH_server_worker_main (void * input) +{ + struct JH_server_worker worker; + + initialize(&worker, input); + + while (JH_server_is_running()) + { + if (JH_server_worker_receive(&worker) < 0) + { + break; + } + + if (JH_server_worker_handle_request(&worker) < 0) + { + break; + } + } + + finalize(&worker); + + return NULL; +} diff --git a/src/server/server_worker_handle_request.c b/src/server/server_worker_handle_request.c new file mode 100644 index 0000000..03c7c43 --- /dev/null +++ b/src/server/server_worker_handle_request.c @@ -0,0 +1,350 @@ +#include "../pervasive.h" + +#include "../error/error.h" + +#include "../sequence/sequence.h" + +#include "../knowledge/knowledge.h" + +#include "../parameters/parameters.h" + +#include "server.h" + +static int load_reply +( + struct JH_server_worker worker [const restrict static 1] +) +{ + JH_index rarest_word_id; + + if + ( + JH_knowledge_lock_access + ( + worker->params.knowledge, + worker->socket_as_file + ) < 0 + ) + { + return -1; + } + + if + ( + JH_knowledge_rarest_word + ( + worker->params.knowledge, + worker->sequence_buffer, + worker->sequence_buffer_length, + &rarest_word_id + ) < 0 + ) + { + JH_knowledge_unlock_access + ( + worker->params.knowledge, + worker->socket_as_file + ); + + JH_S_ERROR(worker->socket_as_file, "Could not find rarest word."); + + return -1; + } + + JH_knowledge_unlock_access + ( + worker->params.knowledge, + worker->socket_as_file + ); + + JH_DEBUG + ( + worker->socket_as_file, + 1, + "Word selected as pillar: %u", + rarest_word_id + ); + + if + ( + JH_sequence_create_from + ( + rarest_word_id, + (size_t *) NULL, + worker->params.knowledge, + JH_parameters_get_markov_order(worker->params.server_params), + &(worker->sequence_buffer), + &(worker->sequence_buffer_capacity), + &(worker->sequence_buffer_length), + worker->socket_as_file + ) < 0 + ) + { + JH_S_ERROR + ( + worker->socket_as_file, + "Could not create reply from selected word." + ); + + return -1; + } + + if + ( + JH_sequence_to_undercase_string + ( + worker->sequence_buffer, + worker->sequence_buffer_length, + worker->params.knowledge, + &(worker->buffer), + &(worker->buffer_capacity), + &(worker->buffer_length), + worker->socket_as_file + ) < 0 + ) + { + JH_S_ERROR + ( + worker->socket_as_file, + "Could not convert reply sequence to string." + ); + + return -1; + } + + return 0; +} + +static int handle_rpv +( + struct JH_server_worker worker [const restrict static 1] +) +{ + /* TODO */ + + return -1; +} + +static int handle_rps +( + struct JH_server_worker worker [const restrict static 1] +) +{ + if (JH_server_worker_send_confirm_pipelining_support(worker) < 0) + { + return -1; + } + + return JH_server_worker_send_positive(worker); +} + +static int handle_rl +( + struct JH_server_worker worker [const restrict static 1] +) +{ + if + ( + JH_sequence_from_undercase_string + ( + (const JH_char *) (worker->buffer + 4), + (worker->buffer_length - 5), + worker->params.knowledge, + &(worker->sequence_buffer), + &(worker->sequence_buffer_capacity), + &(worker->sequence_buffer_length), + worker->socket_as_file + ) < 0 + ) + { + return JH_server_worker_send_negative(worker); + } + + if + ( + JH_knowledge_lock_access + ( + worker->params.knowledge, + worker->socket_as_file + ) < 0 + ) + { + return JH_server_worker_send_negative(worker); + } + + if + ( + JH_knowledge_learn_sequence + ( + worker->params.knowledge, + worker->sequence_buffer, + worker->sequence_buffer_length, + JH_parameters_get_markov_order(worker->params.server_params), + worker->socket_as_file + ) < 0 + ) + { + JH_knowledge_unlock_access + ( + worker->params.knowledge, + worker->socket_as_file + ); + + return JH_server_worker_send_negative(worker); + } + + JH_knowledge_unlock_access + ( + worker->params.knowledge, + worker->socket_as_file + ); + + return JH_server_worker_send_positive(worker); +} + +static int handle_rlr +( + struct JH_server_worker worker [const restrict static 1] +) +{ + if + ( + JH_sequence_from_undercase_string + ( + (const JH_char *) (worker->buffer + 6), + (worker->buffer_length - 7), + worker->params.knowledge, + &(worker->sequence_buffer), + &(worker->sequence_buffer_capacity), + &(worker->sequence_buffer_length), + worker->socket_as_file + ) < 0 + ) + { + return JH_server_worker_send_negative(worker); + } + + if + ( + JH_knowledge_lock_access + ( + worker->params.knowledge, + worker->socket_as_file + ) < 0 + ) + { + return JH_server_worker_send_negative(worker); + } + + if + ( + JH_knowledge_learn_sequence + ( + worker->params.knowledge, + worker->sequence_buffer, + worker->sequence_buffer_length, + JH_parameters_get_markov_order(worker->params.server_params), + worker->socket_as_file + ) < 0 + ) + { + JH_knowledge_unlock_access + ( + worker->params.knowledge, + worker->socket_as_file + ); + + return JH_server_worker_send_negative(worker); + } + + JH_knowledge_unlock_access + ( + worker->params.knowledge, + worker->socket_as_file + ); + + if (load_reply(worker) < 0) + { + return JH_server_worker_send_negative(worker); + } + + if (JH_server_worker_send_generated_reply(worker) < 0) + { + return -1; + } + + return JH_server_worker_send_positive(worker); +} + +static int handle_rr +( + struct JH_server_worker worker [const restrict static 1] +) +{ + if + ( + JH_sequence_from_undercase_string + ( + (const JH_char *) (worker->buffer + 4), + (worker->buffer_length - 5), + worker->params.knowledge, + &(worker->sequence_buffer), + &(worker->sequence_buffer_capacity), + &(worker->sequence_buffer_length), + worker->socket_as_file + ) < 0 + ) + { + JH_S_DEBUG(worker->socket_as_file, 1, "?RR failed at string to sequence."); + + return JH_server_worker_send_negative(worker); + } + + if (load_reply(worker) < 0) + { + JH_S_DEBUG(worker->socket_as_file, 1, "?RR failed at load reply."); + return JH_server_worker_send_negative(worker); + } + + if (JH_server_worker_send_generated_reply(worker) < 0) + { + return -1; + } + + return JH_server_worker_send_positive(worker); +} + +int JH_server_worker_handle_request +( + struct JH_server_worker worker [const restrict static 1] +) +{ + if (JH_IS_PREFIX("?RPV ", worker->buffer)) + { + return handle_rpv(worker); + } + else if (JH_IS_PREFIX("?RPS ", worker->buffer)) + { + return handle_rps(worker); + } + else if (JH_IS_PREFIX("?RL ", worker->buffer)) + { + return handle_rl(worker); + } + else if (JH_IS_PREFIX("?RR ", worker->buffer)) + { + return handle_rr(worker); + } + else if (JH_IS_PREFIX("?RLR ", worker->buffer)) + { + return handle_rlr(worker); + } + else + { + JH_S_ERROR(worker->socket_as_file, "Unsupported request received."); + + return JH_server_worker_send_negative(worker); + } + + return 0; +} diff --git a/src/server/server_worker_receive.c b/src/server/server_worker_receive.c new file mode 100644 index 0000000..a184073 --- /dev/null +++ b/src/server/server_worker_receive.c @@ -0,0 +1,46 @@ +#include <stdio.h> +#include <string.h> +#include <errno.h> + +#include "../error/error.h" + +#include "server.h" + +int JH_server_worker_receive +( + struct JH_server_worker worker [const restrict static 1] +) +{ + const int old_errno = errno; + ssize_t received; + + errno = 0; + + received = + getline + ( + &(worker->buffer), + &(worker->buffer_capacity), + worker->socket_as_file + ); + + if (received == -1) + { + JH_ERROR + ( + stderr, + "Thread could not receive from socket: %s.", + strerror(errno) + ); + + errno = old_errno; + + return -1; + } + + errno = old_errno; + + worker->buffer_length = (size_t) received; + + return 0; +} diff --git a/src/server/server_worker_send.c b/src/server/server_worker_send.c new file mode 100644 index 0000000..79c1709 --- /dev/null +++ b/src/server/server_worker_send.c @@ -0,0 +1,219 @@ +#include <stdio.h> +#include <string.h> + +#include "../error/error.h" + +#include "server.h" + +int JH_server_worker_send_confirm_pipelining_support +( + struct JH_server_worker worker [const restrict static 1] +) +{ + int err; + + err = fprintf(worker->socket_as_file, "!CPS 0\n"); + + if (err == 0) + { + JH_S_ERROR + ( + stderr, + "Thread could not write anything to socket." + ); + + return -1; + } + else if (err < 0) + { + JH_ERROR + ( + stderr, + "Thread could not write to socket: %s.", + strerror(err) + ); + + return -1; + } + + return 0; +} + +int JH_server_worker_send_confirm_protocol_version +( + struct JH_server_worker worker [const restrict static 1] +) +{ + int err; + + err = fprintf(worker->socket_as_file, "!CPV 1\n"); + + if (err == 0) + { + JH_S_ERROR + ( + stderr, + "Thread could not write anything to socket." + ); + + return -1; + } + else if (err < 0) + { + JH_ERROR + ( + stderr, + "Thread could not write to socket: %s.", + strerror(err) + ); + + return -1; + } + + return 0; +} + +int JH_server_worker_send_positive +( + struct JH_server_worker worker [const restrict static 1] +) +{ + int err; + + err = fprintf(worker->socket_as_file, "!P\n"); + + if (err == 0) + { + JH_S_ERROR + ( + stderr, + "Thread could not write anything to socket." + ); + + return -1; + } + else if (err < 0) + { + JH_ERROR + ( + stderr, + "Thread could not write to socket: %s.", + strerror(err) + ); + + return -1; + } + + return 0; +} + +int JH_server_worker_send_negative +( + struct JH_server_worker worker [const restrict static 1] +) +{ + int err; + + err = fprintf(worker->socket_as_file, "!N\n"); + + if (err == 0) + { + JH_S_ERROR + ( + stderr, + "Thread could not write anything to socket." + ); + + return -1; + } + else if (err < 0) + { + JH_ERROR + ( + stderr, + "Thread could not write to socket: %s.", + strerror(err) + ); + + return -1; + } + + return 0; +} + +int JH_server_worker_send_generated_reply +( + struct JH_server_worker worker [const restrict static 1] +) +{ + int err; + size_t written; + + err = fputs + ( + "!GR ", + worker->socket_as_file + ); + + if (err == 0) + { + JH_S_ERROR + ( + stderr, + "Thread could not write anything to socket." + ); + + return -1; + } + else if (err < 0) + { + JH_ERROR + ( + stderr, + "Thread could not write to socket: %s.", + strerror(err) + ); + + return -1; + } + + written = + fwrite + ( + worker->buffer, + sizeof(JH_char), + worker->buffer_length, + worker->socket_as_file + ); + + if (written != (worker->buffer_length * sizeof(JH_char))) + { + // TODO: Error handling. + JH_S_ERROR + ( + stderr, + "Error while writing to socket." + ); + + return -1; + } + + err = fputs + ( + "\n", + worker->socket_as_file + ); + + if (err == 0) + { + JH_S_ERROR + ( + stderr, + "Thread could not write anything to socket." + ); + + return -1; + } + + return 0; +} |