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 "normal_lookup.h"
30 #include <net/tme/tme.h>
31 #include <net/tme/normal_lookup.h>
34 #include <tme/normal_lookup.h>
40 /* lookup in the table, seen as an hash */
41 /* if not found, inserts an element */
42 /* returns TME_TRUE if the entry is found or created, */
43 /* returns TME_FALSE if no more blocks are available */
44 uint32
normal_lut_w_insert(uint8
*key
, TME_DATA
*data
, MEM_TYPE
*mem_ex
, struct time_conv
*time_ref
)
48 uint32
*key32
=(uint32
*) key
;
49 uint32 shrinked_key
=0;
51 RECORD
*records
=(RECORD
*)data
->lut_base_address
;
53 uint32 key_len
=data
->key_len
;
54 /*the key is shrinked into a 32-bit value */
55 for (i
=0; i
<key_len
;i
++)
56 shrinked_key
^=key32
[i
];
57 /*the first index in the table is calculated*/
58 index
=shrinked_key
% data
->lut_entries
;
60 while (tocs
<=data
->filled_entries
)
63 if (records
[index
].block
==0)
64 { /*creation of a new entry*/
66 if (data
->filled_blocks
==data
->shared_memory_blocks
)
68 /*no more free blocks*/
69 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+4*key_len
),time_ref
);
70 data
->last_found
=NULL
;
74 /*offset=absolute pointer to the block associated*/
75 /*with the newly created entry*/
76 offset
=data
->shared_memory_base_address
+
77 data
->block_size
*data
->filled_blocks
;
79 /*copy the key in the block*/
80 COPY_MEMORY(offset
,key32
,key_len
*4);
81 GET_TIME((struct timeval
*)(offset
+4*key_len
),time_ref
);
82 /*assign the block relative offset to the entry, in NBO*/
83 SW_ULONG_ASSIGN(&records
[index
].block
,offset
-mem_ex
->buffer
);
85 data
->filled_blocks
++;
87 /*assign the exec function ID to the entry, in NBO*/
88 SW_ULONG_ASSIGN(&records
[index
].exec_fcn
,data
->default_exec
);
89 data
->filled_entries
++;
91 data
->last_found
=(uint8
*)&records
[index
];
95 /*offset contains the absolute pointer to the block*/
96 /*associated with the current entry */
97 offset
=mem_ex
->buffer
+SW_ULONG_AT(&records
[index
].block
,0);
99 for (i
=0; (i
<key_len
) && (key32
[i
]==ULONG_AT(offset
,i
*4)); i
++);
103 /*key in the block matches the one provided, right entry*/
104 GET_TIME((struct timeval
*)(offset
+4*key_len
),time_ref
);
105 data
->last_found
=(uint8
*)&records
[index
];
110 /* wrong entry, rehashing */
111 if (IS_DELETABLE(offset
+key_len
*4,data
))
113 ZERO_MEMORY(offset
,data
->block_size
);
114 COPY_MEMORY(offset
,key32
,key_len
*4);
115 SW_ULONG_ASSIGN(&records
[index
].exec_fcn
,data
->default_exec
);
116 GET_TIME((struct timeval
*)(offset
+key_len
*4),time_ref
);
117 data
->last_found
=(uint8
*)&records
[index
];
122 index
=(index
+data
->rehashing_value
) % data
->lut_entries
;
128 /* nothing found, last found= out of lut */
129 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+4*key_len
),time_ref
);
130 data
->last_found
=NULL
;
135 /* lookup in the table, seen as an hash */
136 /* if not found, returns out of count entry index */
137 /* returns TME_TRUE if the entry is found */
138 /* returns TME_FALSE if the entry is not found */
139 uint32
normal_lut_wo_insert(uint8
*key
, TME_DATA
*data
, MEM_TYPE
*mem_ex
, struct time_conv
*time_ref
)
143 uint32
*key32
=(uint32
*) key
;
144 uint32 shrinked_key
=0;
146 RECORD
*records
=(RECORD
*)data
->lut_base_address
;
148 uint32 key_len
=data
->key_len
;
149 /*the key is shrinked into a 32-bit value */
150 for (i
=0; i
<key_len
;i
++)
151 shrinked_key
^=key32
[i
];
152 /*the first index in the table is calculated*/
153 index
=shrinked_key
% data
->lut_entries
;
155 while (tocs
<=data
->filled_entries
)
158 if (records
[index
].block
==0)
159 { /*out of table, insertion is not allowed*/
160 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+4*key_len
),time_ref
);
161 data
->last_found
=NULL
;
164 /*offset contains the absolute pointer to the block*/
165 /*associated with the current entry */
167 offset
=mem_ex
->buffer
+SW_ULONG_AT(&records
[index
].block
,0);
169 for (i
=0; (i
<key_len
) && (key32
[i
]==ULONG_AT(offset
,i
*4)); i
++);
173 /*key in the block matches the one provided, right entry*/
174 GET_TIME((struct timeval
*)(offset
+4*key_len
),time_ref
);
175 data
->last_found
=(uint8
*)&records
[index
];
180 /*wrong entry, rehashing*/
181 index
=(index
+data
->rehashing_value
) % data
->lut_entries
;
186 /*nothing found, last found= out of lut*/
187 GET_TIME((struct timeval
*)(data
->shared_memory_base_address
+4*key_len
),time_ref
);
188 data
->last_found
=NULL
;