1 /*
2 * Copyright (c) 2001 - 2003
3 * NetGroup, Politecnico di Torino (Italy)
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the Politecnico di Torino nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 *
31 */
32
33 #include <GlobalConst.h>
34
35 #ifdef WIN32
36 #include "tme.h"
37 #include "bucket_lookup.h"
38 #endif
39
40 #ifdef __FreeBSD__
41
42 #ifdef _KERNEL
43 #include <net/tme/tme.h>
44 #include <net/tme/bucket_lookup.h>
45 #else
46 #include <tme/tme.h>
47 #include <tme/bucket_lookup.h>
48 #endif
49
50 #endif
51
52
53
54 /* the key is represented by the initial and final value */
55 /* of the bucket. At the moment bucket_lookup is able to */
56 /* manage values of 16, 32 bits. */
bucket_lookup(uint8 * key,TME_DATA * data,MEM_TYPE * mem_ex,struct time_conv * time_ref)57 uint32 bucket_lookup(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
58 {
59 uint32 value;
60 uint32 i,j;
61 int found=-1;
62 uint32 blocks;
63 uint32 block_size;
64 uint8 *temp;
65 if ((data->key_len!=1)&& /*16 bit value*/
66 (data->key_len!=2)) /*32 bit value*/
67 return TME_ERROR;
68
69 /*32 bit values*/
70 blocks=data->filled_blocks-1;
71 block_size=data->block_size;
72 i=blocks/2; /*relative shift*/
73 j=i;
74 temp=data->shared_memory_base_address+block_size;
75
76 if (data->key_len==2)
77 {
78 value=SW_ULONG_AT(key,0);
79
80 if((value<SW_ULONG_AT(temp,0))||(value>SW_ULONG_AT(temp+block_size*(blocks-1),4)))
81 {
82 uint32 *key32=(uint32*) key;
83 key32[0]=key32[1]=0;
84
85 GET_TIME((struct timeval *)(data->shared_memory_base_address+8),time_ref);
86
87 data->last_found=NULL;
88 return TME_FALSE;
89 }
90
91 while(found==-1) /* search routine */
92 {
93 i=(i==1)? 1:i>>1;
94 if (SW_ULONG_AT(temp+block_size*j,0)>value)
95 if (SW_ULONG_AT(temp+block_size*(j-1),4)<value)
96 found=-2;
97 else
98 j-=i;
99 else
100 if (SW_ULONG_AT(temp+block_size*j,4)<value)
101 if (SW_ULONG_AT(temp+block_size*j,0)>value)
102 found=-2;
103 else
104 j+=i;
105 else found=j;
106 }
107 if (found<0)
108 {
109 uint32 *key32=(uint32*) key;
110 key32[0]=key32[1]=0;
111
112 GET_TIME((struct timeval *)(data->shared_memory_base_address+8),time_ref);
113
114 data->last_found=NULL;
115 return TME_FALSE;
116 }
117
118 data->last_found=data->lut_base_address+found*sizeof(RECORD);
119
120 COPY_MEMORY(key,temp+block_size*found,8);
121
122 GET_TIME((struct timeval *)(temp+block_size*found+8),time_ref);
123
124 return TME_TRUE;
125 }
126 else
127 {
128 value=SW_USHORT_AT(key,0);
129
130 if((value<SW_USHORT_AT(temp,0))||(value>SW_USHORT_AT(temp+block_size*(blocks-1),2)))
131 {
132 uint16 *key16=(uint16*) key;
133 key16[0]=key16[1]=0;
134
135 GET_TIME((struct timeval *)(data->shared_memory_base_address+4),time_ref);
136
137 data->last_found=NULL;
138 return TME_FALSE;
139 }
140
141 while(found==-1) /* search routine */
142 {
143 i=(i==1)? 1:i>>1;
144 if (SW_USHORT_AT(temp+block_size*j,0)>value)
145 if (SW_USHORT_AT(temp+block_size*(j-1),2)<value)
146 found=-2;
147 else
148 j-=i;
149 else
150 if (SW_USHORT_AT(temp+block_size*j,2)<value)
151 if (SW_USHORT_AT(temp+block_size*j,0)>value)
152 found=-2;
153 else
154 j+=i;
155 else found=j;
156 }
157
158 if (found<0)
159 {
160 uint16 *key16=(uint16*) key;
161 key16[0]=key16[1]=0;
162
163 GET_TIME((struct timeval *)(data->shared_memory_base_address+4),time_ref);
164
165 data->last_found=NULL;
166 return TME_FALSE;
167 }
168
169 data->last_found=data->lut_base_address+found*sizeof(RECORD);
170
171 GET_TIME((struct timeval *)(temp+block_size*found+4),time_ref);
172
173 COPY_MEMORY(key,temp+block_size*found,4);
174
175 return TME_TRUE;
176 }
177
178 }
179
bucket_lookup_insert(uint8 * key,TME_DATA * data,MEM_TYPE * mem_ex,struct time_conv * time_ref)180 uint32 bucket_lookup_insert(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
181 {
182 RECORD *records=(RECORD*)data->lut_base_address;
183
184 if ((data->key_len!=1)&& /*16 bit value*/
185 (data->key_len!=2)) /*32 bit value*/
186 return TME_ERROR;
187
188 if(data->key_len==2)
189 {
190 uint32 start,stop;
191 uint8 *tmp;
192
193 start=SW_ULONG_AT(key,0);
194 stop=SW_ULONG_AT(key,4);
195
196 if (start>stop)
197 return TME_ERROR;
198 if (data->filled_entries>0)
199 {
200 tmp=mem_ex->buffer+SW_ULONG_AT(&records[data->filled_entries-1].block,0);
201 /*check if it is coherent with the previous block*/
202 if (SW_ULONG_AT(tmp,4)>=start)
203 return TME_ERROR;
204 }
205
206 if (data->filled_blocks==data->shared_memory_blocks)
207 return TME_ERROR;
208
209 if (data->filled_entries==data->lut_entries)
210 return TME_ERROR;
211
212 tmp=data->shared_memory_base_address+data->block_size*data->filled_blocks;
213
214 COPY_MEMORY(tmp,key,8);
215
216 SW_ULONG_ASSIGN(&records[data->filled_entries].block,tmp-mem_ex->buffer);
217 SW_ULONG_ASSIGN(&records[data->filled_entries].exec_fcn,data->default_exec);
218
219 GET_TIME((struct timeval *)(tmp+8),time_ref);
220
221 data->filled_blocks++;
222 data->filled_entries++;
223
224 return TME_TRUE;
225 }
226 else
227 {
228 uint16 start,stop;
229 uint8 *tmp;
230
231 start=SW_USHORT_AT(key,0);
232 stop=SW_USHORT_AT(key,2);
233
234 if (start>stop)
235 return TME_ERROR;
236 if (data->filled_entries>0)
237 {
238 tmp=mem_ex->buffer+SW_ULONG_AT(&records[data->filled_entries-1].block,0);
239 /*check if it is coherent with the previous block*/
240 if (SW_USHORT_AT(tmp,2)>=start)
241 return TME_ERROR;
242 }
243
244 if (data->filled_blocks==data->shared_memory_blocks)
245 return TME_ERROR;
246
247 if (data->filled_entries==data->lut_entries)
248 return TME_ERROR;
249
250 tmp=mem_ex->buffer+SW_ULONG_AT(&records[data->filled_entries].block,0);
251
252 COPY_MEMORY(tmp,key,4);
253
254 SW_ULONG_ASSIGN(&records[data->filled_entries].block,tmp-mem_ex->buffer);
255 SW_ULONG_ASSIGN(&records[data->filled_entries].exec_fcn,data->default_exec);
256
257 GET_TIME((struct timeval *)(tmp+4),time_ref);
258
259 data->filled_blocks++;
260 data->filled_entries++;
261
262 return TME_TRUE;
263 }
264 }
265