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