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