| summaryrefslogtreecommitdiff |
diff options
Diffstat (limited to 'src')
26 files changed, 743 insertions, 401 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 07d8f30..25cacc2 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -1,9 +1,9 @@ -add_subdirectory(cli) add_subdirectory(core) add_subdirectory(knowledge) +add_subdirectory(parameters) add_subdirectory(pipe) -add_subdirectory(server) add_subdirectory(sequence) +add_subdirectory(server) add_subdirectory(storage) set( diff --git a/src/core/index.c b/src/core/index.c index dc52d03..5c93ed3 100644 --- a/src/core/index.c +++ b/src/core/index.c @@ -64,3 +64,19 @@ ZoO_index ZoO_index_random_up_to (const ZoO_index max) * ((float) max) ); } + +int ZoO_index_cmp (const ZoO_index a, const ZoO_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 index eb3c471..bd77cb4 100644 --- a/src/core/index.h +++ b/src/core/index.h @@ -21,4 +21,6 @@ ZoO_index ZoO_index_random (void); @*/ ZoO_index ZoO_index_random_up_to (const ZoO_index limit); +int ZoO_index_cmp (const ZoO_index a, const ZoO_index b); + #endif diff --git a/src/core/index_types.h b/src/core/index_types.h index 84a1e20..5514a2a 100644 --- a/src/core/index_types.h +++ b/src/core/index_types.h @@ -1,6 +1,8 @@ #ifndef _ZoO_CORE_INDEX_TYPES_H_ #define _ZoO_CORE_INDEX_TYPES_H_ +#include "../pervasive.h" + /* * ZoO_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 @@ -8,6 +10,7 @@ */ #include <limits.h> +#include <stdint.h> /* Must be unsigned. */ typedef unsigned int ZoO_index; @@ -15,9 +18,10 @@ typedef unsigned int ZoO_index; /* Must be > 0. */ #define ZoO_INDEX_MAX UINT_MAX - -#if (ZoO_INDEX_MAX > SIZE_MAX) - #error "ZoO_index should not be able to go higher than a size_t variable." +#ifndef ZoO_RUNNING_FRAMA_C + #if (ZoO_INDEX_MAX > SIZE_MAX) + #error "ZoO_index should not be able to go higher than a size_t variable." + #endif #endif #endif diff --git a/src/knowledge/CMakeLists.txt b/src/knowledge/CMakeLists.txt index 1245321..ba3293d 100644 --- a/src/knowledge/CMakeLists.txt +++ b/src/knowledge/CMakeLists.txt @@ -2,9 +2,13 @@ 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.h b/src/knowledge/knowledge.h index e868943..7f1bb42 100644 --- a/src/knowledge/knowledge.h +++ b/src/knowledge/knowledge.h @@ -61,24 +61,6 @@ int ZoO_knowledge_learn_markov_sequence const struct ZoO_pipe io [const restrict static 1] ); -int ZoO_knowledge_get_swt_sequences_ref -( - const struct ZoO_knowledge k [const static 1], - const ZoO_index initial_word, - const ZoO_index * restrict following_sequences_ref [const restrict static 1], - const ZoO_index * restrict following_sequences_weights [const restrict static 1], - ZoO_index following_sequences_weights_sum [const static 1], - const struct ZoO_pipe io [const restrict static 1] -); - -int ZoO_knowledge_get_sequence -( - const struct ZoO_knowledge k [const static 1], - const ZoO_index sequences_ref, - const ZoO_index * restrict sequence [const restrict static 1], - const struct ZoO_pipe io [const restrict static 1] -); - int ZoO_knowledge_get_word ( const struct ZoO_knowledge k [const static 1], @@ -106,26 +88,50 @@ int ZoO_knowledge_find_word_id ZoO_index result [const restrict static 1] ); -int ZoO_knowledge_find_tws_targets +int ZoO_knowledge_find_sequence ( const struct ZoO_knowledge k [const static 1], - const ZoO_index sequence [const restrict], - const ZoO_index markov_order, - const ZoO_index * restrict targets [const restrict static 1], - const ZoO_index * restrict targets_weights [const restrict static 1], - ZoO_index targets_weights_sum [const restrict static 1], - const struct ZoO_pipe io [const restrict static 1] + const ZoO_index sequence [const restrict static 1], + const ZoO_index markov_order, /* Pre: (> 1) */ + ZoO_index sequence_id [const restrict static 1] +); + +int ZoO_knowledge_find_markov_sequence +( + const ZoO_index sequence_id, + const struct ZoO_knowledge_sequence_collection sc [const restrict static 1], + ZoO_index result [const restrict static 1] ); -int ZoO_knowledge_find_swt_targets +int ZoO_knowledge_find_sequence_target +( + const ZoO_index target_id, + const struct ZoO_knowledge_sequence_data sd [const restrict static 1], + ZoO_index result [const restrict static 1] +); + +int ZoO_knowledge_random_tws_target ( const struct ZoO_knowledge k [const static 1], - const ZoO_index sequence [const restrict], - const size_t sequence_length, + ZoO_index target [const restrict static 1], + const ZoO_index word_id, + const ZoO_index sequence_id +); + +int ZoO_knowledge_random_swt_target +( + const struct ZoO_knowledge k [const static 1], + const ZoO_index sequence_id, + const ZoO_index word_id, + ZoO_index target [const restrict static 1] +); + +int ZoO_knowledge_copy_random_swt_sequence +( + const struct ZoO_knowledge k [const static 1], + ZoO_index sequence [const restrict static 1], + const ZoO_index word_id, const ZoO_index markov_order, - const ZoO_index * restrict targets [const restrict static 1], - const ZoO_index * restrict targets_weights [const restrict static 1], - ZoO_index targets_weights_sum [const restrict static 1], const struct ZoO_pipe io [const restrict static 1] ); diff --git a/src/knowledge/knowledge_finalize.c b/src/knowledge/knowledge_finalize.c index 9546650..6c249f0 100644 --- a/src/knowledge/knowledge_finalize.c +++ b/src/knowledge/knowledge_finalize.c @@ -2,52 +2,51 @@ #include "knowledge.h" -static void knowledge_sequence_collection_finalize + +static void knowledge_sequence_data_finalize ( - struct ZoO_knowledge_sequence_collection c [const restrict static 1] + struct ZoO_knowledge_sequence_data sd [const restrict static 1] ) { - ZoO_index i; + sd->occurrences = 0; - if (c->sequences_ref != (ZoO_index *) NULL) + if (sd->targets != (struct ZoO_knowledge_target *) NULL) { - free((void *) c->sequences_ref); - c->sequences_ref = (ZoO_index *) NULL; - } + free((void *) sd->targets); - if (c->sequences_ref_sorted != (ZoO_index *) NULL) - { - free((void *) c->sequences_ref_sorted); - c->sequences_ref_sorted = (ZoO_index *) NULL; + sd->targets = (struct ZoO_knowledge_target *) NULL; } - if (c->occurrences != (ZoO_index *) NULL) - { - free((void *) c->occurrences); - c->occurrences = (ZoO_index *) NULL; - } + sd->targets_length = 0; + +} + +static void knowledge_sequence_collection_finalize +( + struct ZoO_knowledge_sequence_collection c [const restrict static 1] +) +{ + ZoO_index i; + for (i = 0; i < c->sequences_ref_length; ++i) { - free((void *) c->targets[i]); - free((void *) c->targets_occurrences[i]); + knowledge_sequence_data_finalize(c->sequences_ref + i); } - c->sequences_ref_length = 0; - - if (c->targets != (ZoO_index **) NULL) + if (c->sequences_ref != (struct ZoO_knowledge_sequence_data *) NULL) { - free((void *) c->targets); - c->targets != (ZoO_index **) NULL; + free((void *) c->sequences_ref); + c->sequences_ref = (struct ZoO_knowledge_sequence_data *) NULL; } - free((void *) c->targets_length); - - if (c->targets_occurrences != (ZoO_index **) NULL) + if (c->sequences_ref_sorted != (ZoO_index *) NULL) { - free((void *) c->targets_occurrences); - c->targets_occurrences != (ZoO_index **) NULL; + free((void *) c->sequences_ref_sorted); + c->sequences_ref_sorted = (ZoO_index *) NULL; } + + c->sequences_ref_length = 0; } static void knowledge_word_finalize diff --git a/src/knowledge/knowledge_get_random_sequence.c b/src/knowledge/knowledge_get_random_sequence.c new file mode 100644 index 0000000..9055d31 --- /dev/null +++ b/src/knowledge/knowledge_get_random_sequence.c @@ -0,0 +1,83 @@ +#include <stdlib.h> + +#include "../core/char.h" +#include "../core/index.h" +#include "../sequence/sequence.h" + +#include "../pipe/pipe.h" + +#include "knowledge.h" + +static int weighted_random_pick +( + const struct ZoO_knowledge_sequence_collection sc [const restrict static 1], + const ZoO_index sum, + ZoO_index result [const restrict static 1] +) +{ + ZoO_index accumulator, random_number; + + accumulator = 0; + + if (sum == 0) + { + return -1; + } + + random_number = ZoO_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 ZoO_knowledge_copy_random_swt_sequence +( + const struct ZoO_knowledge k [const static 1], + ZoO_index sequence [const restrict static 1], + const ZoO_index word_id, + const ZoO_index markov_order, + const struct ZoO_pipe io [const restrict static 1] +) +{ + ZoO_index sequence_id; + + if + ( + weighted_random_pick + ( + &(k->words[word_id].swt), + k->words[word_id].occurrences, + &sequence_id + ) < 0 + ) + { + /* TODO: Err message. */ + + return -1; + } + + memcpy + ( + (void *) sequence, + (const void *) k->sequences[sequence_id], + (((size_t) (markov_order - 1)) * sizeof(ZoO_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..d9bf8a9 --- /dev/null +++ b/src/knowledge/knowledge_get_random_target.c @@ -0,0 +1,108 @@ +#include <stdlib.h> + +#include "../core/char.h" +#include "../core/index.h" +#include "../sequence/sequence.h" + +#include "../pipe/pipe.h" + +#include "knowledge.h" + +static int weighted_random_pick +( + const struct ZoO_knowledge_sequence_data sd [const restrict static 1], + ZoO_index result [const restrict static 1] +) +{ + ZoO_index accumulator, random_number; + + accumulator = 0; + + if (sd->occurrences == 0) + { + return -1; + } + + random_number = ZoO_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 ZoO_knowledge_random_tws_target +( + const struct ZoO_knowledge k [const static 1], + ZoO_index target [const restrict static 1], + const ZoO_index word_id, + const ZoO_index sequence_id +) +{ + ZoO_index s_index; + + if + ( + ZoO_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 ZoO_knowledge_random_swt_target +( + const struct ZoO_knowledge k [const static 1], + const ZoO_index sequence_id, + const ZoO_index word_id, + ZoO_index target [const restrict static 1] +) +{ + ZoO_index s_index; + + if + ( + ZoO_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 index 4258c4a..35cc123 100644 --- a/src/knowledge/knowledge_learn_markov_sequence.c +++ b/src/knowledge/knowledge_learn_markov_sequence.c @@ -244,7 +244,7 @@ static int add_sequence /** SEARCH EXISTING SEQUENCES *************************************************/ /******************************************************************************/ -static int find_sequence +int ZoO_knowledge_find_sequence ( const struct ZoO_knowledge k [const static 1], const ZoO_index sequence [const restrict static 1], @@ -332,7 +332,7 @@ int ZoO_knowledge_learn_markov_sequence if ( - find_sequence + ZoO_knowledge_find_sequence ( k, sequence, diff --git a/src/knowledge/knowledge_learn_sequence.c b/src/knowledge/knowledge_learn_sequence.c index 927b186..6a666bd 100644 --- a/src/knowledge/knowledge_learn_sequence.c +++ b/src/knowledge/knowledge_learn_sequence.c @@ -8,8 +8,6 @@ #include "knowledge.h" - - /******************************************************************************/ /** LEARN FOLLOWING SEQUENCE **************************************************/ /******************************************************************************/ @@ -47,6 +45,7 @@ static int add_swt_sequence const ZoO_index sequence [const restrict static 1], const size_t index, const size_t sequence_length, + const ZoO_index markov_order, ZoO_index buffer [const restrict static 1], const ZoO_index buffer_length, const struct ZoO_pipe io [const restrict static 1] @@ -134,6 +133,7 @@ static int add_tws_sequence const ZoO_index sequence [const restrict static 1], const size_t index, const size_t sequence_length, + const ZoO_index markov_order, ZoO_index buffer [const restrict static 1], const ZoO_index buffer_length, const struct ZoO_pipe io [const restrict static 1] @@ -220,12 +220,14 @@ int ZoO_knowledge_learn_sequence for (i = 0; i < sequence_length; ++i) { + /* TODO: handle failure. */ add_tws_sequence ( k, sequence, i, sequence_length, + markov_order, buffer, buffer_length, io @@ -237,6 +239,7 @@ int ZoO_knowledge_learn_sequence sequence, i, sequence_length, + markov_order, buffer, buffer_length, io diff --git a/src/knowledge/knowledge_learn_word.c b/src/knowledge/knowledge_learn_word.c index 5d932d2..8430bc0 100644 --- a/src/knowledge/knowledge_learn_word.c +++ b/src/knowledge/knowledge_learn_word.c @@ -15,13 +15,9 @@ static void initialize_sequence_collection struct ZoO_knowledge_sequence_collection c [const restrict static 1] ) { - c->sequences_ref = (ZoO_index *) NULL; + c->sequences_ref = (struct ZoO_knowledge_sequence_data *) NULL; c->sequences_ref_length = 0; c->sequences_ref_sorted = (ZoO_index *) NULL; - c->occurrences = (ZoO_index *) NULL; - c->targets = (ZoO_index **) NULL; - c->targets_length = (ZoO_index *) NULL; - c->targets_occurrences = (ZoO_index **) NULL; } static void initialize_word diff --git a/src/knowledge/knowledge_search.c b/src/knowledge/knowledge_search.c index 198da1d..cc1934e 100644 --- a/src/knowledge/knowledge_search.c +++ b/src/knowledge/knowledge_search.c @@ -73,106 +73,36 @@ int ZoO_knowledge_find_word_id } } -/* pre: \length(sequence) >= markov_order */ -int ZoO_knowledge_find_tws_targets +int ZoO_knowledge_find_markov_sequence ( - const struct ZoO_knowledge k [const static 1], - const ZoO_index sequence [restrict static 1], - const ZoO_index markov_order, /* Pre: (> 0) */ - const ZoO_index * restrict targets [const restrict static 1], - const ZoO_index * restrict targets_weights [const restrict static 1], - ZoO_index targets_weights_sum [const restrict static 1], - const struct ZoO_pipe io [const restrict static 1] + const ZoO_index sequence_id, + const struct ZoO_knowledge_sequence_collection sc [const restrict static 1], + ZoO_index result [const restrict static 1] ) { /* This is a binary search */ int cmp; - ZoO_index i, current_min, current_max, local_sequence; - const ZoO_index * restrict candidate; - const ZoO_index markov_sequence_length = (markov_order - 1); - const ZoO_index word = sequence[0]; - - if - ( - (word >= k->words_length) - || (k->words[word].occurrences == 0) - ) - { - ZoO_S_ERROR - ( - io, - "Attempting to find the TWS targets of an unknown word." - ); - - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; - - return -1; - } - - - if (markov_order == 1) - { - /* Special case: empty sequences. */ - *targets = (const ZoO_index *) k->words[word].tws.targets; - - *targets_weights = - (const ZoO_index *) k->words[word].tws.targets_occurrences; - - *targets_weights_sum = k->words[word].occurrences; - - return 0; - } - - - /* pre: \length(sequence) >= markov_order */ - /* markov_order > 1 */ - sequence += 1; /* get the relevant part of the sequence. */ - - /* Handles the case where the list is empty ********************************/ - current_max = k->words[word].tws.sequences_ref_length; + ZoO_index i, current_min, current_max; - if (current_max == 0) + if (sc->sequences_ref_length == 0) { - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; - - ZoO_S_ERROR - ( - io, - "Attempting to find the TWS targets of a sequence that never had any." - ); + *result = 0; - return -2; + return -1; } - /***************************************************************************/ current_min = 0; - current_max -= 1; + current_max = (sc->sequences_ref_length - 1); for (;;) { i = (current_min + ((current_max - current_min) / 2)); - local_sequence = k->words[word].tws.sequences_ref_sorted[i]; - - (void) ZoO_knowledge_get_sequence - ( - k, - k->words[word].tws.sequences_ref[local_sequence], - &candidate, - io - ); - cmp = - ZoO_sequence_cmp + ZoO_index_cmp ( - sequence, - markov_sequence_length, - candidate, - markov_sequence_length + sequence_id, + sc->sequences_ref[sc->sequences_ref_sorted[i]].id ); if (cmp > 0) @@ -181,137 +111,57 @@ int ZoO_knowledge_find_tws_targets if (current_min > current_max) { - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; + *result = current_min; - return -2; + return -1; } } else if (cmp < 0) { if ((current_min > current_max) || (i == 0)) { - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; + *result = current_min; - return -2; + return -1; } current_max = (i - 1); } else { - *targets = k->words[word].tws.targets[local_sequence]; - - *targets_weights = - k->words[word].tws.targets_occurrences[local_sequence]; - - *targets_weights_sum = - k->words[word].tws.occurrences[local_sequence]; + *result = sc->sequences_ref_sorted[i]; return 0; } } } -int ZoO_knowledge_find_swt_targets +int ZoO_knowledge_find_sequence_target ( - const struct ZoO_knowledge k [const static 1], - const ZoO_index sequence [restrict static 1], - const size_t sequence_length, - const ZoO_index markov_order, - const ZoO_index * restrict targets [const restrict static 1], - const ZoO_index * restrict targets_weights [const restrict static 1], - ZoO_index targets_weights_sum [const restrict static 1], - const struct ZoO_pipe io [const restrict static 1] + const ZoO_index target_id, + const struct ZoO_knowledge_sequence_data sd [const restrict static 1], + ZoO_index result [const restrict static 1] ) { /* This is a binary search */ int cmp; - ZoO_index i, current_min, current_max, local_sequence; - const ZoO_index * restrict candidate; - const ZoO_index markov_sequence_length = (markov_order - 1); - const ZoO_index word = sequence[sequence_length - 1]; - - if - ( - (word >= k->words_length) - || (k->words[word].occurrences == 0) - ) - { - ZoO_S_ERROR - ( - io, - "Attempting to find the SWT targets of an unknown word." - ); - - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; - - return -1; - } - - if (markov_order == 1) - { - /* Special case: empty sequences. */ - *targets = (const ZoO_index *) k->words[word].swt.targets; - - *targets_weights = - (const ZoO_index *) k->words[word].swt.targets_occurrences; - - *targets_weights_sum = k->words[word].occurrences; - - return 0; - } - - sequence = (sequence + (sequence_length - markov_order)); - /* Handles the case where the list is empty ********************************/ - current_max = k->words[word].swt.sequences_ref_length; + ZoO_index i, current_min, current_max; - if (current_max == 0) + if (sd->targets_length == 0) { - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; - - ZoO_S_WARNING - ( - io, - "Attempting to find the SWT targets of a sequence that never had any." - ); + *result = 0; - return -2; + return -1; } - /***************************************************************************/ current_min = 0; - current_max -= 1; + current_max = (sd->targets_length - 1); for (;;) { i = (current_min + ((current_max - current_min) / 2)); - local_sequence = k->words[word].swt.sequences_ref_sorted[i]; - - (void) ZoO_knowledge_get_sequence - ( - k, - k->words[word].swt.sequences_ref[local_sequence], - &candidate, - io - ); - - cmp = - ZoO_sequence_cmp - ( - sequence, - markov_sequence_length, - candidate, - markov_sequence_length - ); + cmp = ZoO_index_cmp(target_id, sd->targets[i].id); if (cmp > 0) { @@ -319,35 +169,25 @@ int ZoO_knowledge_find_swt_targets if (current_min > current_max) { - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; + *result = current_min; - return -2; + return -1; } } else if (cmp < 0) { if ((current_min > current_max) || (i == 0)) { - *targets = (const ZoO_index *) NULL; - *targets_weights = (const ZoO_index *) NULL; - *targets_weights_sum = 0; + *result = current_min; - return -2; + return -1; } current_max = (i - 1); } else { - *targets = k->words[word].swt.targets[local_sequence]; - - *targets_weights = - k->words[word].swt.targets_occurrences[local_sequence]; - - *targets_weights_sum = - k->words[word].swt.occurrences[local_sequence]; + *result = i; return 0; } diff --git a/src/knowledge/knowledge_swt_tws_modifications.c b/src/knowledge/knowledge_swt_tws_modifications.c index 87305f2..40e2e3b 100644 --- a/src/knowledge/knowledge_swt_tws_modifications.c +++ b/src/knowledge/knowledge_swt_tws_modifications.c @@ -1,5 +1,157 @@ +#include <stdlib.h> + +#include "../core/index.h" + +#include "../pipe/pipe.h" + #include "knowledge.h" +static int add_target +( + struct ZoO_knowledge_sequence_data sd [const restrict static 1], + const ZoO_index target_id, + const ZoO_index s_index, + const ZoO_index t_index, + const struct ZoO_pipe io [const restrict static 1] +) +{ + struct ZoO_knowledge_target * new_p; + + /* (sd->targets_length == ZoO_INDEX_MAX) => target_id \in sd->targets. */ + + sd->targets_length += 1; + + new_p = + (struct ZoO_knowledge_target *) realloc + ( + (void *) sd->targets, + (sd->targets_length * sizeof(struct ZoO_knowledge_target)) + ); + + if (new_p == (struct ZoO_knowledge_target *) NULL) + { + ZoO_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 ZoO_knowledge_target) + ) + ); + } + + sd->targets[t_index].id = target_id; + sd->targets[t_index].occurrences = 0; + + return 0; +} + +static int add_sequence +( + struct ZoO_knowledge_sequence_collection sc [const restrict static 1], + const ZoO_index sequence_id, + ZoO_index s_index [const restrict static 1], + const struct ZoO_pipe io [const restrict static 1] +) +{ + struct ZoO_knowledge_sequence_data * new_p; + ZoO_index * new_ps; + + /* + * (sc->sequences_ref_length == ZoO_INDEX_MAX) => + * sequence_id \in sc->sequences_ref. + */ + + sc->sequences_ref_length += 1; + + new_p = + (struct ZoO_knowledge_sequence_data *) realloc + ( + (void *) sc->sequences_ref, + (sc->sequences_ref_length * sizeof(struct ZoO_knowledge_sequence_data)) + ); + + if (new_p == (struct ZoO_knowledge_sequence_data *) NULL) + { + ZoO_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 = + (ZoO_index *) realloc + ( + (void *) sc->sequences_ref_sorted, + (sc->sequences_ref_length * sizeof(ZoO_index)) + ); + + if (new_p == (struct ZoO_knowledge_sequence_data *) NULL) + { + ZoO_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(ZoO_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 ZoO_knowledge_target *) NULL; + sc->sequences_ref[*s_index].targets_length = 0; + + return -1; +} + int ZoO_knowledge_strengthen_swt ( struct ZoO_knowledge k [const restrict static 1], @@ -9,9 +161,85 @@ int ZoO_knowledge_strengthen_swt const struct ZoO_pipe io [const restrict static 1] ) { - /* TODO */ + ZoO_index s_index, t_index; - return -1; + if + ( + ZoO_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 + ( + ZoO_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 + == ZoO_INDEX_MAX + ) + || + ( + k->words[word_id].swt.sequences_ref[s_index].targets[t_index].occurrences + == ZoO_INDEX_MAX + ) + ) + { + ZoO_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 ZoO_knowledge_strengthen_tws @@ -23,7 +251,84 @@ int ZoO_knowledge_strengthen_tws const struct ZoO_pipe io [const restrict static 1] ) { - /* TODO */ + ZoO_index s_index, t_index; + + if + ( + ZoO_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 + ( + ZoO_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 + == ZoO_INDEX_MAX + ) + || + ( + k->words[word_id].tws.sequences_ref[s_index].targets[t_index].occurrences + == ZoO_INDEX_MAX + ) + ) + { + ZoO_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 -1; } diff --git a/src/knowledge/knowledge_types.h b/src/knowledge/knowledge_types.h index 9db77bd..53330ce 100644 --- a/src/knowledge/knowledge_types.h +++ b/src/knowledge/knowledge_types.h @@ -1,20 +1,32 @@ #ifndef _ZoO_KNOWLEDGE_KNOWLEDGE_TYPES_H_ #define _ZoO_KNOWLEDGE_KNOWLEDGE_TYPES_H_ -#include <pthread.h> +#ifndef ZoO_RUNNING_FRAMA_C + #include <pthread.h> +#endif #include "../core/index_types.h" #include "../core/char_types.h" +struct ZoO_knowledge_target +{ + ZoO_index id; + ZoO_index occurrences; +}; + +struct ZoO_knowledge_sequence_data +{ + ZoO_index id; + ZoO_index occurrences; + struct ZoO_knowledge_target * targets; + ZoO_index targets_length; +}; + struct ZoO_knowledge_sequence_collection { - ZoO_index * sequences_ref; + struct ZoO_knowledge_sequence_data * sequences_ref; ZoO_index sequences_ref_length; ZoO_index * sequences_ref_sorted; - ZoO_index * occurrences; - ZoO_index ** targets; - ZoO_index * targets_length; - ZoO_index ** targets_occurrences; }; struct ZoO_knowledge_word @@ -38,7 +50,9 @@ struct ZoO_knowledge ZoO_index ** sequences; ZoO_index sequences_length; ZoO_index * sequences_sorted; +#ifndef ZoO_RUNNING_FRAMA_C pthread_mutex_t mutex; +#endif }; #endif @@ -1,6 +1,6 @@ #include <stdio.h> -#include "cli/parameters.h" +#include "parameters/parameters.h" #include "server/server.h" @@ -30,11 +30,8 @@ int main (int const argc, const char * argv [const static argc]) switch (ZoO_parameters_initialize(¶ms, argc, argv)) { - case ZoO_CLEANS_UP: - return ZoO_server_cleanup_session(params.session); - case ZoO_RUNS: - return ZoO_server_main(params); + return ZoO_server_main(¶ms); default: case ZoO_PRINTS_HELP: diff --git a/src/parameters/parameters_types.h b/src/parameters/parameters_types.h index f9ca88b..f3bd65d 100644 --- a/src/parameters/parameters_types.h +++ b/src/parameters/parameters_types.h @@ -1,6 +1,8 @@ #ifndef _ZoO_CLI_PARAMETERS_TYPES_H_ #define _ZoO_CLI_PARAMETERS_TYPES_H_ +#include "../core/index_types.h" + enum ZoO_invocation_objective { ZoO_PRINTS_HELP, diff --git a/src/pervasive.h b/src/pervasive.h index 7359a3d..6677c7e 100644 --- a/src/pervasive.h +++ b/src/pervasive.h @@ -6,7 +6,7 @@ #define ZoO_SERVER_VERSION 1 #define ZoO_PROTOCOL_VERSION 1 -#define ZoO_RUNNING_FRAMA_C 1 +//#define ZoO_RUNNING_FRAMA_C 1 #define ZoO_DEBUG_ALL 1 diff --git a/src/pipe/CMakeLists.txt b/src/pipe/CMakeLists.txt index 03456ed..fa07534 100644 --- a/src/pipe/CMakeLists.txt +++ b/src/pipe/CMakeLists.txt @@ -1,6 +1,6 @@ set( SRC_FILES ${SRC_FILES} - ${CMAKE_CURRENT_SOURCE_DIR}/pipe.c ) + set(SRC_FILES ${SRC_FILES} PARENT_SCOPE) diff --git a/src/sequence/sequence.c b/src/sequence/sequence.c index 852b05c..f3c3b46 100644 --- a/src/sequence/sequence.c +++ b/src/sequence/sequence.c @@ -75,13 +75,13 @@ static void bypass_redundant_sos /* See "sequence.h" */ /*@ - \requires + requires ( \valid(sequence_a+ (0 .. sequence_a_length)) || (sequence_a_length == 0) ); - \requires + requires ( \valid(sequence_b+ (0 .. sequence_b_length)) || (sequence_b_length == 0) diff --git a/src/sequence/sequence.h b/src/sequence/sequence.h index d9cbf86..129c457 100644 --- a/src/sequence/sequence.h +++ b/src/sequence/sequence.h @@ -125,13 +125,14 @@ int ZoO_sequence_create_from requires \valid(io); requires (((*sequence_length) * sizeof(ZoO_index)) <= SIZE_MAX); requires (((*sequence_capacity) * sizeof(ZoO_index)) <= SIZE_MAX); - requires \separated(sequence, sequence, sequence_capacity, sequence_length, io); + requires \separated(sequence, *sequence, sequence_capacity, sequence_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); @@ -188,13 +189,14 @@ int ZoO_sequence_append_left requires \valid(io); requires (((*sequence_length) * sizeof(ZoO_index)) <= SIZE_MAX); requires (((*sequence_capacity) * sizeof(ZoO_index)) <= SIZE_MAX); - requires \separated(sequence, sequence, sequence_capacity, sequence_length, io); + requires \separated(sequence, *sequence, sequence_capacity, sequence_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); diff --git a/src/sequence/sequence_append.c b/src/sequence/sequence_append.c index 7eaa22b..604d251 100644 --- a/src/sequence/sequence_append.c +++ b/src/sequence/sequence_append.c @@ -224,8 +224,9 @@ int ZoO_sequence_append_right return -1; } - /* assert (*sequence_length >= 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 index 429b58c..1f20262 100644 --- a/src/sequence/sequence_creation.c +++ b/src/sequence/sequence_creation.c @@ -11,41 +11,6 @@ #include "sequence.h" -/* - * Returns a randomly chosen index pointing to a element in {weights}. - * The values of {weights} are used as weights to guide the choice. - * Returns: - * Value in [0, (length weights)[. - * Pre: - * (> weights_sum 0). - * (= (sum weights) weights_sum). - */ -/*@ - @ requires (weights_sum > 0); - @ requires \valid(weights); - @ requires (\sum(0, (\length(weights) - 1), weights) = weights_sum); -@*/ -static ZoO_index weighted_random_pick -( - const ZoO_index weights [const restrict static 1], - const ZoO_index weights_sum -) -{ - ZoO_index result, accumulator, random_number; - - accumulator = 0; - - random_number = ZoO_index_random_up_to(weights_sum); - /*@ ensures (0 <= random_number <= weights_sum); @*/ - - for (result = 0; accumulator < random_number; ++result) - { - /*@ requires (\sum(0, (\length(weights) - 1), weights) = weights_sum); @*/ - accumulator += weights[result]; - } - - return result; -} /******************************************************************************/ /** ADDING ELEMENTS TO THE LEFT ***********************************************/ @@ -78,42 +43,58 @@ static int extend_left const struct ZoO_pipe io [const restrict static 1] ) { - const ZoO_index * restrict preceding_words; - const ZoO_index * restrict preceding_words_weights; - ZoO_index preceding_words_weights_sum; + ZoO_index sequence_id, word_id; (void) ZoO_knowledge_lock_access(k, io); + /* preceding_words_weights_sum > 0 */ + if ( - ZoO_knowledge_find_tws_targets + ZoO_knowledge_find_sequence ( k, - *sequence, + ((*sequence) + 1), markov_order, - &preceding_words, - &preceding_words_weights, - &preceding_words_weights_sum, - io + &sequence_id ) < 0 ) { (void) ZoO_knowledge_unlock_access(k, io); + /* TODO: Err message. */ return -1; } - /* preceding_words_weights_sum > 0 */ + (void) ZoO_knowledge_unlock_access(k, io); + + (void) ZoO_knowledge_lock_access(k, io); + + if + ( + ZoO_knowledge_random_tws_target + ( + k, + &word_id, + (*sequence)[0], + sequence_id + ) < 0 + ) + { + (void) ZoO_knowledge_unlock_access(k, io); + + /* TODO: Err message. */ + + return -1; + } + + (void) ZoO_knowledge_unlock_access(k, io); if ( ZoO_sequence_append_left ( - weighted_random_pick - ( - preceding_words_weights, - preceding_words_weights_sum - ), + word_id, sequence, sequence_capacity, sequence_length, @@ -121,13 +102,9 @@ static int extend_left ) < 0 ) { - (void) ZoO_knowledge_unlock_access(k, io); - return -3; } - (void) ZoO_knowledge_unlock_access(k, io); - return 0; } @@ -263,33 +240,54 @@ static int extend_right const struct ZoO_pipe io [const restrict static 1] ) { - const ZoO_index * restrict following_words; - const ZoO_index * restrict following_words_weights; - - ZoO_index following_words_weights_sum; + ZoO_index sequence_id, word_id; (void) ZoO_knowledge_lock_access(k, io); + /* preceding_words_weights_sum > 0 */ + if ( - ZoO_knowledge_find_swt_targets + ZoO_knowledge_find_sequence ( k, - *sequence, - *sequence_length, + ((*sequence) + (*sequence_length - markov_order)), markov_order, - &following_words, - &following_words_weights, - &following_words_weights_sum, - io + &sequence_id ) < 0 ) { (void) ZoO_knowledge_unlock_access(k, io); + /* TODO: Err message. */ return -1; } + (void) ZoO_knowledge_unlock_access(k, io); + + (void) ZoO_knowledge_lock_access(k, io); + + if + ( + ZoO_knowledge_random_swt_target + ( + k, + sequence_id, + (*sequence)[*sequence_length - 1], + &word_id + ) < 0 + ) + { + (void) ZoO_knowledge_unlock_access(k, io); + + /* TODO: Err message. */ + + return -1; + } + + (void) ZoO_knowledge_unlock_access(k, io); + + /* following_words_weights_sum > 0 */ if @@ -297,11 +295,7 @@ static int extend_right ZoO_sequence_append_right ( sequence, - weighted_random_pick - ( - following_words_weights, - following_words_weights_sum - ), + word_id, sequence_capacity, sequence_length, io @@ -447,11 +441,6 @@ static int initialize_sequence const struct ZoO_pipe io [const restrict static 1] ) { - const ZoO_index * restrict swt_sequences_ref; - const ZoO_index * restrict chosen_sequence; - const ZoO_index * restrict swt_sequences_weights; - ZoO_index swt_sequences_weights_sum; - sequence[(markov_order - 1)] = initial_word; if (markov_order == 1) @@ -463,52 +452,21 @@ static int initialize_sequence if ( - ZoO_knowledge_get_swt_sequences_ref + ZoO_knowledge_copy_random_swt_sequence ( k, + sequence, initial_word, - &swt_sequences_ref, - &swt_sequences_weights, - &swt_sequences_weights_sum, + markov_order, io ) < 0 ) { (void) ZoO_knowledge_unlock_access(k, io); - ZoO_S_ERROR - ( - io, - "Unable to find any sequence that would precede the initial word." - ); - return -1; } - /* following_sequences_ref contains only valid references. */ - (void) ZoO_knowledge_get_sequence - ( - k, - swt_sequences_ref - [ - weighted_random_pick - ( - swt_sequences_weights, - swt_sequences_weights_sum - ) - ], - &chosen_sequence, - io - ); - - /* Safe if 'allocate_initial_sequence' succeeded. */ - memcpy - ( - (void *) sequence, - (const void *) chosen_sequence, - ((((size_t) markov_order) - 1) * sizeof(ZoO_index)) - ); - (void) ZoO_knowledge_unlock_access(k, io); return 0; diff --git a/src/sequence/sequence_from_string.c b/src/sequence/sequence_from_string.c index cd04d70..6acfdc2 100644 --- a/src/sequence/sequence_from_string.c +++ b/src/sequence/sequence_from_string.c @@ -16,10 +16,6 @@ /** HANDLING WORDS ************************************************************/ /******************************************************************************/ -/* - * Semaphore: - * Takes then releases access for {k}. - */ static int add_word_to_sequence ( const ZoO_char string [const restrict static 1], diff --git a/src/server/CMakeLists.txt b/src/server/CMakeLists.txt index b3f0c15..ca476fb 100644 --- a/src/server/CMakeLists.txt +++ b/src/server/CMakeLists.txt @@ -6,7 +6,7 @@ set( ${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_signals.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 diff --git a/src/server/server_types.h b/src/server/server_types.h index 99959f5..fb78b77 100644 --- a/src/server/server_types.h +++ b/src/server/server_types.h @@ -3,7 +3,9 @@ #include <sys/time.h> -#include <pthread.h> +#ifndef ZoO_RUNNING_FRAMA_C + #include <pthread.h> +#endif #include "../core/index.h" @@ -24,7 +26,9 @@ enum ZoO_server_thread_state struct ZoO_server_thread_data { +#ifndef ZoO_RUNNING_FRAMA_C pthread_t posix_id; +#endif enum ZoO_server_thread_state state; }; @@ -32,8 +36,10 @@ struct ZoO_server_thread_collection { struct ZoO_server_thread_data * threads; size_t threads_capacity; +#ifndef ZoO_RUNNING_FRAMA_C pthread_mutex_t mutex; pthread_barrier_t barrier; +#endif ZoO_index currently_running; }; |