nucleus/library/structures/string_hasher.cpp

   1 /*****************************************************************************\
   2 *                                                                             *
   3 *  Name   : string_hasher                                                     *
   4 *  Author : Chris Koeritz                                                     *
   5 *                                                                             *
   6 *******************************************************************************
   7 * Copyright (c) 2001-$now By Author.  This program is free software; you can  *
   8 * redistribute it and/or modify it under the terms of the GNU General Public  *
   9 * License as published by the Free Software Foundation; either version 2 of   *
  10 * the License or (at your option) any later version.  This is online at:      *
  11 *     http://www.fsf.org/copyleft/gpl.html                                    *
  12 * Please send any updates to: fred@gruntose.com                               *
  13 \*****************************************************************************/
  14
  15 #include "string_hasher.h"
  16
  17 #include <basis/functions.h>
  18 #include <basis/astring.h>
  19
  20 using namespace basis;
  21
  22 namespace structures {
  23
  24 const int MAX_STRING_CHARS_USED = 3;
  25   // we use this many characters from the string in question (if they
  26   // exist) at each end of the string.
  27
  28 //////////////
  29
  30 hashing_algorithm *string_hasher::clone() const
  31 { return new string_hasher; }
  32
  33 basis::un_int string_hasher::hash(const void *key_data, int key_length_in) const
  34 {
  35   if (!key_data) return 0;  // error!
  36   if (key_length_in <= 1) return 0;  // ditto!
  37
  38   abyte *our_key = (abyte *)key_data;
  39   abyte hashed[4] = { 0, 0, 0, 0 };
  40
  41   int key_length = minimum(key_length_in - 1, MAX_STRING_CHARS_USED);
  42
  43   int fill_posn = 0;
  44   // add the characters from the beginning of the string.
  45   for (int i = 0; i < key_length; i++) {
  46     // add to the primary area.
  47     hashed[fill_posn] = hashed[fill_posn] + our_key[i];
  48     fill_posn++;
  49     if (fill_posn >= 4) fill_posn = 0;
  50     // add to the secondary area (the next in rotation after primary).
  51     hashed[fill_posn] = hashed[fill_posn] + (our_key[i] / 4);
  52   }
  53   // add the characters from the end of the string.
  54   for (int k = key_length_in - 2;
  55       (k >= 0) && (k >= key_length_in - 1 - key_length); k--) {
  56     // add to the primary area.
  57     hashed[fill_posn] = hashed[fill_posn] + our_key[k];
  58     fill_posn++;
  59     if (fill_posn >= 4) fill_posn = 0;
  60     // add to the secondary area (the next in rotation after primary).
  61     hashed[fill_posn] = hashed[fill_posn] + (our_key[k] / 4);
  62   }
  63
  64   basis::un_int to_return = 0;
  65   for (int j = 0; j < 4; j++) to_return = (to_return << 8) + hashed[j];
  66   return to_return;
  67 }
  68
  69 //////////////
  70
  71 hashing_algorithm *astring_hasher::clone() const
  72 { return new astring_hasher; }
  73
  74 basis::un_int astring_hasher::hash(const void *key_data, int key_length_in) const
  75 {
  76   if (!key_data) return 0;  // error.
  77   const astring *real_key = (const astring *)key_data;
  78   if (real_key->length() + 1 != key_length_in) {
  79 //    printf("differing key lengths, string len=%d, key len=%d\n",
  80 //        real_key->length() + 1, key_length_in);
  81   }
  82   return string_hasher().hash((const void *)real_key->observe(),
  83       real_key->length() + 1);
  84 }
  85
  86 } //namespace.
  87