Browse code

all: updated FSF address in GPL text

Anthony Messina authored on 04/07/2014 09:36:37 • Daniel-Constantin Mierla committed on 04/07/2014 09:37:36
Showing 1 changed files
... ...
@@ -15,7 +15,7 @@
15 15
  *
16 16
  * You should have received a copy of the GNU General Public License 
17 17
  * along with this program; if not, write to the Free Software 
18
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
19 19
  */
20 20
 
21 21
 #include "dt.h"
Browse code

pdb: add daemon 'pdb_server' and optimising data compiler 'pdbt'

- add number portability database daemon and optimizing data compiler
- add debian packaging scripts for tool and daemon as well
- TODO:
- add documentation (run binaries with '-h' for now to get help)
- fix this redundant declaration of trie (dt* files) and logging (log*).
There exists already an implementation that uses the sr core parts for
this, but we import the proven implementation for now.
- add data helper scripts as well, they need some cleanup first
- initial implementation was done from Hardy Kahl @ 1&1 Internet Ag
- further bug fixes from Timo Reimann, timo dot reimann at 1und1 dot de

Henning Westerholt authored on 10/09/2009 16:35:05
Showing 1 changed files
1 1
new file mode 100644
... ...
@@ -0,0 +1,360 @@
1
+/*
2
+ * Copyright (C) 2009 1&1 Internet AG
3
+ *
4
+ * This file is part of sip-router, a free SIP server.
5
+ *
6
+ * sip-router is free software; you can redistribute it and/or modify
7
+ * it under the terms of the GNU General Public License as published by
8
+ * the Free Software Foundation; either version 2 of the License, or
9
+ * (at your option) any later version
10
+ *
11
+ * sip-router is distributed in the hope that it will be useful,
12
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
13
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
+ * GNU General Public License for more details.
15
+ *
16
+ * You should have received a copy of the GNU General Public License 
17
+ * along with this program; if not, write to the Free Software 
18
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19
+ */
20
+
21
+#include "dt.h"
22
+#include "dtm.h"
23
+#include "carrier.h"
24
+#include "log.h"
25
+#include <stdlib.h>
26
+#include <stdio.h>
27
+#include <string.h>
28
+
29
+
30
+
31
+
32
+struct dt_node_t *dt_init()
33
+{
34
+	struct dt_node_t *root;
35
+
36
+	root = malloc(sizeof(struct dt_node_t));
37
+	if (root == NULL) {
38
+		LERR("dt_init() cannot allocate memory for dt_node_t.\n");
39
+		return NULL;
40
+	}
41
+
42
+	memset(root, 0, sizeof(struct dt_node_t));
43
+
44
+	return root;
45
+}
46
+
47
+
48
+
49
+
50
+void dt_delete(struct dt_node_t *root, struct dt_node_t *node)
51
+{
52
+	int i;
53
+	if (node==NULL) return;
54
+
55
+	for (i=0; i<10; i++) {
56
+		dt_delete(root, node->child[i]);
57
+		node->child[i] = NULL;
58
+	}
59
+
60
+	if (node != root) free(node);
61
+}
62
+
63
+
64
+
65
+
66
+void dt_destroy(struct dt_node_t **root)
67
+{
68
+	if ((root != NULL) && (*root != NULL)) {
69
+		dt_delete(*root, *root);
70
+		free(*root);
71
+		*root = NULL;
72
+	}
73
+}
74
+
75
+
76
+
77
+
78
+void dt_clear(struct dt_node_t *root)
79
+{
80
+	dt_delete(root, root);
81
+	memset(root, 0, sizeof(struct dt_node_t));
82
+}
83
+
84
+
85
+
86
+
87
+int dt_insert(struct dt_node_t *root, const char *number, int numberlen, carrier_t carrier)
88
+{
89
+	struct dt_node_t *node = root;
90
+	int i=0;
91
+	unsigned int digit;
92
+
93
+	while (i<numberlen) {
94
+		digit = number[i] - '0';
95
+		if (digit>9) {
96
+			LERR("dt_insert() cannot insert non-numerical number\n");
97
+			return -1;
98
+		}
99
+		if (node->child[digit] == NULL) {
100
+			node->child[digit] = malloc(sizeof(struct dt_node_t));
101
+#ifdef DT_MEM_ASSERT
102
+			assert(node->child[digit] != NULL);
103
+#else
104
+			if (node->child[digit] == NULL) {
105
+				LERR("dt_insert() cannot allocate memory\n");
106
+				return -1;
107
+			}
108
+#endif
109
+			/* non-mapping intermediary nodes carry the special carrier id 0 */
110
+			memset(node->child[digit], 0, sizeof(struct dt_node_t));
111
+		}
112
+		node = node->child[digit];
113
+
114
+		i++;
115
+	}
116
+
117
+	node->carrier = carrier;
118
+	return 0;
119
+}
120
+
121
+
122
+
123
+
124
+int dt_size(struct dt_node_t *root)
125
+{
126
+	int i;
127
+	int sum = 0;
128
+
129
+	if (root == NULL) return 0;
130
+
131
+	for (i=0; i<10; i++) {
132
+		sum += dt_size(root->child[i]);
133
+	}
134
+	return sum+1;
135
+}
136
+
137
+
138
+
139
+
140
+int dt_loaded_nodes(struct dt_node_t *root) {
141
+	int i;
142
+	int sum = 0;
143
+
144
+	if (root == NULL) return 0;
145
+
146
+	for (i=0; i<10; i++) {
147
+		sum += dt_loaded_nodes(root->child[i]);
148
+	}
149
+
150
+	if (root->carrier > 0) sum++;
151
+
152
+	return sum;
153
+}
154
+
155
+
156
+
157
+
158
+int dt_leaves(struct dt_node_t *root)
159
+{
160
+	int i;
161
+	int sum = 0;
162
+	int leaf = 1;
163
+
164
+	for (i=0; i<10; i++) {
165
+		if (root->child[i]) {
166
+			sum += dt_leaves(root->child[i]);
167
+			leaf = 0;
168
+		}
169
+	}
170
+
171
+	return sum+leaf;
172
+}
173
+
174
+
175
+
176
+
177
+int dt_longest_match(struct dt_node_t *root, const char *number, int numberlen, carrier_t *carrier)
178
+{
179
+	struct dt_node_t *node = root;
180
+	int nmatch = -1;
181
+	int i=0;
182
+	unsigned int digit;
183
+
184
+	if (node->carrier > 0) {
185
+		nmatch=0;
186
+		*carrier = node->carrier;
187
+	}
188
+	while (i<numberlen) {
189
+		digit = number[i] - '0';
190
+		if (digit>9) return nmatch;
191
+		if (node->child[digit] == NULL) return nmatch;
192
+		node = node->child[digit];
193
+		i++;
194
+		if (node->carrier > 0) {
195
+			nmatch=i;
196
+			*carrier = node->carrier;
197
+		}
198
+	}
199
+
200
+	return nmatch;
201
+}
202
+
203
+
204
+
205
+
206
+int dt_contains(struct dt_node_t *root, const char *number, int numberlen, carrier_t *carrier)
207
+{
208
+  return (dt_longest_match(root, number, numberlen, carrier) == numberlen);
209
+}
210
+
211
+
212
+
213
+
214
+/*
215
+ Returns the carrier if all children have the same carrier,
216
+ 0 otherwise.
217
+ */
218
+carrier_t dt_allcce(struct dt_node_t *root) {
219
+	int i;
220
+	carrier_t ret = 0;
221
+
222
+	/* determine single child carrier */
223
+	for (i=0; i<10; i++) {
224
+		if (root->child[i] == NULL)
225
+			return 0;
226
+		else if (root->child[i]->carrier > 0) {
227
+			ret=root->child[i]->carrier;
228
+			break;
229
+		}
230
+	}
231
+	if (ret==0) return 0;
232
+
233
+	/* check if all children share the same carrier */
234
+	for (i=0; i<10; i++) {
235
+		if ((root->child[i] == NULL) || (root->child[i]->carrier != ret)) return 0;
236
+	}
237
+
238
+	return ret;
239
+}
240
+
241
+
242
+
243
+/*
244
+ Cuts off tree branches which share a common carrier id with a node located
245
+ more upwards in the tree. To do so, the subtree starting at root will be
246
+ traversed recursively and according leaf nodes deleted.
247
+ Nodes potentially eligible for removal will be marked by the special carrier
248
+ id `0' (also denoting a [non-mapping] intermediary node). In order to decide
249
+ whether a node is eligible or not, the lastly observed carrier id will be
250
+ maintained in lastcarrier and transferred over to each recursion.
251
+ */
252
+int dt_optimize_leaf(struct dt_node_t *root, carrier_t lastcarrier)
253
+{
254
+	struct dt_node_t *node = root;
255
+	carrier_t currentcarrier;
256
+	int deleteret;
257
+	int delete;
258
+	carrier_t allcce;
259
+	int i;
260
+
261
+	if (node == NULL) return 0;
262
+
263
+	if (node->carrier == lastcarrier) {
264
+		node->carrier = 0;	    /* this is a node sharing carrier id */
265
+	}
266
+
267
+	if (node->carrier>0) currentcarrier=node->carrier;  /* new common carrier id starts at this node */
268
+	else currentcarrier=lastcarrier;		    /* carry over common carrier id */
269
+
270
+	/* 
271
+	 Nodes with children sharing the same carrier may be generalized into a common node (prefix). 
272
+	 Note that the code in the following if-statement is the reason why dt_optimize() calls this function
273
+	 multiple times.
274
+	 */
275
+	if ((allcce=dt_allcce(node))) {
276
+		/*
277
+		 generalization requires having an intermediary parent node or a common carrier id between
278
+		 all children and the current node 
279
+		 */
280
+		if ((node->carrier == 0) || (node->carrier < 0 && allcce == currentcarrier)) {
281
+			currentcarrier=allcce;
282
+			node->carrier=currentcarrier;
283
+			for(i=0; i<10; i++) {
284
+				/* 
285
+				 Negative carrier ids mark children eligible for generalization into a parent
286
+				 node. Carrier id 0 cannot be used because it could ambiguously refer to an
287
+				 intermediary parent node, thereby rendering differentiation of such nodes and
288
+				 generalized ones impossible and, in turn, overwriting mappings to existing
289
+				 carrier ids.
290
+				 When optimization completes, negative carrier ids will be modified to 0 to
291
+				 make sure other functions operating on the tree do not get confused. (See
292
+				 dt_clear_negatives() for details.)
293
+				 */
294
+				node->child[i]->carrier = -allcce;
295
+			}
296
+		}
297
+	}
298
+
299
+	/* preliminarily assume leaf nodes without carrier to be eligible for removal */
300
+	if (node->carrier <= 0) deleteret=1;
301
+	else deleteret=0;
302
+
303
+	/* optimize children */
304
+	for (i=0; i<10; i++) {
305
+		delete=dt_optimize_leaf(node->child[i], currentcarrier);
306
+		if (delete) {
307
+			dt_delete(node, node->child[i]);
308
+			node->child[i] = NULL;
309
+		}
310
+		/* this is no leaf node ==> revert removal assumption */
311
+		if (node->child[i]) deleteret = 0;
312
+	}
313
+
314
+	return deleteret;
315
+}
316
+
317
+
318
+
319
+/*
320
+ Replaces negative carrier ids in the given, root-based
321
+ subtree by zeros to comply with other functions which may
322
+ not expect negative carrier ids. (See also dt_optimize_leaf().)
323
+ */
324
+void dt_clear_negatives(struct dt_node_t *root)
325
+{
326
+    struct dt_node_t *node = root;
327
+    int i;
328
+
329
+    if (node == NULL) return;
330
+
331
+    for (i=0; i<10; i++) {
332
+	    dt_clear_negatives(node->child[i]);
333
+    }
334
+
335
+    if (node->carrier < 0) node->carrier = 0;
336
+}
337
+
338
+
339
+
340
+void dt_optimize(struct dt_node_t *root)
341
+{
342
+	int size;
343
+	int oldsize = 0;
344
+	
345
+	size=dt_size(root);
346
+
347
+	/*
348
+	 optimization gradually trims leaf nodes in each invocation
349
+	 of dt_optimize_leaf() ==> keep calling this function until
350
+	 the size of the tree stabilizes
351
+	 */
352
+	while (size!=oldsize) {
353
+		dt_optimize_leaf(root, 0);
354
+		oldsize=size;
355
+		size=dt_size(root);
356
+	}
357
+
358
+	/* turn negative carrier ids into zero's  */
359
+	dt_clear_negatives(root);
360
+}