drivers/net/packet/normal_lookup.c

   1 /*
   2  * Copyright (c) 2001
   3  *      Politecnico di Torino.  All rights reserved.
   4  *
   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
  16  * written permission.
  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.
  20  */
  21
  22 #ifdef WIN32
  23 #include "tme.h"
  24 #include "normal_lookup.h"
  25 #endif
  26
  27 #ifdef __FreeBSD__
  28
  29 #ifdef _KERNEL
  30 #include <net/tme/tme.h>
  31 #include <net/tme/normal_lookup.h>
  32 #else
  33 #include <tme/tme.h>
  34 #include <tme/normal_lookup.h>
  35 #endif
  36
  37 #endif
  38
  39
  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)
  45 {
  46         uint32 i;
  47         uint32 tocs=0;
  48         uint32 *key32=(uint32*) key;
  49         uint32 shrinked_key=0;
  50         uint32 index;
  51         RECORD *records=(RECORD*)data->lut_base_address;
  52         uint8 *offset;
  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;
  59
  60         while (tocs<=data->filled_entries)
  61         {
  62
  63                 if (records[index].block==0)
  64                 {   /*creation of a new entry*/
  65
  66                         if (data->filled_blocks==data->shared_memory_blocks)
  67                         {
  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;
  71                                 return TME_FALSE;
  72                         }
  73
  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;
  78
  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);
  84
  85                         data->filled_blocks++;
  86
  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++;
  90
  91                         data->last_found=(uint8*)&records[index];
  92
  93                         return TME_TRUE;
  94                 }
  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);
  98
  99                 for (i=0; (i<key_len) && (key32[i]==ULONG_AT(offset,i*4)); i++);
 100
 101                 if (i==key_len)
 102                         {
 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];
 106                                 return TME_TRUE;
 107                         }
 108                 else
 109                 {
 110                         /* wrong entry, rehashing */
 111                         if (IS_DELETABLE(offset+key_len*4,data))
 112                         {
 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];
 118                                 return TME_TRUE;
 119                         }
 120                         else
 121                         {
 122                                 index=(index+data->rehashing_value) % data->lut_entries;
 123                                 tocs++;
 124                         }
 125                 }
 126         }
 127
 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;
 131         return TME_FALSE;
 132
 133 }
 134
 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)
 140 {
 141         uint32 i;
 142         uint32 tocs=0;
 143         uint32 *key32=(uint32*) key;
 144         uint32 shrinked_key=0;
 145         uint32 index;
 146         RECORD *records=(RECORD*)data->lut_base_address;
 147         uint8 *offset;
 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;
 154
 155         while (tocs<=data->filled_entries)
 156         {
 157
 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;
 162                         return TME_FALSE;
 163                 }
 164                 /*offset contains the absolute pointer to the block*/
 165                 /*associated with the current entry */
 166
 167                 offset=mem_ex->buffer+SW_ULONG_AT(&records[index].block,0);
 168
 169                 for (i=0; (i<key_len) && (key32[i]==ULONG_AT(offset,i*4)); i++);
 170
 171                 if (i==key_len)
 172                         {
 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];
 176                                 return TME_TRUE;
 177                         }
 178                 else
 179                 {
 180                         /*wrong entry, rehashing*/
 181                         index=(index+data->rehashing_value) % data->lut_entries;
 182                         tocs++;
 183                 }
 184         }
 185
 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;
 189         return TME_FALSE;
 190
 191 }