src/rmr/common/src/symtab.c

   1 // : vi ts=4 sw=4 noet :
   2 /*
   3 ==================================================================================
   4         Copyright (c) 2019 Nokia
   5         Copyright (c) 2018-2019 AT&T Intellectual Property.
   6
   7    Licensed under the Apache License, Version 2.0 (the "License");
   8    you may not use this file except in compliance with the License.
   9    You may obtain a copy of the License at
  10
  11            http://www.apache.org/licenses/LICENSE-2.0
  12
  13    Unless required by applicable law or agreed to in writing, software
  14    distributed under the License is distributed on an "AS IS" BASIS,
  15    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16    See the License for the specific language governing permissions and
  17    limitations under the License.
  18 ==================================================================================
  19 */
  20
  21 /*
  22 ------------------------------------------------------------------------------
  23 Mnemonic:       symtab.c
  24 Abstract:       Symbol table -- slightly streamlined from it's original 2000 version
  25                         (a part of the {X}fm opensource code), though we must retain the
  26                         original copyright.
  27
  28                         Things changed for the Ric Msg implemention (Nov 2018):
  29                                 - no concept of copy/free of the user data (functions removed)
  30                                 - add ability to support an integer key (class 0)
  31                                   Numeric key is an unsigned, 64bit key.
  32                                 - externally visible names given a rmr_ extension as it's being
  33                                   incorporated into the RIC msg routing library and will be
  34                                   available to user applications.
  35
  36 Date:           11 Feb 2000
  37 Author:         E. Scott Daniels
  38
  39 Mod:            2016 23 Feb - converted Symtab refs so that caller need only a
  40                                 void pointer to use and struct does not need to be exposed.
  41                         2018 30 Nov - Augmented from original form (see above).
  42 ------------------------------------------------------------------------------
  43 */
  44
  45 #include <stdio.h>
  46 #include <unistd.h>
  47 #include <string.h>
  48 #include <stdlib.h>
  49 #include <memory.h>
  50 #include <netdb.h>
  51
  52 #include "rmr_symtab.h"
  53
  54 //-----------------------------------------------------------------------------------------------
  55
  56 typedef struct Sym_ele
  57 {
  58         struct Sym_ele *next;   /* pointer at next element in list */
  59         struct Sym_ele *prev;   /* larger table, easier deletes */
  60         const char *name;               /* symbol name */
  61         uint64_t nkey;                  // the numeric key
  62         void *val;              /* user data associated with name */
  63         unsigned long mcount;   /* modificaitons to value */
  64         unsigned long rcount;   /* references to symbol */
  65         //unsigned int flags;
  66         unsigned int class;             /* helps divide things up and allows for duplicate names */
  67 } Sym_ele;
  68
  69 typedef struct Sym_tab {
  70         Sym_ele **symlist;                      /* pointer to list of element pointerss */
  71         long    inhabitants;            /* number of active residents */
  72         long    deaths;                         /* number of deletes */
  73         long    size;
  74 } Sym_tab;
  75
  76 // -------------------- internal ------------------------------------------------------------------
  77
  78 static int sym_hash( const char *n, long size )
  79 {
  80         const char *p;
  81         long t = 0;
  82         unsigned long tt = 0;
  83         unsigned long x = 79;
  84
  85         for( p = n; *p; p++ )      /* a bit of magic */
  86                 t = (t * 79 ) + *p;
  87
  88         if( t < 0 )
  89                 t = ~t;
  90
  91         return (int ) (t % size);
  92 }
  93
  94 /* delete element pointed to by eptr at hash loc hv */
  95 static void del_ele( Sym_tab *table, int hv, Sym_ele *eptr )
  96 {
  97         Sym_ele **sym_tab;
  98
  99         sym_tab = table->symlist;
 100
 101         if( eptr )         /* unchain it */
 102         {
 103                 if( eptr->prev )
 104                         eptr->prev->next = eptr->next;
 105                 else
 106                         sym_tab[hv] = eptr->next;
 107
 108                 if( eptr->next )
 109                         eptr->next->prev = eptr->prev;
 110
 111                 if( eptr->class && eptr->name ) {                               // class 0 entries are numeric, so name is NOT a pointer
 112                         free( (void *) eptr->name );                    // and if free fails, what?  panic?
 113                 }
 114
 115                 free( eptr );
 116
 117                 table->deaths++;
 118                 table->inhabitants--;
 119         }
 120 }
 121
 122 /*
 123         Determine if these are the same.
 124 */
 125 static inline int same( unsigned int c1, unsigned int c2, const char *s1, const char* s2 )
 126 {
 127         if( c1 != c2 )
 128                 return 0;               /* different class - not the same */
 129
 130         if( *s1 == *s2 && strcmp( s1, s2 ) == 0 )
 131                 return 1;
 132         return 0;
 133 }
 134
 135 /*
 136         Generic routine to put something into the table
 137         called by sym_map or sym_put since the logic for each is pretty
 138         much the same.
 139 */
 140 static int putin( Sym_tab *table, const char *name, unsigned int class, void *val ) {
 141         Sym_ele *eptr;                  /* pointer into hash table */
 142         Sym_ele **sym_tab;      /* pointer into hash table */
 143         int hv;                 /* hash value */
 144         int rc = 0;             /* assume it existed */
 145         uint64_t nkey = 0;              // numeric key if class == 0
 146
 147         sym_tab = table->symlist;
 148
 149         if( class ) {                                                           // string key
 150                 hv = sym_hash( name, table->size );             // hash it
 151                 for( eptr=sym_tab[hv]; eptr && ! same( class, eptr->class, eptr->name, name); eptr=eptr->next );
 152         } else {
 153                 nkey = *((uint64_t *) name);
 154                 hv = nkey % table->size;                                        // just hash the number
 155                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
 156         }
 157
 158         if( ! eptr ) {                  // not found above, so add
 159                 rc++;
 160                 table->inhabitants++;
 161
 162                 eptr = (Sym_ele *) malloc( sizeof( Sym_ele) );
 163                 if( ! eptr ) {
 164                         fprintf( stderr, "[FAIL] symtab/putin: out of memory\n" );
 165                         return -1;
 166                 }
 167
 168                 eptr->prev = NULL;
 169                 eptr->class = class;
 170                 eptr->mcount = eptr->rcount = 0;        /* init counters */
 171                 eptr->val = NULL;
 172                 eptr->nkey = nkey;
 173                 if( class ) {
 174                         eptr->name = strdup( name );
 175                 } else {
 176                         eptr->name = NULL;                              // for a numeric key, just save the value
 177                 }
 178                 eptr->next = sym_tab[hv];                       // add to head of list
 179                 sym_tab[hv] = eptr;
 180                 if( eptr->next )
 181                         eptr->next->prev = eptr;         /* chain back to new one */
 182         }
 183
 184         eptr->mcount++;
 185
 186         eptr->val = val;
 187
 188         return rc;
 189 }
 190
 191 // -------------------- visible  ------------------------------------------------------------------
 192
 193 /* delete all elements in the table */
 194 extern void rmr_sym_clear( void *vtable )
 195 {
 196         Sym_tab *table;
 197         Sym_ele **sym_tab;
 198         int i;
 199
 200         table = (Sym_tab *) vtable;
 201         sym_tab = table->symlist;
 202
 203         for( i = 0; i < table->size; i++ )
 204                 while( sym_tab[i] )
 205                         del_ele( table, i, sym_tab[i] );
 206 }
 207
 208 /*
 209         Clear and then free the whole thing.
 210 */
 211 extern void rmr_sym_free( void *vtable ) {
 212         Sym_tab *table;
 213
 214         table = (Sym_tab *) vtable;
 215
 216         if( table == NULL )
 217                 return;
 218
 219         rmr_sym_clear( vtable );
 220         free( table->symlist );
 221         free( table );
 222 }
 223
 224 extern void rmr_sym_dump( void *vtable )
 225 {
 226         Sym_tab *table;
 227         int i;
 228         Sym_ele *eptr;
 229         Sym_ele **sym_tab;
 230
 231         table = (Sym_tab *) vtable;
 232         sym_tab = table->symlist;
 233
 234         for( i = 0; i < table->size; i++ )
 235         {
 236                 if( sym_tab[i] )
 237                 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
 238                 {
 239                         if( eptr->val && eptr->class ) {
 240                                 fprintf( stderr, "key=%s val@=%p\n", eptr->name, eptr->val );
 241                         } else {
 242                                 fprintf( stderr, "nkey=%lu val@=%p\n", (unsigned long) eptr->nkey, eptr->val );
 243                         }
 244                 }
 245         }
 246 }
 247
 248 /*
 249         Allocate a table the size requested - best if size is prime.
 250         Returns a pointer to the management block (handle) or NULL on failure.
 251 */
 252 extern void *rmr_sym_alloc( int size )
 253 {
 254         int i;
 255         Sym_tab *table;
 256
 257         if( size < 11 )     /* provide a bit of sanity */
 258                 size = 11;
 259
 260         if( (table = (Sym_tab *) malloc( sizeof( Sym_tab ))) == NULL )
 261         {
 262                 fprintf( stderr, "rmr_sym_alloc: unable to get memory for symtable (%d elements)", size );
 263                 return NULL;
 264         }
 265
 266         memset( table, 0, sizeof( *table ) );
 267
 268         if((table->symlist = (Sym_ele **) malloc( sizeof( Sym_ele *) * size )))
 269         {
 270                 memset( table->symlist, 0, sizeof( Sym_ele *) * size );
 271                 table->size = size;
 272         }
 273         else
 274         {
 275                 fprintf( stderr, "sym_alloc: unable to get memory for %d elements", size );
 276                 return NULL;
 277         }
 278
 279         return (void *) table;    /* user might want to know what the size is */
 280 }
 281
 282 /*
 283         Delete an element given name/class or numeric key (class 0).
 284 */
 285 extern void rmr_sym_del( void *vtable, const char *name, unsigned int class )
 286 {
 287         Sym_tab *table;
 288         Sym_ele **sym_tab;
 289         Sym_ele *eptr;                  /* pointer into hash table */
 290         int hv;                 /* hash value */
 291         uint64_t        nkey;           // class 0, name points to integer not string
 292
 293         table = (Sym_tab *) vtable;
 294         sym_tab = table->symlist;
 295
 296         if( class ) {
 297                 hv = sym_hash( name, table->size );
 298                 for(eptr=sym_tab[hv]; eptr &&  ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
 299         } else {
 300                 nkey = *((uint64_t *) name);
 301                 hv = nkey % table->size;                        // just hash the number
 302                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
 303         }
 304
 305         del_ele( table, hv, eptr );    /* ignors null ptr, so safe to always call */
 306 }
 307
 308 /*
 309         Delete element by numberic key.
 310 */
 311 extern void *rmr_sym_ndel(  void *vtable, uint64_t key ) {
 312         rmr_sym_del( vtable, (const char *) &key, 0 );
 313 }
 314
 315
 316 extern void *rmr_sym_get( void *vtable, const char *name, unsigned int class )
 317 {
 318         Sym_tab *table;
 319         Sym_ele **sym_tab;
 320         Sym_ele *eptr;                  // element from table
 321         int hv;                 // hash value of key
 322         uint64_t nkey;                  // numeric key if class 0
 323
 324         if( (table = (Sym_tab *) vtable) == NULL ) {
 325                 return NULL;
 326         }
 327
 328         sym_tab = table->symlist;
 329
 330         if( class ) {
 331                 hv = sym_hash( name, table->size );
 332                 for(eptr=sym_tab[hv]; eptr &&  ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
 333         } else {
 334                 nkey = *((uint64_t *) name);
 335                 hv = nkey % table->size;                        // just hash the number
 336                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
 337         }
 338
 339         if( eptr )
 340         {
 341                 eptr->rcount++;
 342                 return eptr->val;
 343         }
 344
 345         return NULL;
 346 }
 347
 348 /*
 349         Retrieve the data referenced by a numerical key.
 350 */
 351 extern void *rmr_sym_pull(  void *vtable, uint64_t key ) {
 352         return rmr_sym_get( vtable, (const char *) &key, 0 );
 353 }
 354
 355 /*
 356         Put an element with a string key into the table. Replaces the element
 357         if it was already there.  Class must be >0 and if not 1 will be forced.
 358         (class 0 keys are numeric).
 359         Returns 1 if new, 0 if existed.
 360 */
 361 extern int rmr_sym_put( void *vtable, const char *name, unsigned int class, void *val )
 362 {
 363         Sym_tab *table;
 364
 365         if( class == 0 ) {
 366                 class = 1;
 367         }
 368
 369         table = (Sym_tab *) vtable;
 370         return putin( table, name, class, val );
 371 }
 372
 373 /*
 374         Add a new entry assuming that the key is an unsigned, 64 bit, integer.
 375
 376         Returns 1 if new, 0 if existed
 377 */
 378 extern int rmr_sym_map( void *vtable, uint64_t key, void *val ) {
 379         Sym_tab *table;
 380
 381         table = (Sym_tab *) vtable;
 382         return putin( table, (const char *) &key, 0, val );
 383 }
 384
 385 /*
 386         Dump some statistics to stderr dev. Higher level is the more info dumpped
 387 */
 388 extern void rmr_sym_stats( void *vtable, int level )
 389 {
 390         Sym_tab *table;
 391         Sym_ele *eptr;    /* pointer into the elements */
 392         Sym_ele **sym_tab;
 393         int i;
 394         int empty = 0;
 395         long ch_count;
 396         long max_chain = 0;
 397         int maxi = 0;
 398         int twoper = 0;
 399
 400         table = (Sym_tab *) vtable;
 401         sym_tab = table->symlist;
 402
 403         for( i = 0; i < table->size; i++ )
 404         {
 405                 ch_count = 0;
 406                 if( sym_tab[i] )
 407                 {
 408                         for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
 409                         {
 410                                 ch_count++;
 411                                 if( level > 3 ) {
 412                                         if( eptr->class  ) {                                    // a string key
 413                                                 fprintf( stderr, "sym: (%d) key=%s val@=%p ref=%ld mod=%lu\n", i, eptr->name, eptr->val, eptr->rcount, eptr->mcount );
 414                                         } else {
 415                                                 fprintf( stderr, "sym: (%d) key=%lu val@=%p ref=%ld mod=%lu\n", i, (unsigned long) eptr->nkey, eptr->val, eptr->rcount, eptr->mcount );
 416                                         }
 417                                 }
 418                         }
 419                 }
 420                 else
 421                         empty++;
 422
 423                 if( ch_count > max_chain )
 424                 {
 425                         max_chain = ch_count;
 426                         maxi = i;
 427                 }
 428                 if( ch_count > 1 )
 429                         twoper++;
 430
 431                 if( level > 2 )
 432                         fprintf( stderr, "sym: (%d) chained=%ld\n", i, ch_count );
 433         }
 434
 435         if( level > 1 )
 436         {
 437                 fprintf( stderr, "sym: longest chain: idx=%d has %ld elsements):\n", maxi, max_chain );
 438                 for( eptr = sym_tab[maxi]; eptr; eptr = eptr->next ) {
 439                         if( eptr->class ) {
 440                                 fprintf( stderr, "\t%s\n", eptr->name );
 441                         } else {
 442                                 fprintf( stderr, "\t%lu (numeric key)\n", (unsigned long) eptr->nkey );
 443                         }
 444                 }
 445         }
 446
 447         fprintf( stderr, "sym:%ld(size)  %ld(inhab) %ld(occupied) %ld(dead) %ld(maxch) %d(>2per)\n",
 448                         table->size, table->inhabitants, table->size - empty, table->deaths, max_chain, twoper );
 449 }
 450
 451 /*
 452         Drive a user callback function for each entry in a class. It is safe for
 453         the user to delete the element as we capture a next pointer before
 454         calling their function.
 455 */
 456 extern void rmr_sym_foreach_class( void *vst, unsigned int class, void (* user_fun)( void*, void*, const char*, void*, void* ), void *user_data )
 457 {
 458         Sym_tab *st;
 459         Sym_ele **list;
 460         Sym_ele *se;
 461         Sym_ele *next;          /* allows user to delete the node(s) we return */
 462         int     i;
 463
 464         st = (Sym_tab *) vst;
 465
 466         if( st && (list = st->symlist) != NULL && user_fun != NULL )
 467                 for( i = 0; i < st->size; i++ )
 468                         for( se = list[i]; se; se = next )              /* using next allows user to delet via this */
 469                         {
 470                                 next = se->next;
 471                                 if( class == se->class ) {
 472                                         user_fun( st, se, se->name, se->val, user_data );
 473                                 }
 474                         }
 475 }