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->hashmask=0;
  40   table_field->count=0;
  41   table_field->treeroots.treesingle.treeroot=NULL;
  42   return 0;
  43 }
  44
  45 int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field,
  46                 ul_hashtab_hashval_t newsize, ul_hashtab_resize_insert_fnc_t *ins_fnc)
  47 {
  48   ul_hashtab_hashval_t oldsize=table_field->hashmask+1;
  49   ul_hashtab_treeroot_t oldsingle;
  50   ul_hashtab_treeroot_t *pt;
  51   ul_hashtab_treeroot_t *oldtable;
  52   gavl_node_t *treenode;
  53   int res;
  54
  55   if(newsize<=0)
  56     newsize=1;
  57
  58   if(oldsize>1) {
  59     oldtable=table_field->treeroots.treetable;
  60   } else {
  61     oldsingle.treeroot=table_field->treeroots.treesingle.treeroot;
  62     oldtable=NULL;
  63   }
  64
  65   if(newsize>1) {
  66     pt=malloc(sizeof(*pt)*newsize);
  67     if(pt==NULL)
  68       return -1;
  69     memset(pt,0,sizeof(*pt)*newsize);
  70     table_field->treeroots.treetable=pt;
  71   } else {
  72     table_field->treeroots.treesingle.treeroot=NULL;
  73   }
  74   table_field->hashmask=newsize-1;
  75
  76   pt = oldtable!=NULL? oldtable: &oldsingle;
  77
  78   while(oldsize--) {
  79     while(pt->treeroot!=NULL) {
  80       treenode=gavl_cut_first_primitive(&pt->treeroot);
  81       res=ins_fnc(table_field, treenode);
  82     }
  83     pt++;
  84   }
  85
  86   if(oldtable)
  87     free(oldtable);
  88
  89   return 0;
  90 }
  91
  92 gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *table_field,
  93         ul_hashtab_treeroot_t **pptreeroot, gavl_node_t *treenode)
  94 {
  95   if(treenode!=NULL) {
  96     treenode=gavl_next_node(treenode);
  97     if((treenode!=NULL) || !table_field->hashmask)
  98       return treenode;
  99     if(table_field->treeroots.treetable+table_field->hashmask==*pptreeroot)
 100       return treenode;
 101     (*pptreeroot)++;
 102   } else {
 103     if(!table_field->hashmask) {
 104       const ul_hashtab_treeroot_t *treeroot=&table_field->treeroots.treesingle;
 105       *pptreeroot=(ul_hashtab_treeroot_t *)treeroot;
 106     } else {
 107       *pptreeroot=table_field->treeroots.treetable;
 108     }
 109   }
 110   do {
 111     if(*pptreeroot) {
 112       treenode=(*pptreeroot)->treeroot;
 113       if(treenode)
 114         while(treenode->left!=NULL)
 115           treenode=treenode->left;
 116       if(treenode!=NULL)
 117         return treenode;
 118     }
 119     if(!table_field->hashmask)
 120       return treenode;
 121     if(table_field->treeroots.treetable+table_field->hashmask==*pptreeroot)
 122       return treenode;
 123     (*pptreeroot)++;
 124   } while (1);
 125 }