src/cm/cm_hash.x

   1 /*******************************************************************************
   2 ################################################################################
   3 #   Copyright (c) [2017-2019] [Radisys]                                        #
   4 #                                                                              #
   5 #   Licensed under the Apache License, Version 2.0 (the "License");            #
   6 #   you may not use this file except in compliance with the License.           #
   7 #   You may obtain a copy of the License at                                    #
   8 #                                                                              #
   9 #       http://www.apache.org/licenses/LICENSE-2.0                             #
  10 #                                                                              #
  11 #   Unless required by applicable law or agreed to in writing, software        #
  12 #   distributed under the License is distributed on an "AS IS" BASIS,          #
  13 #   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   #
  14 #   See the License for the specific language governing permissions and        #
  15 #   limitations under the License.                                             #
  16 ################################################################################
  17 *******************************************************************************/
  18 \f
  19 /********************************************************************20**
  20
  21      Name:     common hash functions
  22
  23      Type:     C include file
  24
  25      Desc:     Structures, variables and typedefs required by common
  26                functions.
  27                (Newer version of functions in cm_bdy1)
  28
  29      File:     cm_hash.x
  30
  31 *********************************************************************21*/
  32
  33 #ifndef __CMHASHX__
  34 #define __CMHASHX__
  35
  36 #ifdef __cplusplus
  37 extern "C" {
  38 #endif
  39 \f
  40 /* typedefs */
  41
  42 /* forward definitions */
  43
  44 typedef struct cmHashListCp CmHashListCp;     /*  hash list control point */
  45
  46
  47 /* hash function */
  48
  49 typedef S16 (* CmHashFunc) ARGS((CmHashListCp *hashListCp, uint8_t *key,
  50                                   uint16_t keyLen, uint16_t *idx));
  51
  52 /* list entry */
  53 typedef struct cmListEnt CmListEnt;      /* list entry */
  54
  55 struct cmListEnt                         /* list entry */
  56 {
  57    CmListEnt *next;                /* next entry in list */
  58    CmListEnt *prev;                /* prev entry in list */
  59 };
  60
  61 #ifdef CM_MT_HASH_BIN
  62 typedef struct cmListBinEnt CmListBinEnt;/* Bin entry */
  63
  64 struct cmListBinEnt                /* Bin entry */
  65 {
  66    CmListEnt *next;                /* next entry in list */
  67    CmListEnt *prev;                /* prev entry in list */
  68    uint16_t nmbEnt;                     /* current number of entries */
  69 };
  70 #endif
  71
  72
  73 /* hash list entry */
  74
  75 typedef struct cmHashListEnt       /* hash list entry */
  76 {
  77    CmListEnt list;                 /* list pointers */
  78    uint8_t  *key;                       /* pointer to key */
  79    uint16_t keyLen;                     /* length of key */
  80    uint16_t hashVal;                    /* computed hash value */
  81 } CmHashListEnt;
  82
  83 /* hash list control point */
  84
  85 struct cmHashListCp        /*  hash list control point */
  86 {
  87 #ifndef CM_MT_HASH_BIN
  88    CmListEnt *hl;                  /* pointer to hash list bins */
  89 #else
  90    CmListBinEnt *hl;               /* pointer to hash list bins */
  91 #endif
  92    Region region;                  /* memory region to allocate bins */
  93    Pool pool;                      /* memory pool to allocate bins */
  94    uint16_t nmbBins;                    /* number of hash list bins */
  95    uint16_t binBitMask;                 /* number of bits if nmbBins is power of 2 */
  96    uint8_t  nmbBinBits;                 /* number of bits to represent nmbBins */
  97 #ifndef CM_MT_HASH_BIN
  98    uint16_t nmbEnt;                     /* current number of entries */
  99 #endif
 100    uint16_t offset;                     /* offset of CmHashListEnt in entries */
 101    Bool dupFlg;                    /* allow duplicate keys */
 102    uint16_t  keyType;                   /* key type for selecting hash functions */
 103    CmHashFunc hashFunc;            /* hash function for this key type */
 104 };
 105
 106 \f
 107 /* functions prototypes */
 108
 109 S16 cmHashListInit ARGS((
 110               CmHashListCp *hashListCp,  /* hash list to initialize */
 111               uint16_t          nmbBins,      /* number of hash list bins */
 112               uint16_t          offset,       /* offset of CmHashListEnt in entries */
 113               Bool         dupFlg,       /* allow duplicate keys */
 114               uint16_t          keyType,      /* key type for selecting hash fn */
 115               Region       region,       /* memory region to allocate bins */
 116               Pool         pool));       /* memory pool to allocate bins */
 117
 118 S16 cmHashListDeinit ARGS((
 119               CmHashListCp *hashListCp));/* hash list to initialize */
 120
 121 S16 cmHashListInsert ARGS((
 122               CmHashListCp *hashListCp,  /* hash list to add to */
 123               PTR          entry,        /* entry to add */
 124               uint8_t           *key,         /* pointer to key */
 125               uint16_t          keyLen));     /* length of key */
 126
 127 S16 cmHashListDelete ARGS((
 128               CmHashListCp *hashListCp,  /* hash list to delete from */
 129               PTR          entry));      /* entry to delete */
 130
 131 S16 cmHashListFind ARGS((
 132               CmHashListCp *hashListCp,  /* hash list to search */
 133               uint8_t           *key,         /* pointer to key */
 134               uint16_t          keyLen,       /* length of key */
 135               uint16_t          seqNmb,       /* used in case of duplicate keys */
 136               PTR          *entry));     /* entry to be returned */
 137
 138 S16 cmHashListGetNext ARGS((
 139               CmHashListCp *hashListCp,    /* hash list to get from */
 140               PTR          prevEnt,        /* previous entry */
 141               PTR          *entry));       /* entry to be returned */
 142
 143 #ifdef CM_MT_HASH_BIN
 144 S16 cmHashListBinGetNextEntry ARGS((
 145               CmHashListCp *hashListCp,    /* hash list to get from */
 146               uint16_t          binIdx,         /* Index of the bin */
 147               PTR          prevEnt,        /* previous entry */
 148               PTR          *entry));       /* entry to be returned */
 149 #endif
 150
 151 /* This function is obsoleted! Use macros defined in cm_hash.h instead
 152  */
 153 S16 cmHashListQuery ARGS((
 154               CmHashListCp *hashListCp,    /* hash list to query */
 155               uint8_t           queryType,      /* type of query */
 156               uint16_t          *result));      /* result of query */
 157
 158 /* Hash list with open addressing
 159  */
 160 S16 cmHashListOAInsert ARGS((
 161               CmHashListCp *hashListCp,  /* hash list to add to */
 162               PTR          entry,        /* entry to add */
 163               uint8_t           *key,         /* pointer to key */
 164               uint16_t          keyLen));     /* length of key */
 165
 166 #ifdef __cplusplus
 167 }
 168 #endif
 169
 170 #endif /* __CMHASHX__ */
 171
 172 \f
 173 /********************************************************************30**
 174
 175          End of file
 176 **********************************************************************/