src/rmr/common/src/symtab.c

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