drivers/misc/mediatek/gpu/ged/src/ged_hashtable.c

   1 #include "ged_base.h"
   2 #include "ged_hashtable.h"
   3 #include <linux/hashtable.h>
   4
   5 typedef struct GED_HASHTABLE_TAG
   6 {
   7     unsigned int        ui32Bits;
   8     unsigned int        ui32Length;
   9     unsigned int        ui32CurrentID;
  10     unsigned int        ui32Count;
  11     struct hlist_head*  psHashTable;
  12 } GED_HASHTABLE;
  13
  14 typedef struct GED_HASHNODE_TAG
  15 {
  16     unsigned int        ui32ID;
  17     void*               pvoid;
  18     struct hlist_node   sNode;
  19 } GED_HASHNODE;
  20
  21 #define GED_HASHTABLE_INIT_ID 1234 // 0 = invalid
  22
  23 void* __ged_hashtable_find(struct hlist_head *head, unsigned int ui32ID)
  24 {
  25     GED_HASHNODE* psHN;
  26     hlist_for_each_entry_rcu(psHN, head, sNode)
  27     {
  28         if (psHN->ui32ID == ui32ID)
  29         {
  30             return psHN;
  31         }
  32     }
  33     return NULL;
  34 }
  35
  36 static int ged_hash(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
  37 {
  38     GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
  39     return hash_32(ui32ID, psHT->ui32Bits);
  40 }
  41
  42 GED_HASHTABLE_HANDLE ged_hashtable_create(unsigned int ui32Bits)
  43 {
  44     GED_HASHTABLE* psHT;
  45     unsigned int i;
  46
  47     if (ui32Bits > 20)
  48     {
  49         // 1048576 slots !?
  50         // Need to check the necessary
  51         return NULL;
  52     }
  53
  54     psHT = (GED_HASHTABLE*)ged_alloc(sizeof(GED_HASHTABLE));
  55     if (psHT)
  56     {
  57         psHT->ui32Bits = ui32Bits;
  58         psHT->ui32Length = 1 << ui32Bits;
  59         psHT->ui32CurrentID = GED_HASHTABLE_INIT_ID; // 0 = invalid
  60         psHT->psHashTable = (struct hlist_head*)ged_alloc(psHT->ui32Length * sizeof(struct hlist_head));
  61         if (psHT->psHashTable)
  62         {
  63             for (i = 0; i < psHT->ui32Length; i++)
  64             {
  65                 INIT_HLIST_HEAD(&psHT->psHashTable[i]);
  66             }
  67             return (GED_HASHTABLE_HANDLE)psHT;
  68         }
  69     }
  70
  71     ged_hashtable_destroy(psHT);
  72     return NULL;
  73 }
  74
  75 void ged_hashtable_destroy(GED_HASHTABLE_HANDLE hHashTable)
  76 {
  77     GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
  78     if (psHT)
  79     {
  80         int i = 0;
  81         while(psHT->ui32Count > 0)
  82         {
  83             unsigned int ui32ID = 0;
  84             GED_HASHNODE* psHN;
  85             // get one to be freed
  86             for (;i < psHT->ui32Length; i++)
  87             {
  88                 struct hlist_head *head = &psHT->psHashTable[i];
  89                 hlist_for_each_entry_rcu(psHN, head, sNode)
  90                 {
  91                     ui32ID = psHN->ui32ID;
  92                     break;
  93                 }
  94                 if (0 < ui32ID)
  95                 {
  96                     break;
  97                 }
  98             }
  99
 100             if (i >= psHT->ui32Length)
 101             {
 102                 break;
 103             }
 104
 105             ged_hashtable_remove(psHT, ui32ID);
 106         }
 107
 108         /* free the hash table */
 109         ged_free(psHT->psHashTable, psHT->ui32Length * sizeof(struct hlist_head));
 110         ged_free(psHT, sizeof(GED_HASHTABLE));
 111     }
 112 }
 113
 114 GED_ERROR ged_hashtable_insert(GED_HASHTABLE_HANDLE hHashTable, void* pvoid, unsigned int* pui32ID)
 115 {
 116     GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
 117     GED_HASHNODE* psHN = NULL;
 118     unsigned int ui32Hash, ui32ID;
 119
 120     if ((!psHT) || (!pui32ID))
 121     {
 122         return GED_ERROR_INVALID_PARAMS;
 123     }
 124
 125     ui32ID = psHT->ui32CurrentID + 1;
 126     while(1)
 127     {
 128         ui32Hash = ged_hash(psHT, ui32ID);
 129         psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
 130         if (psHN != NULL)
 131         {
 132             ui32ID++;
 133             if (ui32ID == 0)//skip the value 0
 134             {
 135                 ui32ID = 1;
 136             }
 137             if (ui32ID == psHT->ui32CurrentID)
 138             {
 139                 return GED_ERROR_FAIL;
 140             }
 141         }
 142         else
 143         {
 144             break;
 145         }
 146     };
 147
 148     psHN = (GED_HASHNODE*)ged_alloc(sizeof(GED_HASHNODE));
 149     if (psHN)
 150     {
 151         psHN->pvoid = pvoid;
 152         psHN->ui32ID = ui32ID;
 153         psHT->ui32CurrentID = ui32ID;
 154         *pui32ID = ui32ID;
 155         hlist_add_head_rcu(&psHN->sNode, &psHT->psHashTable[ui32Hash]);
 156         psHT->ui32Count += 1;
 157         return GED_OK;
 158     }
 159
 160     return GED_ERROR_OOM;
 161 }
 162
 163 void ged_hashtable_remove(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
 164 {
 165     GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
 166     if (psHT)
 167     {
 168         unsigned int ui32Hash = ged_hash(psHT, ui32ID);
 169         GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
 170         if (psHN)
 171         {
 172             hlist_del_rcu(&psHN->sNode);
 173             synchronize_rcu();
 174             ged_free(psHN, sizeof(GED_HASHNODE));
 175             psHT->ui32Count -= 1;
 176         }
 177     }
 178 }
 179
 180 void* ged_hashtable_find(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
 181 {
 182     GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
 183     if (psHT)
 184     {
 185         unsigned int ui32Hash = ged_hash(psHT, ui32ID);
 186         GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
 187         if (psHN)
 188         {
 189             return psHN->pvoid;
 190         }
 191 #ifdef GED_DEBUG
 192         if (ui32ID != 0)
 193         {
 194             GED_LOGE("ged_hashtable_find: ui32ID=%u ui32Hash=%u psHN=%p\n", ui32ID, ui32Hash, psHN);
 195         }
 196 #endif
 197     }
 198     return NULL;
 199 }
 200
 201 GED_ERROR ged_hashtable_set(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID, void* pvoid)
 202 {
 203     GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
 204     if (psHT)
 205     {
 206         unsigned int ui32Hash = ged_hash(psHT, ui32ID);
 207         GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
 208         if (psHN)
 209         {
 210             psHN->pvoid = pvoid;
 211             return GED_OK;
 212         }
 213     }
 214
 215     return GED_ERROR_INVALID_PARAMS;
 216 }
 217