nis-util  1.0.D108
lib/symtab.cc
Go to the documentation of this file.
00001 //
00002 // nis-util - NIS Administration Utilities
00003 // Copyright (C) 2001, 2002, 2008, 2009, 2011, 2012 Peter Miller
00004 //
00005 // This program is free software; you can redistribute it and/or modify
00006 // it under the terms of the GNU General Public License as published by
00007 // the Free Software Foundation; either version 2 of the License, or (at
00008 // your option) any later version.
00009 //
00010 // This program is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013 // General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU General Public License
00016 // along with this program. If not, see <http://www.gnu.org/licenses/>.
00017 //
00018 
00019 #include <lib/ac/stdlib.h>
00020 #include <libexplain/malloc.h>
00021 #include <libexplain/output.h>
00022 #include <libexplain/realloc.h>
00023 
00024 #include <lib/symtab.h>
00025 
00026 
00027 symtab::~symtab()
00028 {
00029     for (hash_ty j = 0; j < hash_modulus; ++j)
00030     {
00031         row_ty **rpp = &hash_table[j];
00032         while (*rpp)
00033         {
00034             row_ty *rp = *rpp;
00035             *rpp = rp->overflow;
00036             if (reap)
00037                 reap(rp->data);
00038             delete rp;
00039         }
00040     }
00041     free(hash_table);
00042 }
00043 
00044 
00045 symtab::symtab()
00046 {
00047     hash_ty size = 5;
00048     reap = 0;
00049     hash_modulus = 1 << 2; // MUST be a power of 2
00050     while (hash_modulus < size)
00051         hash_modulus <<= 1;
00052     hash_cutover = hash_modulus;
00053     hash_split = hash_modulus - hash_cutover;
00054     hash_cutover_mask = hash_cutover - 1;
00055     hash_cutover_split_mask = (hash_cutover * 2) - 1;
00056     hash_load = 0;
00057     hash_table =
00058         (row_ty **)explain_malloc_or_die(hash_modulus * sizeof(row_ty *));
00059     for (hash_ty j = 0; j < hash_modulus; ++j)
00060         hash_table[j] = 0;
00061 }
00062 
00063 
00064 void
00065 symtab::split(void)
00066 {
00067     //
00068     // get the list to be split across buckets
00069     //
00070     row_ty *p = hash_table[hash_split];
00071     hash_table[hash_split] = 0;
00072 
00073     //
00074     // increase the modulus by one
00075     //
00076     hash_modulus++;
00077     hash_table =
00078         (row_ty **)
00079         explain_realloc_or_die(hash_table, hash_modulus * sizeof(row_ty *));
00080     hash_table[hash_modulus - 1] = 0;
00081     hash_split = hash_modulus - hash_cutover;
00082     if (hash_split >= hash_cutover)
00083     {
00084         hash_cutover = hash_modulus;
00085         hash_split = 0;
00086         hash_cutover_mask = hash_cutover - 1;
00087         hash_cutover_split_mask = (hash_cutover * 2) - 1;
00088     }
00089 
00090     //
00091     // now redistribute the list elements
00092     //
00093     // It is important to preserve the order of the links because
00094     // they can be push-down stacks, and to simply add them to the
00095     // head of the list will reverse the order of the stack!
00096     //
00097     while (p)
00098     {
00099         row_ty *p2 = p;
00100         p = p2->overflow;
00101         p2->overflow = 0;
00102 
00103         hash_ty index = p2->key.get_hash() & hash_cutover_mask;
00104         if (index < hash_split)
00105         {
00106             index =
00107                 (
00108                     p2->key.get_hash()
00109                 &
00110                     hash_cutover_split_mask
00111                 );
00112         }
00113         row_ty **ipp;
00114         for
00115         (
00116             ipp = &hash_table[index];
00117             *ipp;
00118             ipp = &(*ipp)->overflow
00119         )
00120             ;
00121         *ipp = p2;
00122     }
00123 }
00124 
00125 
00126 void *
00127 symtab::query(const rcstring &key)
00128     const
00129 {
00130     hash_ty index = key.get_hash() & hash_cutover_mask;
00131     if (index < hash_split)
00132         index = key.get_hash() & hash_cutover_split_mask;
00133     for (row_ty *p = hash_table[index]; p; p = p->overflow)
00134     {
00135         if (key == p->key)
00136             return p->data;
00137     }
00138     return 0;
00139 }
00140 
00141 
00142 void
00143 symtab::assign(const rcstring &key, void *data)
00144 {
00145     hash_ty index = key.get_hash() & hash_cutover_mask;
00146     if (index < hash_split)
00147         index = key.get_hash() & hash_cutover_split_mask;
00148     for (row_ty *p = hash_table[index]; p; p = p->overflow)
00149     {
00150         if (key == p->key)
00151         {
00152             if (reap)
00153                 reap(p->data);
00154             p->data = data;
00155             return;
00156         }
00157     }
00158 
00159     row_ty *np = new row_ty;
00160     np->key = key;
00161     np->overflow = hash_table[index];
00162     np->data = data;
00163     hash_table[index] = np;
00164 
00165     hash_load++;
00166     while (hash_load * 10 >= hash_modulus * 8)
00167         split();
00168 }
00169 
00170 
00171 void
00172 symtab::remove(const rcstring &key)
00173 {
00174     hash_ty index = key.get_hash() & hash_cutover_mask;
00175     if (index < hash_split)
00176         index = key.get_hash() & hash_cutover_split_mask;
00177 
00178     row_ty **pp = &hash_table[index];
00179     for (;;)
00180     {
00181         row_ty *p = *pp;
00182         if (!p)
00183             break;
00184         if (key == p->key)
00185         {
00186             if (reap)
00187                 reap(p->data);
00188             *pp = p->overflow;
00189             delete p;
00190             hash_load--;
00191             break;
00192         }
00193         pp = &p->overflow;
00194     }
00195 }
00196 
00197 
00198 void
00199 symtab::dump(const char *caption)
00200     const
00201 {
00202     explain_output_error("symbol table %s = {", caption);
00203     for (hash_ty j = 0; j < hash_modulus; ++j)
00204     {
00205         for (row_ty *p = hash_table[j]; p; p = p->overflow)
00206         {
00207             explain_output_error
00208             (
00209                 "key = \"%s\", data = %08lX",
00210                 p->key.c_str(),
00211                 (long)p->data
00212             );
00213         }
00214     }
00215     explain_output_error("}");
00216 }
00217 
00218 
00219 void
00220 symtab::walk(walk_t &arg)
00221 {
00222     for (hash_ty j = 0; j < hash_modulus; ++j)
00223         for (row_ty *p = hash_table[j]; p; p = p->overflow)
00224             arg.action(p->key, p->data);
00225 }
00226 
00227 
00228 symtab::key_list_t
00229 symtab::keys()
00230     const
00231 {
00232     symtab::key_list_t result;
00233     for (hash_ty j = 0; j < hash_modulus; ++j)
00234         for (row_ty *p = hash_table[j]; p; p = p->overflow)
00235             result.push_back(p->key);
00236     return result;
00237 }
00238 
00239 
00240 void
00241 symtab::set_reaper(void (*fp)(void *))
00242 {
00243     reap = fp;
00244 }
00245 
00246 
00247 // vim: set ts=8 sw=4 et :