Add alarm generation when application is slow
[ric-plt/lib/rmr.git] / 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 }