Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / 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