Correct meid table parse bug
[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
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 }