contrib/gperf/src/keyword.cc

   1 /* Keyword data.
   2    Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
   3    Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
   4    and Bruno Haible <bruno@clisp.org>.
   5
   6    This file is part of GNU GPERF.
   7
   8    GNU GPERF is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    GNU GPERF is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; see the file COPYING.
  20    If not, write to the Free Software Foundation, Inc.,
  21    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  22
  23 /* Specification. */
  24 #include "keyword.h"
  25
  26 #include <stddef.h>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include "positions.h"
  30
  31
  32 /* --------------------------- KeywordExt class --------------------------- */
  33
  34 /* Sort a small set of 'unsigned int', base[0..len-1], in place.  */
  35 static inline void sort_char_set (unsigned int *base, int len)
  36 {
  37   /* Bubble sort is sufficient here.  */
  38   for (int i = 1; i < len; i++)
  39     {
  40       int j;
  41       unsigned int tmp;
  42
  43       for (j = i, tmp = base[j]; j > 0 && tmp < base[j - 1]; j--)
  44         base[j] = base[j - 1];
  45
  46       base[j] = tmp;
  47     }
  48 }
  49
  50 /* Initializes selchars and selchars_length.
  51
  52    General idea:
  53      The hash function will be computed as
  54          asso_values[allchars[key_pos[0]]] +
  55          asso_values[allchars[key_pos[1]]] + ...
  56      We compute selchars as the multiset
  57          { allchars[key_pos[0]], allchars[key_pos[1]], ... }
  58      so that the hash function becomes
  59          asso_values[selchars[0]] + asso_values[selchars[1]] + ...
  60    Furthermore we sort the selchars array, to ease detection of duplicates
  61    later.
  62
  63    More in detail: The arguments alpha_unify (used for case-insensitive
  64    hash functions) and alpha_inc (used to disambiguate permutations)
  65    apply slight modifications. The hash function will be computed as
  66        sum (j=0,1,...: k = key_pos[j]:
  67             asso_values[alpha_unify[allchars[k]+alpha_inc[k]]])
  68        + (allchars_length if !option[NOLENGTH], 0 otherwise).
  69    We compute selchars as the multiset
  70        { alpha_unify[allchars[k]+alpha_inc[k]] : j=0,1,..., k = key_pos[j] }
  71    so that the hash function becomes
  72        asso_values[selchars[0]] + asso_values[selchars[1]] + ...
  73        + (allchars_length if !option[NOLENGTH], 0 otherwise).
  74  */
  75
  76 unsigned int *
  77 KeywordExt::init_selchars_low (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc)
  78 {
  79   /* Iterate through the list of positions, initializing selchars
  80      (via ptr).  */
  81   PositionIterator iter = positions.iterator(_allchars_length);
  82
  83   unsigned int *key_set = new unsigned int[iter.remaining()];
  84   unsigned int *ptr = key_set;
  85
  86   for (int i; (i = iter.next ()) != PositionIterator::EOS; )
  87     {
  88       unsigned int c;
  89       if (i == Positions::LASTCHAR)
  90         /* Special notation for last KEY position, i.e. '$'.  */
  91         c = static_cast<unsigned char>(_allchars[_allchars_length - 1]);
  92       else if (i < _allchars_length)
  93         {
  94           /* Within range of KEY length, so we'll keep it.  */
  95           c = static_cast<unsigned char>(_allchars[i]);
  96           if (alpha_inc)
  97             c += alpha_inc[i];
  98         }
  99       else
 100         /* Out of range of KEY length, the iterator should not have
 101            produced this.  */
 102         abort ();
 103       if (alpha_unify)
 104         c = alpha_unify[c];
 105       *ptr = c;
 106       ptr++;
 107     }
 108
 109   _selchars = key_set;
 110   _selchars_length = ptr - key_set;
 111
 112   return key_set;
 113 }
 114
 115 void
 116 KeywordExt::init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify)
 117 {
 118   init_selchars_low (positions, alpha_unify, NULL);
 119 }
 120
 121 void
 122 KeywordExt::init_selchars_multiset (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc)
 123 {
 124   unsigned int *selchars =
 125     init_selchars_low (positions, alpha_unify, alpha_inc);
 126
 127   /* Sort the selchars elements alphabetically.  */
 128   sort_char_set (selchars, _selchars_length);
 129 }
 130
 131 /* Deletes selchars.  */
 132 void
 133 KeywordExt::delete_selchars ()
 134 {
 135   delete[] const_cast<unsigned int *>(_selchars);
 136 }
 137
 138
 139 /* ------------------------- Keyword_Factory class ------------------------- */
 140
 141 Keyword_Factory::Keyword_Factory ()
 142 {
 143 }
 144
 145 Keyword_Factory::~Keyword_Factory ()
 146 {
 147 }
 148
 149
 150 /* ------------------------------------------------------------------------- */
 151
 152 char empty_string[1] = "";
 153
 154
 155 #ifndef __OPTIMIZE__
 156
 157 #define INLINE /* not inline */
 158 #include "keyword.icc"
 159 #undef INLINE
 160
 161 #endif /* not defined __OPTIMIZE__ */