cde/lib/tt/lib/util/tt_object_table.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 //%%  (c) Copyright 1993, 1994 Hewlett-Packard Company
  24 //%%  (c) Copyright 1993, 1994 International Business Machines Corp.
  25 //%%  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
  26 //%%  (c) Copyright 1993, 1994 Novell, Inc.
  27 //%%  $XConsortium: tt_object_table.C /main/3 1995/10/23 10:42:52 rswiston $
  28 /* -*-C++-*-
  29  * @(#)tt_object_table.C        1.11 @(#)
  30  *
  31  * tt_object_table.cc
  32  *
  33  * Generic hash table implementation
  34  *
  35  * Copyright (c) 1990 by Sun Microsystems, Inc.
  36  */
  37
  38 #include "tt_options.h"
  39 #if defined(OPT_BUG_SUNOS_4) && defined(__GNUG__)
  40         // The GNU headers for 4.x do not fix malloc.h, so abort its inclusion
  41 #       define __malloc_h
  42 #endif
  43
  44 #include <util/tt_object_table.h>
  45
  46 /*
  47  * Table operations
  48  */
  49
  50 _Tt_object_table::
  51 _Tt_object_table(int n)
  52 {
  53         num_buckets = n;
  54         buckets = (_Tt_object_list_ptr *)calloc(n,
  55                                                 sizeof(_Tt_object_list_ptr));
  56         _count = 0;
  57 }
  58
  59 _Tt_object_table::
  60 ~_Tt_object_table()
  61 {
  62         for (int i = 0; i < num_buckets; i++) {
  63                 buckets[i] = (_Tt_object_list *)0;
  64         }
  65         (void)free((MALLOCTYPE *)buckets);
  66 }
  67
  68 _Tt_object_ptr & _Tt_object_table::
  69 lookup(const _Tt_string &k) const
  70 {
  71         _Tt_object_list_ptr bl = buckets[k.hash(num_buckets)];
  72
  73         if (!bl.is_null() && bl->count()!=0) {
  74                 _Tt_object_list_cursor b(bl);
  75                 while (b.next()) {
  76                         if ((*_getkey)(*b) == k) {
  77                                 return *b;
  78                         }
  79                 }
  80         }
  81         return _Tt_object::null_ptr();
  82 }
  83
  84 int _Tt_object_table::
  85 lookup(const _Tt_string &k, _Tt_object_ptr &obj) const
  86 {
  87         _Tt_object_list_ptr bl = buckets[k.hash(num_buckets)];
  88
  89         if (bl.is_null() || bl->count()==0) {
  90                 obj = (_Tt_object *)0;
  91                 return FALSE;
  92         }
  93         _Tt_object_list_cursor b(bl);
  94         while (b.next()) {
  95                 if ((*_getkey)(*b) == k) {
  96                         obj=*b;
  97                         return(TRUE);
  98                 }
  99         }
 100         obj = (_Tt_object *)0;
 101         return FALSE;
 102 }
 103
 104 void _Tt_object_table::
 105 insert(_Tt_object_ptr &n)
 106 {
 107         _Tt_string      key((*_getkey)(n));
 108         int bucket_no = key.hash(num_buckets);
 109
 110         if (buckets[bucket_no].is_null()) {
 111                 buckets[bucket_no] = new _Tt_object_list;
 112         }
 113         buckets[bucket_no]->push(n);
 114         ++_count;
 115 }
 116
 117
 118 void _Tt_object_table::
 119 remove(const _Tt_string &k)
 120 {
 121         _Tt_object_list_cursor b(buckets[k.hash(num_buckets)]);
 122         while (b.next()) {
 123                 if ((*_getkey)(*b) == k) {
 124                         b.remove();
 125                         --_count;
 126                         return;
 127                 }
 128         }
 129 }
 130
 131
 132 void _Tt_object_table::
 133 flush()
 134 {
 135         int i;
 136         for (i=0;i<num_buckets;++i) {
 137                 if (!buckets[i].is_null()) {
 138                         buckets[i] = (_Tt_object_list *)0;
 139                 }
 140         }
 141         _count = 0;
 142 }
 143
 144 void _Tt_object_table::
 145 print(_Tt_object_printfn print_elt, const _Tt_ostream &os) const
 146 {
 147         _Tt_object_table_ptr     t = (_Tt_object_table *)this;
 148         _Tt_object_table_cursor  c(t);
 149         while (c.next()) {
 150                 (*print_elt)(os, (*c).c_pointer());
 151         }
 152 }
 153
 154
 155 /*
 156  *  XDR encoding and decoding function for tables
 157  */
 158 bool_t _Tt_object_table::
 159 xdr(XDR *xdrs, _Tt_new_xdrfn xdrfn, _Tt_object *(*make_new)())
 160 {
 161         if (! xdr_int(xdrs, &_count)) {
 162                 return(0);
 163         }
 164         if (xdrs->x_op == XDR_ENCODE) {
 165                 _Tt_object_table_ptr t = this;
 166                 _Tt_object_table_cursor cursor(t);
 167                 while (cursor.next()) {
 168                         if ((*cursor).is_null()) {
 169                                 continue;
 170                         }
 171                         if (! (*xdrfn)(xdrs, (*cursor).c_pointer())) {
 172                                 return(0);
 173                         }
 174                 }
 175         } else {
 176                 int             i;
 177                 int             len;
 178                 _Tt_object_ptr  ptr;
 179
 180                 len = _count;
 181                 _count = 0;
 182                 for (i=len; i > 0; --i) {
 183                         ptr = (*make_new)();
 184                         if (! (*xdrfn)(xdrs, ptr.c_pointer())) {
 185                                 return(0);
 186                         } else {
 187                                 _Tt_object_ptr ptr2;
 188                                 int found = lookup((*_getkey)(ptr),ptr2);
 189                                 if (found==TRUE) {
 190                                         remove((*_getkey)(ptr));
 191                                 }
 192                                 insert(ptr);
 193                         }
 194                 }
 195         }
 196
 197         return(1);
 198 }
 199
 200
 201 /*
 202  * Cursor functions
 203  */
 204
 205 _Tt_object_table_cursor::
 206 _Tt_object_table_cursor()
 207 {
 208         table = (_Tt_object_table *)0;
 209         current_bucket = -1;
 210 }
 211
 212
 213 _Tt_object_table_cursor::
 214 _Tt_object_table_cursor(const _Tt_object_table_cursor &c)
 215 {
 216         table = c.table;
 217         listcursor = c.listcursor;
 218         current_bucket = c.current_bucket;
 219 }
 220
 221 _Tt_object_table_cursor::
 222 _Tt_object_table_cursor(const _Tt_object_table_ptr &l)
 223 {
 224         table = l;
 225         current_bucket = -1;
 226 }
 227
 228 _Tt_object_table_cursor::
 229 ~_Tt_object_table_cursor()
 230 {
 231 }
 232
 233 _Tt_object_table_cursor & _Tt_object_table_cursor::
 234 reset()
 235 {
 236         current_bucket = -1;
 237         return *this;
 238 }
 239
 240 _Tt_object_table_cursor & _Tt_object_table_cursor::
 241 reset(_Tt_object_table_ptr &l)
 242 {
 243         table = l;
 244         current_bucket = -1;
 245         return *this;
 246 }
 247
 248 _Tt_object_ptr & _Tt_object_table_cursor::
 249 operator*()
 250 {
 251         if (current_bucket == -1) {
 252                 return _Tt_object::null_ptr();
 253         } else {
 254                 return(*listcursor);
 255         }
 256 }
 257
 258 _Tt_object_ptr & _Tt_object_table_cursor::
 259 operator->()
 260 {
 261         return(*listcursor);
 262 }
 263
 264 int _Tt_object_table_cursor::
 265 next()
 266 {
 267         if (current_bucket == -1) {
 268                 current_bucket = 0;
 269                 listcursor.reset(table->buckets[current_bucket]);
 270         }
 271         while (!listcursor.next()) {
 272                 ++current_bucket;
 273                 if (current_bucket >= table->num_buckets) {
 274                         this->reset(table);
 275                         return 0;
 276                 } else {
 277                         listcursor.reset(table->buckets[current_bucket]);
 278                 }
 279         }
 280         return 1;
 281 }
 282
 283 int _Tt_object_table_cursor::
 284 prev()
 285 {
 286         if (current_bucket == -1) {
 287                 current_bucket = table->num_buckets-1;
 288                 listcursor.reset(table->buckets[current_bucket]);
 289         }
 290         while (!listcursor.prev()) {
 291                 --current_bucket;
 292                 if (current_bucket<0) {
 293                         this->reset(table);
 294                         return 0;
 295                 } else {
 296                         listcursor.reset(table->buckets[current_bucket]);
 297                 }
 298         }
 299         return 1;
 300 }
 301
 302 int _Tt_object_table_cursor::
 303 is_valid() const
 304 {
 305         if (current_bucket==-1) return 0;
 306         return listcursor.is_valid();
 307 }
 308 implement_ptr_to(_Tt_object_table)
 309
 310
 311