src/ulut/ulut/ul_hashtabprim.c

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_hashtabprim.c      - primitives to support hash tables
   5
   6   (C) Copyright 2009 by Pavel Pisa - Originator
   7
   8   The uLan utilities library can be used, copied and modified under
   9   next licenses
  10     - GPL - GNU General Public License
  11     - LGPL - GNU Lesser General Public License
  12     - MPL - Mozilla Public License
  13     - and other licenses added by project originators
  14   Code can be modified and re-distributed under any combination
  15   of the above listed licenses. If contributor does not agree with
  16   some of the licenses, he/she can delete appropriate line.
  17   Warning, if you delete all lines, you are not allowed to
  18   distribute source code and/or binaries utilizing code.
  19
  20   See files COPYING and README for details.
  21
  22  *******************************************************************/
  23
  24 #include <string.h>
  25 #include "ul_utmalloc.h"
  26 #include "ul_hashtab.h"
  27
  28 void ul_hashtab_init_table_field_primitive(ul_hashtab_cust_table_field_t *table_field)
  29 {
  30   table_field->hashmask=0;
  31   table_field->count=0;
  32   table_field->treeroots.treesingle.treeroot=NULL;
  33 }
  34
  35 int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field)
  36 {
  37   if(table_field->hashmask)
  38     free(table_field->treeroots.treetable);
  39   table_field->sizestep=0;
  40   table_field->hashmask=0;
  41   table_field->count=0;
  42   table_field->treeroots.treesingle.treeroot=NULL;
  43   return 0;
  44 }
  45
  46 int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field,
  47                 ul_hashtab_hashval_t newsize, ul_hashtab_resize_insert_fnc_t *ins_fnc)
  48 {
  49   ul_hashtab_hashval_t oldsize=table_field->hashmask+1;
  50   ul_hashtab_treeroot_t oldsingle;
  51   ul_hashtab_treeroot_t *pt;
  52   ul_hashtab_treeroot_t *oldtable;
  53   gavl_node_t *treenode;
  54   int res;
  55
  56   if(newsize<=0)
  57     newsize=1;
  58
  59   if(oldsize>1) {
  60     oldtable=table_field->treeroots.treetable;
  61   } else {
  62     oldsingle.treeroot=table_field->treeroots.treesingle.treeroot;
  63     oldtable=NULL;
  64   }
  65
  66   if(newsize>1) {
  67     pt=malloc(sizeof(*pt)*newsize);
  68     if(pt==NULL)
  69       return -1;
  70     memset(pt,0,sizeof(*pt)*newsize);
  71     table_field->treeroots.treetable=pt;
  72   } else {
  73     table_field->treeroots.treesingle.treeroot=NULL;
  74   }
  75   table_field->hashmask=newsize-1;
  76
  77   pt = oldtable!=NULL? oldtable: &oldsingle;
  78
  79   while(oldsize--) {
  80     while(pt->treeroot!=NULL) {
  81       treenode=gavl_cut_first_primitive(&pt->treeroot);
  82       res=ins_fnc(table_field, treenode);
  83     }
  84     pt++;
  85   }
  86
  87   if(oldtable)
  88     free(oldtable);
  89
  90   return 0;
  91 }
  92
  93 gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *table_field,
  94         ul_hashtab_treeroot_t **pptreeroot, gavl_node_t *treenode)
  95 {
  96   if(treenode!=NULL) {
  97     treenode=gavl_next_node(treenode);
  98     if((treenode!=NULL) || !table_field->hashmask)
  99       return treenode;
 100     if(table_field->treeroots.treetable+table_field->hashmask==*pptreeroot)
 101       return treenode;
 102     (*pptreeroot)++;
 103   } else {
 104     if(!table_field->hashmask) {
 105       const ul_hashtab_treeroot_t *treeroot=&table_field->treeroots.treesingle;
 106       *pptreeroot=(ul_hashtab_treeroot_t *)treeroot;
 107     } else {
 108       *pptreeroot=table_field->treeroots.treetable;
 109     }
 110   }
 111   do {
 112     if(*pptreeroot) {
 113       treenode=(*pptreeroot)->treeroot;
 114       if(treenode)
 115         while(treenode->left!=NULL)
 116           treenode=treenode->left;
 117       if(treenode!=NULL)
 118         return treenode;
 119     }
 120     if(!table_field->hashmask)
 121       return treenode;
 122     if(table_field->treeroots.treetable+table_field->hashmask==*pptreeroot)
 123       return treenode;
 124     (*pptreeroot)++;
 125   } while (1);
 126 }
 127
 128 #undef TABENT
 129 #define TABENT(pow) ((ul_hashtab_hashval_t)(1l<<(pow)))
 130
 131 static const ul_hashtab_sizestep_t ul_hashtab_sizestep_default_table[]={
 132   { ((ul_hashtab_hashval_t)~0l)<(1l<<8)?2:
 133     ((ul_hashtab_hashval_t)~0l)<(1l<<16)?5:8,
 134                TABENT( 2), TABENT( 0)},
 135   {TABENT( 0), TABENT( 4), TABENT( 4)},
 136   {TABENT( 3), TABENT( 6), TABENT( 6)},
 137   {TABENT( 5), TABENT( 8), TABENT( 8)},
 138   {TABENT( 7), TABENT(11), TABENT(10)},
 139   {TABENT(10), TABENT(14), TABENT(12)},
 140   {TABENT(13), TABENT(18), TABENT(14)},
 141   {TABENT(17), TABENT(21), TABENT(16)},
 142   {TABENT(16),         0,  TABENT(18)},
 143 };
 144
 145 const ul_hashtab_sizestep_t * const ul_hashtab_sizestep_default=ul_hashtab_sizestep_default_table;
 146 const ul_hashtab_sizestep_t *ul_hashtab_sizestep_global=ul_hashtab_sizestep_default_table;