Branch data     Line data    Source code

       1                 :            : #include "vqueue.h"
       2                 :            : #include "fch_buckets.h"
       3                 :            : #include <stdio.h>
       4                 :            : #include <assert.h>
       5                 :            : #include <stdlib.h>
       6                 :            : //#define DEBUG
       7                 :            : #include "debug.h"
       8                 :            : 
       9                 :            : typedef struct __fch_bucket_entry_t
      10                 :            : {
      11                 :            :   char * value;
      12                 :            :   cmph_uint32 length;
      13                 :            : } fch_bucket_entry_t;
      14                 :            : 
      15                 :            : typedef struct __fch_bucket_t
      16                 :            : {
      17                 :            :   fch_bucket_entry_t * entries;
      18                 :            :   cmph_uint32 capacity, size;
      19                 :            : } fch_bucket_t;
      20                 :            : 
      21                 :            : 
      22                 :            : 
      23                 :          0 : static void fch_bucket_new(fch_bucket_t *bucket) 
      24                 :            : {
      25         [ #  # ]:          0 :         assert(bucket);
      26                 :          0 :         bucket->size = 0;
      27                 :          0 :         bucket->entries = NULL;
      28                 :          0 :         bucket->capacity = 0;
      29                 :          0 : }
      30                 :            : 
      31                 :          0 : static void fch_bucket_destroy(fch_bucket_t *bucket)
      32                 :            : {
      33                 :            :         cmph_uint32 i;
      34         [ #  # ]:          0 :         assert(bucket);
      35         [ #  # ]:          0 :         for (i = 0; i < bucket->size; i++)
      36                 :            :         {
      37                 :          0 :                 free((bucket->entries + i)->value);
      38                 :            :         }
      39                 :          0 :         free(bucket->entries);
      40                 :          0 : }
      41                 :            : 
      42                 :            : 
      43                 :          0 : static void fch_bucket_reserve(fch_bucket_t *bucket, cmph_uint32 size)
      44                 :            : {
      45         [ #  # ]:          0 :         assert(bucket);
      46         [ #  # ]:          0 :         if (bucket->capacity < size)
      47                 :            :         {
      48                 :          0 :                 cmph_uint32 new_capacity = bucket->capacity + 1;
      49                 :            :                 DEBUGP("Increasing current capacity %u to %u\n", bucket->capacity, size);
      50         [ #  # ]:          0 :                 while (new_capacity < size)
      51                 :            :                 {
      52                 :          0 :                         new_capacity *= 2;
      53                 :            :                 }
      54                 :          0 :                 bucket->entries = (fch_bucket_entry_t *)realloc(bucket->entries, sizeof(fch_bucket_entry_t)*new_capacity);
      55         [ #  # ]:          0 :                 assert(bucket->entries);
      56                 :          0 :                 bucket->capacity = new_capacity;
      57                 :            :                 DEBUGP("Increased\n");
      58                 :            :         }
      59                 :          0 : }
      60                 :            : 
      61                 :          0 : static void fch_bucket_insert(fch_bucket_t *bucket, char *val, cmph_uint32 val_length)
      62                 :            : {
      63         [ #  # ]:          0 :         assert(bucket);
      64                 :          0 :         fch_bucket_reserve(bucket, bucket->size + 1);
      65                 :          0 :         (bucket->entries + bucket->size)->value = val;
      66                 :          0 :         (bucket->entries + bucket->size)->length = val_length;
      67                 :          0 :         ++(bucket->size);
      68                 :          0 : }
      69                 :            : 
      70                 :            : 
      71                 :          0 : static cmph_uint8 fch_bucket_is_empty(fch_bucket_t *bucket)
      72                 :            : {
      73         [ #  # ]:          0 :         assert(bucket);
      74                 :          0 :         return (cmph_uint8)(bucket->size == 0);
      75                 :            : }
      76                 :            : 
      77                 :          0 : static cmph_uint32 fch_bucket_size(fch_bucket_t *bucket)
      78                 :            : {
      79         [ #  # ]:          0 :         assert(bucket);
      80                 :          0 :         return bucket->size;
      81                 :            : }
      82                 :            : 
      83                 :          0 : static char * fch_bucket_get_key(fch_bucket_t *bucket, cmph_uint32 index_key)
      84                 :            : {
      85   [ #  #  #  # ]:          0 :         assert(bucket); assert(index_key < bucket->size);
      86                 :          0 :         return (bucket->entries + index_key)->value;
      87                 :            : }
      88                 :            : 
      89                 :          0 : static cmph_uint32 fch_bucket_get_length(fch_bucket_t *bucket, cmph_uint32 index_key)
      90                 :            : {
      91   [ #  #  #  # ]:          0 :         assert(bucket); assert(index_key < bucket->size);
      92                 :          0 :         return (bucket->entries + index_key)->length;
      93                 :            : }
      94                 :            : 
      95                 :          0 : static void fch_bucket_print(fch_bucket_t * bucket, cmph_uint32 index)
      96                 :            : {
      97                 :            :         cmph_uint32 i;
      98         [ #  # ]:          0 :         assert(bucket);
      99                 :          0 :         fprintf(stderr, "Printing bucket %u ...\n", index);
     100         [ #  # ]:          0 :         for (i = 0; i < bucket->size; i++)
     101                 :            :         {
     102                 :          0 :                 fprintf(stderr, "  key: %s\n", (bucket->entries + i)->value);
     103                 :            :         }
     104                 :          0 : }
     105                 :            : 
     106                 :            : //////////////////////////////////////////////////////////////////////////////////////
     107                 :            : 
     108                 :            : struct __fch_buckets_t
     109                 :            : {
     110                 :            :   fch_bucket_t * values;
     111                 :            :   cmph_uint32 nbuckets, max_size;
     112                 :            :   
     113                 :            : };
     114                 :            : 
     115                 :          0 : fch_buckets_t * fch_buckets_new(cmph_uint32 nbuckets)
     116                 :            : {
     117                 :            :         cmph_uint32 i;
     118                 :          0 :         fch_buckets_t *buckets = (fch_buckets_t *)malloc(sizeof(fch_buckets_t));
     119         [ #  # ]:          0 :         assert(buckets);
     120                 :          0 :         buckets->values = (fch_bucket_t *)calloc((size_t)nbuckets, sizeof(fch_bucket_t));
     121         [ #  # ]:          0 :         for (i = 0; i < nbuckets; i++) fch_bucket_new(buckets->values + i); 
     122         [ #  # ]:          0 :         assert(buckets->values);
     123                 :          0 :         buckets->nbuckets = nbuckets;
     124                 :          0 :         buckets->max_size = 0;
     125                 :          0 :         return buckets;
     126                 :            : }
     127                 :            : 
     128                 :          0 : cmph_uint8 fch_buckets_is_empty(fch_buckets_t * buckets, cmph_uint32 index)
     129                 :            : {
     130         [ #  # ]:          0 :         assert(index < buckets->nbuckets);
     131                 :          0 :         return fch_bucket_is_empty(buckets->values + index);
     132                 :            : }
     133                 :            : 
     134                 :          0 : void fch_buckets_insert(fch_buckets_t * buckets, cmph_uint32 index, char * key, cmph_uint32 length)
     135                 :            : {
     136         [ #  # ]:          0 :         assert(index < buckets->nbuckets);
     137                 :          0 :         fch_bucket_insert(buckets->values + index, key, length);
     138         [ #  # ]:          0 :         if (fch_bucket_size(buckets->values + index) > buckets->max_size) 
     139                 :            :         {
     140                 :          0 :                 buckets->max_size = fch_bucket_size(buckets->values + index);
     141                 :            :         }
     142                 :          0 : }
     143                 :            : 
     144                 :          0 : cmph_uint32 fch_buckets_get_size(fch_buckets_t * buckets, cmph_uint32 index)
     145                 :            : {
     146         [ #  # ]:          0 :         assert(index < buckets->nbuckets);
     147                 :          0 :         return fch_bucket_size(buckets->values + index);
     148                 :            : }
     149                 :            : 
     150                 :            : 
     151                 :          0 : char * fch_buckets_get_key(fch_buckets_t * buckets, cmph_uint32 index, cmph_uint32 index_key)
     152                 :            : {
     153         [ #  # ]:          0 :         assert(index < buckets->nbuckets);
     154                 :          0 :         return fch_bucket_get_key(buckets->values + index, index_key);
     155                 :            : }
     156                 :            : 
     157                 :          0 : cmph_uint32 fch_buckets_get_keylength(fch_buckets_t * buckets, cmph_uint32 index, cmph_uint32 index_key)
     158                 :            : {
     159         [ #  # ]:          0 :         assert(index < buckets->nbuckets);
     160                 :          0 :         return fch_bucket_get_length(buckets->values + index, index_key);
     161                 :            : }
     162                 :            : 
     163                 :          0 : cmph_uint32 fch_buckets_get_max_size(fch_buckets_t * buckets)
     164                 :            : {
     165                 :          0 :         return buckets->max_size;
     166                 :            : }
     167                 :            : 
     168                 :          0 : cmph_uint32 fch_buckets_get_nbuckets(fch_buckets_t * buckets)
     169                 :            : {
     170                 :          0 :         return buckets->nbuckets;
     171                 :            : }
     172                 :            : 
     173                 :          0 : cmph_uint32 * fch_buckets_get_indexes_sorted_by_size(fch_buckets_t * buckets) 
     174                 :            : {
     175                 :          0 :         cmph_uint32 i = 0;
     176                 :          0 :         cmph_uint32 sum = 0, value;
     177                 :          0 :         cmph_uint32 *nbuckets_size = (cmph_uint32 *) calloc((size_t)buckets->max_size + 1, sizeof(cmph_uint32));
     178                 :          0 :         cmph_uint32 * sorted_indexes = (cmph_uint32 *) calloc((size_t)buckets->nbuckets, sizeof(cmph_uint32));
     179                 :            :         
     180                 :            :         // collect how many buckets for each size.
     181         [ #  # ]:          0 :         for(i = 0; i < buckets->nbuckets; i++) nbuckets_size[fch_bucket_size(buckets->values + i)] ++;
     182                 :            :         
     183                 :            :         // calculating offset considering a decreasing order of buckets size.
     184                 :          0 :         value = nbuckets_size[buckets->max_size];
     185                 :          0 :         nbuckets_size[buckets->max_size] = sum;
     186                 :          0 :         for(i = (int)buckets->max_size - 1; i >= 0; i--)
     187                 :            :         {
     188                 :          0 :                 sum += value;
     189                 :          0 :                 value = nbuckets_size[i];
     190                 :          0 :                 nbuckets_size[i] = sum;
     191                 :            :                 
     192                 :            :         }
     193                 :            :         for(i = 0; i < buckets->nbuckets; i++) 
     194                 :            :         {
     195                 :            :                 sorted_indexes[nbuckets_size[fch_bucket_size(buckets->values + i)]] = (cmph_uint32)i;
     196                 :            :                 nbuckets_size[fch_bucket_size(buckets->values + i)] ++;
     197                 :            :         }       
     198                 :            :         free(nbuckets_size);
     199                 :            :         return sorted_indexes;
     200                 :            : }
     201                 :            : 
     202                 :          0 : void fch_buckets_print(fch_buckets_t * buckets)
     203                 :            : {
     204                 :            :         cmph_uint32 i;
     205         [ #  # ]:          0 :         for (i = 0; i < buckets->nbuckets; i++) fch_bucket_print(buckets->values + i, i);
     206                 :          0 : }
     207                 :            : 
     208                 :          0 : void fch_buckets_destroy(fch_buckets_t * buckets)
     209                 :            : {
     210                 :            :         cmph_uint32 i;
     211         [ #  # ]:          0 :         for (i = 0; i < buckets->nbuckets; i++) fch_bucket_destroy(buckets->values + i); 
     212                 :          0 :         free(buckets->values);
     213                 :          0 :         free(buckets);
     214                 :          0 : }