search.h

   1 #ifndef CGPERF_SEARCH_H
   2 #define CGPERF_SEARCH_H
   3 #include <stdbool.h>
   4 #include "c_fixing.h"
   5 #include "keyword_list.h"
   6 #include "positions.h"
   7 #include "bool-array.h"
   8 /*------------------------------------------------------------------------------------------------*/
   9 #include "namespace/search.h"
  10 #include "namespace/keyword.h"
  11 #include "namespace/keyword_list.h"
  12 #include "namespace/positions.h"
  13 #include "namespace/bool-array.h"
  14 /* for the Search local types */
  15 #include "namespace/search.c"
  16 /*---------------------------i--------------------------------------------------------------------*/
  17 /*{{{ types */
  18 struct Search {
  19 /*{{{ public */
  20         struct Keyword_List *head;
  21         /* total number of keywords, counting duplicates */
  22         s32 total_keys;
  23         /* maximum length of the longest keyword */
  24         s32 max_key_len;
  25         /* minimum length of the shortest keyword */
  26         s32 min_key_len;
  27         /* whether the hash function includes the length */
  28         bool hash_includes_len;
  29         /* user-specified or computed key positions */
  30         struct Positions *key_positions;
  31         /* adjustments to add to bytes add specific key positions */
  32         u32 *alpha_inc;
  33         /* size of alphabet */
  34         u32 alpha_size;
  35         /*
  36          * alphabet character unification, either the identity or a mapping from upper case
  37          * characters to lower case characters (and maybe more)
  38          */
  39         u32 *alpha_unify;
  40         /* maximum _selchars_length over all keywords */
  41         u32 max_selchars_length;
  42         /*
  43          * total number of duplicates that have been moved to _duplicate_link lists (not counting
  44          * their representatives which stay on the main list)
  45          */
  46         s32 total_duplicates;
  47         /*
  48          * Counts occurrences of each key set character.  occurrences[c] is the number of times that
  49          * c occurs among the _selchars of a keyword.
  50          */
  51         s32 *occurrences;
  52         /* value associated with each character */
  53         s32 *asso_values;
  54 /*}}} public -- END */
  55 /*{{{ private */
  56         /* maximal possible hash value */
  57         s32 max_hash_value;
  58         /* exclusive upper bound for every _asso_values[c]. A power of 2. */
  59         u32 asso_value_max;
  60         /* Initial value for asso_values table. -1 means random. */
  61         s32 initial_asso_value;
  62         /* Jump length when trying alternative values. 0 means random. */
  63         s32 jump;
  64         /* Length of _head list. Number of keywords, not counting duplicates. */
  65         s32 list_len;
  66         /* sparse bit vector for collision detection */
  67         struct Bool_Array *collision_detector;
  68 /*}}} private -- END */
  69 };
  70 /*}}} types -- END */
  71 /*{{{ public static methods */
  72 static struct Search *schr_new(struct Keyword_List *list);
  73 static void schr_del(struct Search *t);
  74 static void schr_optimize(struct Search *t);
  75 /*}}} public static methods -- END */
  76 /*{{{ private static methods */
  77 static void schr_prepare(struct Search *t);
  78 static void schr_find_good_asso_values(struct Search *t);
  79 static u32 schr_count_duplicates_tuple(struct Search *t);
  80 static u32 schr_count_duplicates_tuple_do(struct Search *t, struct Positions *positions,
  81                                                                                 u32 *alpha_unify);
  82 static void schr_find_positions(struct Search *t);
  83 static void schr_find_alpha_inc(struct Search *t);
  84 static u32 *schr_compute_alpha_unify(struct Search *t);
  85 static u32 *schr_compute_alpha_unify_with_inc(struct Search *t, struct Positions *positions,
  86                                                                                 u32 *alpha_inc);
  87 static u32 schr_compute_alpha_size(void);
  88 static u32 schr_compute_alpha_size_with_inc(struct Search *t, u32 *alpha_inc);
  89 static void schr_init_selchars_tuple(struct Search *t, struct Positions *positions,
  90                                                                                 u32 *alpha_unify);
  91 static void schr_delete_selchars(struct Search *t);
  92 static u32 schr_count_duplicates_multiset(struct Search *t, u32 *alpha_inc);
  93 static void schr_init_selchars_multiset(struct Search *t, struct Positions *positions,
  94                                                                 u32 *alpha_unify, u32 *alpha_inc);
  95 static void schr_prepare_asso_values(struct Search *t);
  96 static void schr_find_asso_values(struct Search *t);
  97 struct EquivalenceClass;
  98 static struct EquivalenceClass *schr_compute_partition(struct Search *t, bool *undetermined);
  99 static u32 schr_count_possible_collisions(struct Search *t, struct EquivalenceClass *partition,
 100                                                                                         u32 c);
 101 static bool schr_unchanged_partition(struct Search *t, struct EquivalenceClass *partition, u32 c);
 102 static s32 schr_compute_hash(struct Search *t, struct Keyword *kw);
 103 static void schr_sort(struct Search *t);
 104 /*}}} private static methods -- END */
 105 /*------------------------------------------------------------------------------------------------*/
 106 #define EPILOG
 107 #include "namespace/search.h"
 108 #include "namespace/keyword.h"
 109 #include "namespace/keyword_list.h"
 110 #include "namespace/positions.h"
 111 #include "namespace/bool-array.h"
 112 /* for the Search local types */
 113 #include "namespace/search.c"
 114 #undef EPILOG
 115 /*------------------------------------------------------------------------------------------------*/
 116 #endif