Kannel: Open Source WAP and SMS gateway  svn-r5335
numhash.c
Go to the documentation of this file.
1 /* ====================================================================
2  * The Kannel Software License, Version 1.0
3  *
4  * Copyright (c) 2001-2018 Kannel Group
5  * Copyright (c) 1998-2001 WapIT Ltd.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Kannel Group (http://www.kannel.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Kannel" and "Kannel Group" must not be used to
28  * endorse or promote products derived from this software without
29  * prior written permission. For written permission, please
30  * contact org@kannel.org.
31  *
32  * 5. Products derived from this software may not be called "Kannel",
33  * nor may "Kannel" appear in their name, without prior written
34  * permission of the Kannel Group.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS
40  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
41  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
42  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
43  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
44  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
45  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
46  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  *
49  * This software consists of voluntary contributions made by many
50  * individuals on behalf of the Kannel Group. For more information on
51  * the Kannel Group, please see <http://www.kannel.org/>.
52  *
53  * Portions of this software are based upon software originally written at
54  * WapIT Ltd., Helsinki, Finland for the Kannel project.
55  */
56 
57 /*
58  * numhash.c
59  *
60  * NUMBER HASH functions
61  *
62  * functions to add a number to database/hash
63  * and functions to retrieve them
64  *
65  * notes: read header file
66  *
67  * Kalle Marjola for project Kannel 1999-2000
68  */
69 
70 #include <stdlib.h>
71 #include <string.h>
72 #include <ctype.h>
73 #include <errno.h>
74 
75 #include "gwlib/gwlib.h"
76 #include "numhash.h"
77 
78 
79 #define NUMHASH_AUTO_HASH -1
80 
81 /* set of pre-calculated prime numbers for hash generation... */
82 
83 static int primes[] = {
84  101, 503, 1009, 2003, 3001, 5003, 7001,
85  10007, 20011, 30011, 40009, 50021, 60013, 70001, 80021, 90001,
86  100003, 150001, 200003, 300007, 400009, 500009, 600011, 700001,
87  800011, 900001, 1000003, 1100009, 1200007, 1300021, 1400017, 1500007,
88  1600033, 1700021, 1800017, 1900009, 2000003, 3000017, 4000037, 5000111,
89  6000101, 7000127, 8000051, -1
90 };
91 
92 struct numhash_table {
95  long table_size;
96  struct numhash_number **hash;
97  long hash_size;
98 }; /* Numhash */
99 
101  long long key; /* (hopefully) unique key */
102  struct numhash_number *next; /* next in hash table, if any */
103 };
104 
105 
106 struct nh_entry {
108  struct nh_entry *next;
109 };
110 
111 struct numhashes {
112  struct nh_entry *first;
113  struct nh_entry *last;
114 }; /* Multitable */
115 
116 
117 static int precision = 19; /* the precision (last numbers) used */
118 
119 /*
120  * add new item (number) to hash table
121  */
122 static int add_item(Numhash *table, struct numhash_number *nro)
123 {
124  if (table->hash[nro->key % table->hash_size]) { /* conflict */
125  struct numhash_number *ptr = table->hash[nro->key % table->hash_size];
126 
127  if (ptr->key == nro->key)
128  goto duplicate;
129 
130  while(ptr->next) {
131  ptr = ptr->next;
132  if (ptr->key == nro->key)
133  goto duplicate;
134  }
135  ptr->next = nro; /* put as last of the linkage */
136  } else
137  table->hash[nro->key % table->hash_size] = nro;
138 
139  return 0;
140 
141 duplicate:
142  warning(0, "Duplicate number %lld!", nro->key);
143  return -1;
144 }
145 
146 /* Add a new number to number list and hash
147  * Return 0 if all went ok, -1 if out of room
148  */
149 static int numhash_add_number(Numhash *table, char *nro)
150 {
151  struct numhash_number *newnro;
152 
153  if (table->number_total == table->table_size) {
154  error(0, "Table limit %ld reached, cannot add %s!",
155  table->table_size, nro);
156  return -1;
157  }
158  newnro = &table->numbers[table->number_total++]; /* take the next free */
159 
160  newnro->key = numhash_get_char_key(nro);
161  newnro->next = NULL;
162 
163  add_item(table, newnro);
164 
165  return 0;
166 }
167 
168 
169 /* Init the number table and hash table with given sizes
170  */
171 static Numhash *numhash_init(int max_numbers, int hash_size)
172 {
173  Numhash *ntable = NULL;
174 
175  ntable = gw_malloc(sizeof(Numhash));
176 
177  if (hash_size > 0)
178  ntable->hash_size = hash_size;
179  else if (hash_size == NUMHASH_AUTO_HASH) {
180  int i;
181  for(i=0 ; primes[i] > 0; i++) {
182  ntable->hash_size = primes[i];
183  if (ntable->hash_size > max_numbers)
184  break;
185  }
186  } else {
187  gw_free(ntable);
188  return NULL;
189  }
190  ntable->hash = gw_malloc(ntable->hash_size * sizeof(struct numhash_number *));
191  memset(ntable->hash, 0, sizeof(struct numhash_number *) * ntable->hash_size);
192 
193  ntable->table_size = max_numbers;
194  ntable->numbers = gw_malloc(ntable->table_size * sizeof(struct numhash_number));
195 
196  ntable->number_total = 0;
197 
198  /* set our accuracy according to the size of long int
199  * Ok, we call this many times if we use multiple tables, but
200  * that is not a problem...
201  */
202  if (sizeof(long long) >= 16)
203  precision = 38;
204  else if (sizeof(long long) >= 8)
205  precision = 19;
206 
207  return ntable;
208 }
209 
210 
211 
212 /*------------------------------------------------------
213  * PUBLIC FUNCTIONS
214  */
215 
216 
217 
219 {
220  long long key = numhash_get_key(nro);
221  if (key < 0)
222  return key;
223 
224  return numhash_find_key(table, key);
225 }
226 
227 
229 {
230  struct numhash_number *ptr;
231 
232  ptr = table->hash[key % table->hash_size];
233  while (ptr) {
234  if (ptr->key == key) return 1;
235  ptr = ptr->next;
236  }
237  return 0; /* not found */
238 }
239 
240 
241 
242 long long numhash_get_key(Octstr *nro)
243 {
244  long long key;
245 
246  if (!nro) return -1;
247 
248  if (octstr_len(nro) > precision)
249  key = strtoll(octstr_get_cstr(nro) + octstr_len(nro) - precision, (char**) NULL, 10);
250  else
251  key = strtoll(octstr_get_cstr(nro), (char**) NULL, 10);
252 
253  return key;
254 }
255 
256 
257 long long numhash_get_char_key(char *nro)
258 {
259  int len;
260  long long key;
261 
262  if (!nro) return -1;
263 
264  len = strlen(nro);
265 
266  if (len > precision)
267  key = strtoll(nro + len - precision, (char**) NULL, 10);
268  else
269  key = strtoll(nro, (char**) NULL, 10);
270 
271  return key;
272 }
273 
274 
276 {
277  if (table == NULL)
278  return;
279  gw_free(table->numbers);
280  gw_free(table->hash);
281  gw_free(table);
282 }
283 
284 
285 double numhash_hash_fill(Numhash *table, int *longest)
286 {
287  int i, l, max = 0, tot = 0;
288  struct numhash_number *ptr;
289 
290  for (i=0; i < table->hash_size; i++)
291  if (table->hash[i]) {
292  tot++;
293  ptr = table->hash[i];
294  for (l=0; ptr->next; ptr = ptr->next)
295  l++;
296  if (l > max)
297  max = l;
298  }
299 
300  if (longest != NULL)
301  *longest = max;
302 
303  return (double)(tot*100.0/(table->hash_size));
304 }
305 
306 
308 {
309  return table->number_total;
310 }
311 
312 
313 Numhash *numhash_create(const char *seek_url)
314 {
315  int loc, lines = 0;
316  List *request_headers, *reply_headers;
317  Octstr *url, *final_url, *reply_body;
318  Octstr *type, *charset;
319 
320  char *data, *ptr, numbuf[100];
321  int status;
322  Numhash *table;
323 
324  url = octstr_create(seek_url);
325  request_headers = http_create_empty_headers();
326  status = http_get_real(HTTP_METHOD_GET, url, request_headers, &final_url,
327  &reply_headers, &reply_body);
329  octstr_destroy(final_url);
330  http_destroy_headers(request_headers);
331 
332  if (status != HTTP_OK) {
333  http_destroy_headers(reply_headers);
334  octstr_destroy(reply_body);
335  error(0, "Cannot load numhash!");
336  return NULL;
337  }
338  http_header_get_content_type(reply_headers, &type, &charset);
340  http_destroy_headers(reply_headers);
341 
342  if (octstr_str_compare(type, "text/plain") != 0) {
343  octstr_destroy(reply_body);
344  error(0, "Strange content type <%s> for numhash - expecting 'text/plain'"
345  ", operatiom fails", octstr_get_cstr(type));
347  return NULL;
348  }
350 
351  ptr = data = octstr_get_cstr(reply_body);
352  while(*ptr) {
353  if (*ptr == '\n') lines++;
354  ptr++;
355  }
356  debug("numhash", 0, "Total %d lines in %s", lines, seek_url);
357 
358  table = numhash_init(lines+10, NUMHASH_AUTO_HASH); /* automatic hash */
359 
360  /* now, parse the number information */
361 
362  lines = 0;
363 
364  while((ptr = strchr(data, '\n'))) { /* each line is ended with linefeed */
365  *ptr = '\0';
366  while(*data != '\0' && isspace(*data))
367  data++;
368  if (*data != '#') {
369  loc = 0;
370  while (*data != '\0') {
371  if (isdigit(*data))
372  numbuf[loc++] = *data;
373  else if (*data == ' ' || *data == '+' || *data == '-')
374  ;
375  else break;
376  data++;
377  }
378  if (loc) {
379  numbuf[loc] = '\0';
380  numhash_add_number(table, numbuf);
381  lines++;
382  }
383  else
384  warning(0, "Corrupted line '%s'", data);
385  }
386  data = ptr+1; /* next row... */
387  }
388  octstr_destroy(reply_body);
389 
390  info(0, "Read from <%s> total of %ld numbers", seek_url, table->number_total);
391  return table;
392 }
393 
static Numhash * numhash_init(int max_numbers, int hash_size)
Definition: numhash.c:171
void error(int err, const char *fmt,...)
Definition: log.c:648
void info(int err, const char *fmt,...)
Definition: log.c:672
long * numbers
Definition: wsp_strings.c:85
static int primes[]
Definition: numhash.c:83
int type
Definition: smsc_cimd2.c:215
Numhash * hash
Definition: numhash.c:107
struct nh_entry * first
Definition: numhash.c:112
void http_header_get_content_type(List *headers, Octstr **type, Octstr **charset)
Definition: http.c:3225
struct numhash_number * next
Definition: numhash.c:102
void numhash_destroy(Numhash *table)
Definition: numhash.c:275
struct nh_entry * last
Definition: numhash.c:113
#define octstr_get_cstr(ostr)
Definition: octstr.h:233
Octstr * charset
Definition: test_ota.c:68
static List * lines
Definition: mtbatch.c:88
Numhash * numhash_create(const char *seek_url)
Definition: numhash.c:313
long number_total
Definition: numhash.c:94
long long key
Definition: numhash.c:101
void http_destroy_headers(List *headers)
Definition: http.c:2879
double numhash_hash_fill(Numhash *table, int *longest)
Definition: numhash.c:285
Definition: http.h:142
int numhash_find_number(Numhash *table, Octstr *nro)
Definition: numhash.c:218
int numhash_find_key(Numhash *table, long long key)
Definition: numhash.c:228
long long numhash_get_char_key(char *nro)
Definition: numhash.c:257
List * http_create_empty_headers(void)
Definition: http.c:2872
void warning(int err, const char *fmt,...)
Definition: log.c:660
void octstr_destroy(Octstr *ostr)
Definition: octstr.c:324
struct numhash_number * numbers
Definition: numhash.c:93
#define octstr_create(cstr)
Definition: octstr.h:125
static int add_item(Numhash *table, struct numhash_number *nro)
Definition: numhash.c:122
long octstr_len(const Octstr *ostr)
Definition: octstr.c:342
#define NUMHASH_AUTO_HASH
Definition: numhash.c:79
int http_get_real(int method, Octstr *url, List *request_headers, Octstr **final_url, List **reply_headers, Octstr **reply_body)
Definition: http.c:1821
long table_size
Definition: numhash.c:95
Definition: octstr.c:118
static int precision
Definition: numhash.c:117
void debug(const char *place, int err, const char *fmt,...)
Definition: log.c:726
int octstr_str_compare(const Octstr *ostr, const char *str)
Definition: octstr.c:973
long long numhash_get_key(Octstr *nro)
Definition: numhash.c:242
long hash_size
Definition: numhash.c:97
int numhash_size(Numhash *table)
Definition: numhash.c:307
static int numhash_add_number(Numhash *table, char *nro)
Definition: numhash.c:149
Definition: numhash.c:106
struct nh_entry * next
Definition: numhash.c:108
static Octstr * url
Definition: test_xmlrpc.c:84
Definition: list.c:102
struct numhash_number ** hash
Definition: numhash.c:96
See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.