1 /*
2 * Copyright (C) 2005-2009 Voice Sistem SRL
3 *
4 * This file is part of Kamailio, a free SIP server.
5 *
6 * Kamailio 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 * Kamailio 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 */
21
22
23 #include <stdlib.h>
24 #include <stdio.h>
25
26 #include "../../core/str.h"
27 #include "../../core/mem/shm_mem.h"
28
29 #include "prefix_tree.h"
30 #include "routing.h"
31 #include "dr_time.h"
32
33 extern int inode;
34 extern int unode;
35
36
check_time(tmrec_t * time_rec)37 static inline int check_time(tmrec_t *time_rec)
38 {
39 ac_tm_t att;
40
41 /* shortcut: if there is no dstart, timerec is valid */
42 if(time_rec->dtstart == 0)
43 return 1;
44
45 memset(&att, 0, sizeof(att));
46
47 /* set current time */
48 if(ac_tm_set_time(&att, time(0)))
49 return 0;
50
51 /* does the recv_time match the specified interval? */
52 if(check_tmrec(time_rec, &att, 0) != 0)
53 return 0;
54
55 return 1;
56 }
57
58
internal_check_rt(ptree_node_t * ptn,unsigned int rgid)59 static inline rt_info_t *internal_check_rt(ptree_node_t *ptn, unsigned int rgid)
60 {
61 int i;
62 int rg_pos = 0;
63 rg_entry_t *rg = NULL;
64 rt_info_wrp_t *rtlw = NULL;
65
66 if((NULL == ptn) || (NULL == ptn->rg))
67 return NULL;
68
69 rg_pos = ptn->rg_pos;
70 rg = ptn->rg;
71 for(i = 0; (i < rg_pos) && (rg[i].rgid != rgid); i++)
72 ;
73 if(i < rg_pos) {
74 LM_DBG("found rgid %d (rule list %p)\n", rgid, rg[i].rtlw);
75 rtlw = rg[i].rtlw;
76 while(rtlw != NULL) {
77 if(check_time(rtlw->rtl->time_rec))
78 return rtlw->rtl;
79 rtlw = rtlw->next;
80 }
81 }
82
83 return NULL;
84 }
85
86
check_rt(ptree_node_t * ptn,unsigned int rgid)87 rt_info_t *check_rt(ptree_node_t *ptn, unsigned int rgid)
88 {
89 return internal_check_rt(ptn, rgid);
90 }
91
92
get_prefix(ptree_t * ptree,str * prefix,unsigned int rgid)93 rt_info_t *get_prefix(ptree_t *ptree, str *prefix, unsigned int rgid)
94 {
95 rt_info_t *rt = NULL;
96 char *tmp = NULL;
97 int idx = 0;
98
99 if(NULL == ptree)
100 goto err_exit;
101 if(NULL == prefix || NULL == prefix->s)
102 goto err_exit;
103 tmp = prefix->s;
104 /* go the tree down to the last digit in the
105 * prefix string or down to a leaf */
106 while(tmp < (prefix->s + prefix->len)) {
107 idx = get_node_index(*tmp);
108 if(idx == -1) {
109 /* unknown character in the prefix string */
110 goto err_exit;
111 }
112 if(tmp == (prefix->s + prefix->len - 1)) {
113 /* last digit in the prefix string */
114 break;
115 }
116 if(NULL == ptree->ptnode[idx].next) {
117 /* this is a leaf */
118 break;
119 }
120 ptree = ptree->ptnode[idx].next;
121 tmp++;
122 }
123 /* go in the tree up to the root trying to match the prefix */
124 while(ptree != NULL) {
125 /* is it a real node or an intermediate one */
126 idx = get_node_index(*tmp);
127 if(idx != -1 && NULL != ptree->ptnode[idx].rg) {
128 /* real node; check the constraints on the routing info*/
129 if(NULL != (rt = internal_check_rt(&(ptree->ptnode[idx]), rgid)))
130 break;
131 }
132 tmp--;
133 ptree = ptree->bp;
134 }
135 return rt;
136
137 err_exit:
138 return NULL;
139 }
140
141
get_pgw(pgw_t * pgw_l,long id)142 pgw_t *get_pgw(pgw_t *pgw_l, long id)
143 {
144 if(NULL == pgw_l)
145 goto err_exit;
146 while(NULL != pgw_l) {
147 if(id == pgw_l->id) {
148 return pgw_l;
149 }
150 pgw_l = pgw_l->next;
151 }
152 err_exit:
153 return NULL;
154 }
155
156
add_prefix(ptree_t * ptree,str * prefix,rt_info_t * r,unsigned int rg)157 int add_prefix(ptree_t *ptree, str *prefix, rt_info_t *r, unsigned int rg)
158 {
159 char *tmp = NULL;
160 int res = 0;
161 if(NULL == ptree)
162 goto err_exit;
163 tmp = prefix->s;
164 while(tmp < (prefix->s + prefix->len)) {
165 if(NULL == tmp)
166 goto err_exit;
167 int insert_index = get_node_index(*tmp);
168 if(insert_index == -1) {
169 /* unknown character in the prefix string */
170 goto err_exit;
171 }
172 if(tmp == (prefix->s + prefix->len - 1)) {
173 /* last symbol in the prefix string */
174
175 LM_DBG("adding info %p, %d at: "
176 "%p (%d)\n",
177 r, rg, &(ptree->ptnode[insert_index]), insert_index);
178 res = add_rt_info(&(ptree->ptnode[insert_index]), r, rg);
179 if(res < 0)
180 goto err_exit;
181 unode++;
182 res = 1;
183 goto ok_exit;
184 }
185 /* process the current symbol in the prefix */
186 if(NULL == ptree->ptnode[insert_index].next) {
187 /* allocate new node */
188 INIT_PTREE_NODE(ptree, ptree->ptnode[insert_index].next);
189 inode += PTREE_CHILDREN;
190 #if 0
191 printf("new tree node: %p (bp: %p)\n",
192 ptree->ptnode[insert_index].next,
193 ptree->ptnode[insert_index].next->bp
194 );
195 #endif
196 }
197 ptree = ptree->ptnode[insert_index].next;
198 tmp++;
199 }
200
201 ok_exit:
202 return 0;
203
204 err_exit:
205 return -1;
206 }
207
del_tree(ptree_t * t)208 int del_tree(ptree_t *t)
209 {
210 int i, j;
211 if(NULL == t)
212 goto exit;
213 /* delete all the children */
214 for(i = 0; i < PTREE_CHILDREN; i++) {
215 /* shm_free the rg array of rt_info */
216 if(NULL != t->ptnode[i].rg) {
217 for(j = 0; j < t->ptnode[i].rg_pos; j++) {
218 /* if non intermediate delete the routing info */
219 if(t->ptnode[i].rg[j].rtlw != NULL)
220 del_rt_list(t->ptnode[i].rg[j].rtlw);
221 }
222 shm_free(t->ptnode[i].rg);
223 }
224 /* if non leaf delete all the children */
225 if(t->ptnode[i].next != NULL)
226 del_tree(t->ptnode[i].next);
227 }
228 shm_free(t);
229 exit:
230 return 0;
231 }
232
del_rt_list(rt_info_wrp_t * rwl)233 void del_rt_list(rt_info_wrp_t *rwl)
234 {
235 rt_info_wrp_t *t = rwl;
236 while(rwl != NULL) {
237 t = rwl;
238 rwl = rwl->next;
239 if((--t->rtl->ref_cnt) == 0)
240 free_rt_info(t->rtl);
241 shm_free(t);
242 }
243 }
244
free_rt_info(rt_info_t * rl)245 void free_rt_info(rt_info_t *rl)
246 {
247 if(NULL == rl)
248 return;
249 if(NULL != rl->pgwl)
250 shm_free(rl->pgwl);
251 if(NULL != rl->time_rec)
252 tmrec_free(rl->time_rec);
253 shm_free(rl);
254 return;
255 }
256
print_rt(rt_info_t * rt)257 void print_rt(rt_info_t *rt)
258 {
259 int i = 0;
260 if(NULL == rt)
261 return;
262 printf("priority:%d list of gw:\n", rt->priority);
263 for(i = 0; i < rt->pgwa_len; i++)
264 if(NULL != rt->pgwl[i].pgw)
265 printf(" id:%ld pri:%.*s ip:%.*s \n", rt->pgwl[i].pgw->id,
266 rt->pgwl[i].pgw->pri.len, rt->pgwl[i].pgw->pri.s,
267 rt->pgwl[i].pgw->ip.len, rt->pgwl[i].pgw->ip.s);
268 }
269
270
get_node_index(char ch)271 int get_node_index(char ch)
272 {
273 switch(ch) {
274 case '0':
275 case '1':
276 case '2':
277 case '3':
278 case '4':
279 case '5':
280 case '6':
281 case '7':
282 case '8':
283 case '9':
284 return ch - '0';
285 case '*':
286 return 10;
287 case '#':
288 return 11;
289 case '+':
290 return 12;
291 }
292 return -1;
293 }
294