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