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 "normal_lookup.h"
38 #endif
39
40 #ifdef __FreeBSD__
41
42 #ifdef _KERNEL
43 #include <net/tme/tme.h>
44 #include <net/tme/normal_lookup.h>
45 #else
46 #include <tme/tme.h>
47 #include <tme/normal_lookup.h>
48 #endif
49
50 #endif
51
52
53 /* lookup in the table, seen as an hash */
54 /* if not found, inserts an element */
55 /* returns TME_TRUE if the entry is found or created, */
56 /* returns TME_FALSE if no more blocks are available */
normal_lut_w_insert(uint8 * key,TME_DATA * data,MEM_TYPE * mem_ex,struct time_conv * time_ref)57 uint32 normal_lut_w_insert(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
58 {
59 uint32 i;
60 uint32 tocs=0;
61 uint32 *key32=(uint32*) key;
62 uint32 shrinked_key=0;
63 uint32 index;
64 RECORD *records=(RECORD*)data->lut_base_address;
65 uint8 *offset;
66 uint32 key_len=data->key_len;
67 /*the key is shrinked into a 32-bit value */
68 for (i=0; i<key_len;i++)
69 shrinked_key^=key32[i];
70 /*the first index in the table is calculated*/
71 index=shrinked_key % data->lut_entries;
72
73 while (tocs<=data->filled_entries)
74 {
75
76 if (records[index].block==0)
77 { /*creation of a new entry*/
78
79 if (data->filled_blocks==data->shared_memory_blocks)
80 {
81 /*no more free blocks*/
82 GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
83 data->last_found=NULL;
84 return TME_FALSE;
85 }
86
87 /*offset=absolute pointer to the block associated*/
88 /*with the newly created entry*/
89 offset=data->shared_memory_base_address+
90 data->block_size*data->filled_blocks;
91
92 /*copy the key in the block*/
93 COPY_MEMORY(offset,key32,key_len*4);
94 GET_TIME((struct timeval *)(offset+4*key_len),time_ref);
95 /*assign the block relative offset to the entry, in NBO*/
96 SW_ULONG_ASSIGN(&records[index].block,offset-mem_ex->buffer);
97
98 data->filled_blocks++;
99
100 /*assign the exec function ID to the entry, in NBO*/
101 SW_ULONG_ASSIGN(&records[index].exec_fcn,data->default_exec);
102 data->filled_entries++;
103
104 data->last_found=(uint8*)&records[index];
105
106 return TME_TRUE;
107 }
108 /*offset contains the absolute pointer to the block*/
109 /*associated with the current entry */
110 offset=mem_ex->buffer+SW_ULONG_AT(&records[index].block,0);
111
112 for (i=0; (i<key_len) && (key32[i]==ULONG_AT(offset,i*4)); i++);
113
114 if (i==key_len)
115 {
116 /*key in the block matches the one provided, right entry*/
117 GET_TIME((struct timeval *)(offset+4*key_len),time_ref);
118 data->last_found=(uint8*)&records[index];
119 return TME_TRUE;
120 }
121 else
122 {
123 /* wrong entry, rehashing */
124 if (IS_DELETABLE(offset+key_len*4,data))
125 {
126 ZERO_MEMORY(offset,data->block_size);
127 COPY_MEMORY(offset,key32,key_len*4);
128 SW_ULONG_ASSIGN(&records[index].exec_fcn,data->default_exec);
129 GET_TIME((struct timeval*)(offset+key_len*4),time_ref);
130 data->last_found=(uint8*)&records[index];
131 return TME_TRUE;
132 }
133 else
134 {
135 index=(index+data->rehashing_value) % data->lut_entries;
136 tocs++;
137 }
138 }
139 }
140
141 /* nothing found, last found= out of lut */
142 GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
143 data->last_found=NULL;
144 return TME_FALSE;
145
146 }
147
148 /* lookup in the table, seen as an hash */
149 /* if not found, returns out of count entry index */
150 /* returns TME_TRUE if the entry is found */
151 /* returns TME_FALSE if the entry is not found */
normal_lut_wo_insert(uint8 * key,TME_DATA * data,MEM_TYPE * mem_ex,struct time_conv * time_ref)152 uint32 normal_lut_wo_insert(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
153 {
154 uint32 i;
155 uint32 tocs=0;
156 uint32 *key32=(uint32*) key;
157 uint32 shrinked_key=0;
158 uint32 index;
159 RECORD *records=(RECORD*)data->lut_base_address;
160 uint8 *offset;
161 uint32 key_len=data->key_len;
162 /*the key is shrinked into a 32-bit value */
163 for (i=0; i<key_len;i++)
164 shrinked_key^=key32[i];
165 /*the first index in the table is calculated*/
166 index=shrinked_key % data->lut_entries;
167
168 while (tocs<=data->filled_entries)
169 {
170
171 if (records[index].block==0)
172 { /*out of table, insertion is not allowed*/
173 GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
174 data->last_found=NULL;
175 return TME_FALSE;
176 }
177 /*offset contains the absolute pointer to the block*/
178 /*associated with the current entry */
179
180 offset=mem_ex->buffer+SW_ULONG_AT(&records[index].block,0);
181
182 for (i=0; (i<key_len) && (key32[i]==ULONG_AT(offset,i*4)); i++);
183
184 if (i==key_len)
185 {
186 /*key in the block matches the one provided, right entry*/
187 GET_TIME((struct timeval *)(offset+4*key_len),time_ref);
188 data->last_found=(uint8*)&records[index];
189 return TME_TRUE;
190 }
191 else
192 {
193 /*wrong entry, rehashing*/
194 index=(index+data->rehashing_value) % data->lut_entries;
195 tocs++;
196 }
197 }
198
199 /*nothing found, last found= out of lut*/
200 GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
201 data->last_found=NULL;
202 return TME_FALSE;
203
204 }
205