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