1 /** @file
2 
3   @section license License
4 
5   Licensed to the Apache Software Foundation (ASF) under one
6   or more contributor license agreements.  See the NOTICE file
7   distributed with this work for additional information
8   regarding copyright ownership.  The ASF licenses this file
9   to you under the Apache License, Version 2.0 (the
10   "License"); you may not use this file except in compliance
11   with the License.  You may obtain a copy of the License at
12 
13       http://www.apache.org/licenses/LICENSE-2.0
14 
15   Unless required by applicable law or agreed to in writing, software
16   distributed under the License is distributed on an "AS IS" BASIS,
17   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18   See the License for the specific language governing permissions and
19   limitations under the License.
20  */
21 
22 #include "tscore/ConsistentHash.h"
23 #include <cstring>
24 #include <string>
25 #include <sstream>
26 #include <cmath>
27 #include <climits>
28 #include <cstdio>
29 
30 std::ostream &
operator <<(std::ostream & os,ATSConsistentHashNode & thing)31 operator<<(std::ostream &os, ATSConsistentHashNode &thing)
32 {
33   return os << thing.name;
34 }
35 
ATSConsistentHash(int r,ATSHash64 * h)36 ATSConsistentHash::ATSConsistentHash(int r, ATSHash64 *h) : replicas(r), hash(h) {}
37 
38 void
insert(ATSConsistentHashNode * node,float weight,ATSHash64 * h)39 ATSConsistentHash::insert(ATSConsistentHashNode *node, float weight, ATSHash64 *h)
40 {
41   int i;
42   char numstr[256];
43   ATSHash64 *thash;
44   std::ostringstream string_stream;
45   std::string std_string;
46 
47   if (h) {
48     thash = h;
49   } else if (hash) {
50     thash = hash;
51   } else {
52     return;
53   }
54 
55   string_stream << *node;
56   std_string = string_stream.str();
57 
58   for (i = 0; i < static_cast<int>(roundf(replicas * weight)); i++) {
59     snprintf(numstr, 256, "%d-", i);
60     thash->update(numstr, strlen(numstr));
61     thash->update(std_string.c_str(), strlen(std_string.c_str()));
62     thash->final();
63     NodeMap.insert(std::pair<uint64_t, ATSConsistentHashNode *>(thash->get(), node));
64     thash->clear();
65   }
66 }
67 
68 ATSConsistentHashNode *
lookup(const char * url,ATSConsistentHashIter * i,bool * w,ATSHash64 * h)69 ATSConsistentHash::lookup(const char *url, ATSConsistentHashIter *i, bool *w, ATSHash64 *h)
70 {
71   uint64_t url_hash;
72   ATSConsistentHashIter NodeMapIterUp, *iter;
73   ATSHash64 *thash;
74   bool *wptr, wrapped = false;
75 
76   if (h) {
77     thash = h;
78   } else if (hash) {
79     thash = hash;
80   } else {
81     return nullptr;
82   }
83 
84   if (w) {
85     wptr = w;
86   } else {
87     wptr = &wrapped;
88   }
89 
90   if (i) {
91     iter = i;
92   } else {
93     iter = &NodeMapIterUp;
94   }
95 
96   if (url) {
97     thash->update(url, strlen(url));
98     thash->final();
99     url_hash = thash->get();
100     thash->clear();
101 
102     *iter = NodeMap.lower_bound(url_hash);
103 
104     if (*iter == NodeMap.end()) {
105       *wptr = true;
106       *iter = NodeMap.begin();
107     }
108   } else {
109     (*iter)++;
110   }
111 
112   if (!(*wptr) && *iter == NodeMap.end()) {
113     *wptr = true;
114     *iter = NodeMap.begin();
115   }
116 
117   if (*wptr && *iter == NodeMap.end()) {
118     return nullptr;
119   }
120 
121   return (*iter)->second;
122 }
123 
124 ATSConsistentHashNode *
lookup_available(const char * url,ATSConsistentHashIter * i,bool * w,ATSHash64 * h)125 ATSConsistentHash::lookup_available(const char *url, ATSConsistentHashIter *i, bool *w, ATSHash64 *h)
126 {
127   uint64_t url_hash;
128   ATSConsistentHashIter NodeMapIterUp, *iter;
129   ATSHash64 *thash;
130   bool *wptr, wrapped = false;
131 
132   if (h) {
133     thash = h;
134   } else if (hash) {
135     thash = hash;
136   } else {
137     return nullptr;
138   }
139 
140   if (w) {
141     wptr = w;
142   } else {
143     wptr = &wrapped;
144   }
145 
146   if (i) {
147     iter = i;
148   } else {
149     iter = &NodeMapIterUp;
150   }
151 
152   if (url) {
153     thash->update(url, strlen(url));
154     thash->final();
155     url_hash = thash->get();
156     thash->clear();
157 
158     *iter = NodeMap.lower_bound(url_hash);
159   }
160 
161   if (*iter == NodeMap.end()) {
162     *wptr = true;
163     *iter = NodeMap.begin();
164   }
165 
166   while (!(*iter)->second->available) {
167     (*iter)++;
168 
169     if (!(*wptr) && *iter == NodeMap.end()) {
170       *wptr = true;
171       *iter = NodeMap.begin();
172     } else if (*wptr && *iter == NodeMap.end()) {
173       return nullptr;
174     }
175   }
176 
177   return (*iter)->second;
178 }
179 
180 ATSConsistentHashNode *
lookup_by_hashval(uint64_t hashval,ATSConsistentHashIter * i,bool * w)181 ATSConsistentHash::lookup_by_hashval(uint64_t hashval, ATSConsistentHashIter *i, bool *w)
182 {
183   ATSConsistentHashIter NodeMapIterUp, *iter;
184   bool *wptr, wrapped = false;
185 
186   if (w) {
187     wptr = w;
188   } else {
189     wptr = &wrapped;
190   }
191 
192   if (i) {
193     iter = i;
194   } else {
195     iter = &NodeMapIterUp;
196   }
197 
198   *iter = NodeMap.lower_bound(hashval);
199 
200   if (*iter == NodeMap.end()) {
201     *wptr = true;
202     *iter = NodeMap.begin();
203   }
204 
205   return (*iter)->second;
206 }
207 
~ATSConsistentHash()208 ATSConsistentHash::~ATSConsistentHash()
209 {
210   if (hash) {
211     delete hash;
212   }
213 }
214