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