3 * Politecnico di Torino. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that: (1) source code distributions
7 * retain the above copyright notice and this paragraph in its entirety, (2)
8 * distributions including binary code include the above copyright notice and
9 * this paragraph in its entirety in the documentation or other materials
10 * provided with the distribution, and (3) all advertising materials mentioning
11 * features or use of this software display the following acknowledgement:
12 * ``This product includes software developed by the Politecnico
13 * di Torino, and its contributors.'' Neither the name of
14 * the University nor the names of its contributors may be used to endorse
15 * or promote products derived from this software without specific prior
17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
18 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
24 #include "bucket_lookup.h"
30 #include <net/tme/tme.h>
31 #include <net/tme/bucket_lookup.h>
34 #include <tme/bucket_lookup.h>
41 /* the key is represented by the initial and final value */
42 /* of the bucket. At the moment bucket_lookup is able to */
43 /* manage values of 16, 32 bits. */
44 uint32
bucket_lookup(uint8
*key
, TME_DATA
*data
, MEM_TYPE
*mem_ex
, struct time_conv
*time_ref
)
52 if ((data
->key_len
!=1)&& /*16 bit value*/
53 (data
->key_len
!=2)) /*32 bit value*/
57 blocks
=data
->filled_blocks
-1;
58 block_size
=data
->block_size
;
59 i
=blocks
/2; /*relative shift*/
61 temp
=data
->shared_memory_base_address
+block_size
;
65 value
=SW_ULONG_AT(key
,0);
67 if((value
<SW_ULONG_AT(temp
,0))||(value
>SW_ULONG_AT(temp
+block_size
*(blocks
-1),4)))
69 uint32
*key32
=(uint32
*) key
;
72 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+8),time_ref
);
74 data
->last_found
=NULL
;
78 while(found
==-1) /* search routine */
81 if (SW_ULONG_AT(temp
+block_size
*j
,0)>value
)
82 if (SW_ULONG_AT(temp
+block_size
*(j
-1),4)<value
)
87 if (SW_ULONG_AT(temp
+block_size
*j
,4)<value
)
88 if (SW_ULONG_AT(temp
+block_size
*j
,0)>value
)
96 uint32
*key32
=(uint32
*) key
;
99 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+8),time_ref
);
101 data
->last_found
=NULL
;
105 data
->last_found
=data
->lut_base_address
+found
*sizeof(RECORD
);
107 COPY_MEMORY(key
,temp
+block_size
*found
,8);
109 GET_TIME((struct timeval
*)(temp
+block_size
*found
+8),time_ref
);
115 value
=SW_USHORT_AT(key
,0);
117 if((value
<SW_USHORT_AT(temp
,0))||(value
>SW_USHORT_AT(temp
+block_size
*(blocks
-1),2)))
119 uint16
*key16
=(uint16
*) key
;
122 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+4),time_ref
);
124 data
->last_found
=NULL
;
128 while(found
==-1) /* search routine */
131 if (SW_USHORT_AT(temp
+block_size
*j
,0)>value
)
132 if (SW_USHORT_AT(temp
+block_size
*(j
-1),2)<value
)
137 if (SW_USHORT_AT(temp
+block_size
*j
,2)<value
)
138 if (SW_USHORT_AT(temp
+block_size
*j
,0)>value
)
147 uint16
*key16
=(uint16
*) key
;
150 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+4),time_ref
);
152 data
->last_found
=NULL
;
156 data
->last_found
=data
->lut_base_address
+found
*sizeof(RECORD
);
158 GET_TIME((struct timeval
*)(temp
+block_size
*found
+4),time_ref
);
160 COPY_MEMORY(key
,temp
+block_size
*found
,4);
167 uint32
bucket_lookup_insert(uint8
*key
, TME_DATA
*data
, MEM_TYPE
*mem_ex
, struct time_conv
*time_ref
)
169 RECORD
*records
=(RECORD
*)data
->lut_base_address
;
171 if ((data
->key_len
!=1)&& /*16 bit value*/
172 (data
->key_len
!=2)) /*32 bit value*/
180 start
=SW_ULONG_AT(key
,0);
181 stop
=SW_ULONG_AT(key
,4);
185 if (data
->filled_entries
>0)
187 tmp
=mem_ex
->buffer
+SW_ULONG_AT(&records
[data
->filled_entries
-1].block
,0);
188 /*check if it is coherent with the previous block*/
189 if (SW_ULONG_AT(tmp
,4)>=start
)
193 if (data
->filled_blocks
==data
->shared_memory_blocks
)
196 if (data
->filled_entries
==data
->lut_entries
)
199 tmp
=data
->shared_memory_base_address
+data
->block_size
*data
->filled_blocks
;
201 COPY_MEMORY(tmp
,key
,8);
203 SW_ULONG_ASSIGN(&records
[data
->filled_entries
].block
,tmp
-mem_ex
->buffer
);
204 SW_ULONG_ASSIGN(&records
[data
->filled_entries
].exec_fcn
,data
->default_exec
);
206 GET_TIME((struct timeval
*)(tmp
+8),time_ref
);
208 data
->filled_blocks
++;
209 data
->filled_entries
++;
218 start
=SW_USHORT_AT(key
,0);
219 stop
=SW_USHORT_AT(key
,2);
223 if (data
->filled_entries
>0)
225 tmp
=mem_ex
->buffer
+SW_ULONG_AT(&records
[data
->filled_entries
-1].block
,0);
226 /*check if it is coherent with the previous block*/
227 if (SW_USHORT_AT(tmp
,2)>=start
)
231 if (data
->filled_blocks
==data
->shared_memory_blocks
)
234 if (data
->filled_entries
==data
->lut_entries
)
237 tmp
=mem_ex
->buffer
+SW_ULONG_AT(&records
[data
->filled_entries
].block
,0);
239 COPY_MEMORY(tmp
,key
,4);
241 SW_ULONG_ASSIGN(&records
[data
->filled_entries
].block
,tmp
-mem_ex
->buffer
);
242 SW_ULONG_ASSIGN(&records
[data
->filled_entries
].exec_fcn
,data
->default_exec
);
244 GET_TIME((struct timeval
*)(tmp
+4),time_ref
);
246 data
->filled_blocks
++;
247 data
->filled_entries
++;