userapps/opensource/net-snmp/snmplib/container_binary_array.c

   1 #if BRCM_CONTAINER_SUPPORT
   2 /*
   3  * container_binary_array.c
   4  * $Id: container_binary_array.c,v 1.6.2.2 2003/01/21 04:21:08 rstory Exp $
   5  *
   6  * see comments in header file.
   7  *
   8  */
   9
  10 #include <net-snmp/net-snmp-config.h>
  11
  12 #if HAVE_IO_H
  13 #include <io.h>
  14 #endif
  15 #include <stdio.h>
  16 #if HAVE_STDLIB_H
  17 #include <stdlib.h>
  18 #endif
  19 #if HAVE_MALLOC_H
  20 #include <malloc.h>
  21 #endif
  22 #include <sys/types.h>
  23 #if HAVE_STRING_H
  24 #include <string.h>
  25 #else
  26 #include <strings.h>
  27 #endif
  28
  29 #include <net-snmp/net-snmp-includes.h>
  30 #include <net-snmp/types.h>
  31 #include <net-snmp/library/snmp_api.h>
  32 #include <net-snmp/library/container.h>
  33 #include <net-snmp/library/container_binary_array.h>
  34 #include <net-snmp/library/tools.h>
  35 #include <net-snmp/library/snmp_assert.h>
  36
  37 typedef struct binary_array_table_s {
  38     size_t                     max_size;   /* Size of the current data table */
  39     size_t                     count;      /* Index of the next free entry */
  40     int                        dirty;
  41     int                        data_size;  /* Size of an individual entry */
  42     void                     **data;       /* The table itself */
  43 } binary_array_table;
  44
  45 static void
  46 array_qsort(void **data, int first, int last, netsnmp_container_compare *f)
  47 {
  48     int i, j;
  49     void *mid, *tmp;
  50
  51     i = first;
  52     j = last;
  53     mid = data[(first+last)/2];
  54
  55     do {
  56         while ( ((*f)(data[i], mid) < 0) && (i < last))
  57             ++i;
  58         while ( ((*f)(mid, data[j]) < 0) && (j > first))
  59             --j;
  60
  61         if(i < j) {
  62             tmp = data[i];
  63             data[i] = data[j];
  64             data[j] = tmp;
  65             ++i;
  66             --j;
  67         }
  68         else if (i == j) {
  69             ++i;
  70             --j;
  71             break;
  72         }
  73     } while(i <= j);
  74
  75     if (j > first)
  76         array_qsort(data, first, j, f);
  77
  78     if (i < last)
  79         array_qsort(data, i, last, f);
  80 }
  81
  82 static int
  83 Sort_Array(netsnmp_container *c)
  84 {
  85     binary_array_table *t = (binary_array_table*)c->private;
  86     netsnmp_assert(t!=NULL);
  87     netsnmp_assert(c->compare!=NULL);
  88
  89     if (t->dirty) {
  90         /*
  91          * Sort the table
  92          */
  93         if (t->count > 1)
  94             array_qsort(t->data, 0, t->count - 1, c->compare);
  95         t->dirty = 0;
  96     }
  97
  98     return 1;
  99 }
 100
 101 static int
 102 binary_search(const void *val, netsnmp_container *c, int exact)
 103 {
 104     binary_array_table *t = (binary_array_table*)c->private;
 105     size_t             len = t->count;
 106     size_t             half;
 107     size_t             middle;
 108     size_t             first = 0;
 109     int                result = 0;
 110
 111     if (!len)
 112         return -1;
 113
 114     if (t->dirty)
 115         Sort_Array(c);
 116
 117     while (len > 0) {
 118         half = len >> 1;
 119         middle = first;
 120         middle += half;
 121         if ((result =
 122              c->compare(t->data[middle], val)) < 0) {
 123             first = middle;
 124             ++first;
 125             len = len - half - 1;
 126         } else {
 127             if(result == 0) {
 128                 first = middle;
 129                 break;
 130             }
 131             len = half;
 132         }
 133     }
 134
 135     if (first >= t->count)
 136         return -1;
 137
 138     if(first != middle) {
 139         /* last compare wasn't against first, so get actual result */
 140         result = c->compare(t->data[first], val);
 141     }
 142
 143     if(result == 0) {
 144         if (!exact) {
 145             if (++first == t->count)
 146                first = -1;
 147         }
 148     }
 149     else {
 150         if(exact)
 151             first = -1;
 152     }
 153
 154     return first;
 155 }
 156
 157 binary_array_table *
 158 netsnmp_binary_array_initialize(void)
 159 {
 160     binary_array_table *t;
 161
 162     t = SNMP_MALLOC_TYPEDEF(binary_array_table);
 163     if (t == NULL)
 164         return NULL;
 165
 166     t->max_size = 0;
 167     t->count = 0;
 168     t->dirty = 0;
 169     t->data_size = 4;
 170     t->data = NULL;
 171
 172     return t;
 173 }
 174
 175 void
 176 netsnmp_binary_array_release(netsnmp_container *c)
 177 {
 178     binary_array_table *t = (binary_array_table*)c->private;
 179     free(t);
 180 }
 181
 182 size_t
 183 netsnmp_binary_array_count(netsnmp_container *c)
 184 {
 185     binary_array_table *t = (binary_array_table*)c->private;
 186     /*
 187      * return count
 188      */
 189     return t ? t->count : 0;
 190 }
 191
 192 void           *
 193 netsnmp_binary_array_get(netsnmp_container *c, const void *key, int exact)
 194 {
 195     binary_array_table *t = (binary_array_table*)c->private;
 196     int             index = 0;
 197
 198     /*
 199      * if there is no data, return NULL;
 200      */
 201     if (!t->count)
 202         return 0;
 203
 204     /*
 205      * if the table is dirty, sort it.
 206      */
 207     if (t->dirty)
 208         Sort_Array(c);
 209
 210     /*
 211      * if there is a key, search. Otherwise default is 0;
 212      */
 213     if (key) {
 214         if ((index = binary_search(key, c, exact)) == -1)
 215             return 0;
 216     }
 217
 218     return t->data[index];
 219 }
 220
 221 int
 222 netsnmp_binary_array_replace(netsnmp_container *c, void *entry)
 223 {
 224     binary_array_table *t = (binary_array_table*)c->private;
 225     int             index = 0;
 226
 227     /*
 228      * if there is no data, return NULL;
 229      */
 230     if (!t->count)
 231         return 0;
 232
 233     /*
 234      * if the table is dirty, sort it.
 235      */
 236     if (t->dirty)
 237         Sort_Array(c);
 238
 239     /*
 240      * search
 241      */
 242     if ((index = binary_search(entry, c, 1)) == -1)
 243         return 0;
 244
 245     t->data[index] = entry;
 246
 247     return 0;
 248 }
 249
 250 int
 251 netsnmp_binary_array_remove(netsnmp_container *c, const void *key, void **save)
 252 {
 253     binary_array_table *t = (binary_array_table*)c->private;
 254     int             index = 0;
 255
 256     if (save)
 257         *save = NULL;
 258
 259     /*
 260      * if there is no data, return NULL;
 261      */
 262     if (!t->count)
 263         return 0;
 264
 265     /*
 266      * if the table is dirty, sort it.
 267      */
 268     if (t->dirty)
 269         Sort_Array(c);
 270
 271     /*
 272      * search
 273      */
 274     if ((index = binary_search(key, c, 1)) == -1)
 275         return -1;
 276
 277     /*
 278      * find old data and save it, if ptr provided
 279      */
 280     if (save)
 281         *save = t->data[index];
 282
 283     /*
 284      * if entry was last item, just decrement count
 285      */
 286     --t->count;
 287     if (index != t->count) {
 288         /*
 289          * otherwise, shift array down
 290          */
 291         memmove(&t->data[index], &t->data[index+1], t->data_size * (t->count - index));
 292     }
 293
 294     return 0;
 295 }
 296
 297 void
 298 netsnmp_binary_array_for_each(netsnmp_container *c,
 299                               netsnmp_container_obj_func *fe,
 300                               void *context, int sort)
 301 {
 302     binary_array_table *t = (binary_array_table*)c->private;
 303     size_t             i;
 304
 305     if (sort && t->dirty)
 306         Sort_Array(c);
 307
 308     for (i = 0; i < t->count; ++i)
 309         (*fe) (t->data[i], context);
 310 }
 311
 312 int
 313 netsnmp_binary_array_insert(netsnmp_container *c, const void *entry)
 314 {
 315     binary_array_table *t = (binary_array_table*)c->private;
 316     int             new_max;
 317     void           *new_data;   /* Used for * a) extending the data table
 318                                  * * b) the next entry to use */
 319
 320     if (t->max_size <= t->count) {
 321         /*
 322          * Table is full, so extend it to double the size
 323          */
 324         new_max = 2 * t->max_size;
 325         if (new_max == 0)
 326             new_max = 10;       /* Start with 10 entries */
 327
 328         new_data = (void *) calloc(new_max, t->data_size);
 329         if (new_data == NULL)
 330             return -1;
 331
 332         if (t->data) {
 333             memcpy(new_data, t->data, t->max_size * t->data_size);
 334             free(t->data);
 335         }
 336         t->data = new_data;
 337         t->max_size = new_max;
 338     }
 339
 340     /*
 341      * Insert the new entry into the data array
 342      */
 343     t->data[t->count++] = (void*)entry;
 344     t->dirty = 1;
 345     return 0;
 346 }
 347
 348 void           *
 349 netsnmp_binary_array_retrieve(netsnmp_container *c, int *max_oids, int sort)
 350 {
 351     binary_array_table *t = (binary_array_table*)c->private;
 352     if (sort && t->dirty)
 353         Sort_Array(c);
 354
 355     *max_oids = t->count;
 356     return t->data;
 357 }
 358
 359 /**********************************************************************
 360  *
 361  * Special case support for subsets
 362  *
 363  */
 364 static int
 365 binary_search_for_start(netsnmp_index *val, netsnmp_container *c)
 366 {
 367     binary_array_table *t = (binary_array_table*)c->private;
 368     size_t             len = t->count;
 369     size_t             half;
 370     size_t             middle;
 371     size_t             first = 0;
 372     int                result = 0;
 373
 374     if (!len)
 375         return -1;
 376
 377     if (t->dirty)
 378         Sort_Array(c);
 379
 380     while (len > 0) {
 381         half = len >> 1;
 382         middle = first;
 383         middle += half;
 384         if ((result = c->ncompare(t->data[middle], val)) < 0) {
 385             first = middle;
 386             ++first;
 387             len = len - half - 1;
 388         } else
 389             len = half;
 390     }
 391
 392     if ((first >= t->count) ||
 393         c->ncompare(t->data[first], val) != 0)
 394         return -1;
 395
 396     return first;
 397 }
 398
 399 void          **
 400 netsnmp_binary_array_get_subset(netsnmp_container *c, void *key, int *len)
 401 {
 402     binary_array_table *t = (binary_array_table*)c->private;
 403     void          **subset;
 404     int             start, end;
 405     size_t          i;
 406
 407     /*
 408      * if there is no data, return NULL;
 409      */
 410     if (!t->count || !key)
 411         return 0;
 412
 413     /*
 414      * if the table is dirty, sort it.
 415      */
 416     if (t->dirty)
 417         Sort_Array(c);
 418
 419     /*
 420      * find matching items
 421      */
 422     start = end = binary_search_for_start(key, c);
 423     if (start == -1)
 424         return 0;
 425
 426     for (i = start + 1; i < t->count; ++i) {
 427         if (0 != c->ncompare(t->data[i], key))
 428             break;
 429         ++end;
 430     }
 431
 432     *len = end - start + 1;
 433     subset = malloc((*len) * t->data_size);
 434     memcpy(subset, &t->data[start], t->data_size * (*len));
 435
 436     return subset;
 437 }
 438
 439 /**********************************************************************
 440  *
 441  * container
 442  *
 443  */
 444 static void *
 445 _ba_find(netsnmp_container *container, const void *data)
 446 {
 447     return netsnmp_binary_array_get(container, data, 1);
 448 }
 449
 450 static void *
 451 _ba_find_next(netsnmp_container *container, const void *data)
 452 {
 453     return netsnmp_binary_array_get(container, data, 0);
 454 }
 455
 456 static int
 457 _ba_insert(netsnmp_container *container, const void *data)
 458 {
 459     return netsnmp_binary_array_insert(container, data);
 460 }
 461
 462 static int
 463 _ba_remove(netsnmp_container *container, const void *data)
 464 {
 465     return netsnmp_binary_array_remove(container,data, NULL);
 466 }
 467
 468 static int
 469 _ba_free(netsnmp_container *container)
 470 {
 471     netsnmp_binary_array_release(container);
 472     return 0;
 473 }
 474
 475 static size_t
 476 _ba_size(netsnmp_container *container)
 477 {
 478     return netsnmp_binary_array_count(container);
 479 }
 480
 481 static void
 482 _ba_for_each(netsnmp_container *container, netsnmp_container_obj_func *f,
 483              void *context)
 484 {
 485     netsnmp_binary_array_for_each(container, f, context, 0);
 486 }
 487
 488 static netsnmp_void_array *
 489 _ba_get_subset(netsnmp_container *container, void *data)
 490 {
 491     netsnmp_void_array * va;
 492     void ** rtn;
 493     int len;
 494
 495     rtn = netsnmp_binary_array_get_subset(container, data, &len);
 496     if ((NULL==rtn) || (len <=0))
 497         return NULL;
 498
 499     va = SNMP_MALLOC_TYPEDEF(netsnmp_void_array);
 500     if (NULL==va)
 501         return NULL;
 502
 503     va->size = len;
 504     va->array = rtn;
 505
 506     return va;
 507 }
 508
 509 int
 510 netsnmp_container_get_binary_array_noalloc(netsnmp_container *c)
 511 {
 512     if (NULL==c)
 513         return -1;
 514
 515     c->private = netsnmp_binary_array_initialize();
 516
 517     c->get_size = _ba_size;
 518     c->init = NULL;
 519     c->cfree = _ba_free;
 520     c->insert = _ba_insert;
 521     c->remove = _ba_remove;
 522     c->find = _ba_find;
 523     c->find_next = _ba_find_next;
 524     c->get_subset = _ba_get_subset;
 525     c->get_iterator = NULL;
 526     c->for_each = _ba_for_each;
 527
 528     return 0;
 529 }
 530
 531 netsnmp_container *
 532 netsnmp_container_get_binary_array(void)
 533 {
 534     /*
 535      * allocate memory
 536      */
 537     netsnmp_container *c = SNMP_MALLOC_TYPEDEF(netsnmp_container);
 538     if (NULL==c) {
 539         snmp_log(LOG_ERR, "couldn't allocate memory\n");
 540         return NULL;
 541     }
 542
 543     if (0 != netsnmp_container_get_binary_array_noalloc(c)) {
 544         free(c);
 545         return NULL;
 546     }
 547
 548     return c;
 549 }
 550
 551 netsnmp_factory *
 552 netsnmp_container_get_binary_array_factory(void)
 553 {
 554     static netsnmp_factory f = { "binary_array",
 555                                  (netsnmp_factory_produce_f*)
 556                                  netsnmp_container_get_binary_array,
 557                                  (netsnmp_factory_produce_noalloc_f*)
 558                                  netsnmp_container_get_binary_array_noalloc };
 559
 560     return &f;
 561 }
 562
 563 #ifdef NOT_YET
 564 void *
 565 netsnmp_binary_array_iterator_first(netsnmp_iterator *it)
 566 {
 567     binary_array_table *t;
 568
 569     if(NULL == it) {
 570         netsnmp_assert(NULL != it);
 571         return NULL;
 572     }
 573     if(NULL == it->container) {
 574         netsnmp_assert(NULL != it->container);
 575         return NULL;
 576     }
 577     if(NULL == it->container->private) {
 578         netsnmp_assert(NULL != it->container->private);
 579         return NULL;
 580     }
 581     t = (binary_array_table*)(it->container->private);
 582
 583     (int)(it->context) = 0;
 584
 585     if((int)(it->context) <= t->count)
 586         return NULL;
 587
 588     return t->data[ (int)(it->context) ];
 589 }
 590
 591 netsnmp_binary_array_iterator_next(netsnmp_iterator *it)
 592 {
 593     if(NULL == it) {
 594         netsnmp_assert(NULL != it);
 595         return NULL;
 596     }
 597     if(NULL == it->container) {
 598         netsnmp_assert(NULL != it->container);
 599         return NULL;
 600     }
 601     if(NULL == it->container->private) {
 602         netsnmp_assert(NULL != it->container->private);
 603         return NULL;
 604     }
 605     t = (binary_array_table*)(it->container->private);
 606
 607     ++(int)(it->context);
 608
 609     if((int)(it->context) <= t->count)
 610         return NULL;
 611
 612     return t->data[ (int)(it->context) ];
 613
 614 }
 615
 616 void *
 617 netsnmp_binary_array_iterator_last(netsnmp_iterator *it)
 618 {
 619     if(NULL == it) {
 620         netsnmp_assert(NULL != it);
 621         return NULL;
 622     }
 623     if(NULL == it->container) {
 624         netsnmp_assert(NULL != it->container);
 625         return NULL;
 626     }
 627     if(NULL == it->container->private) {
 628         netsnmp_assert(NULL != it->container->private);
 629         return NULL;
 630     }
 631     t = (binary_array_table*)(it->container->private);
 632
 633     return t->data[ t->count - 1 ];
 634 }
 635
 636 /*  void * */
 637 /*  netsnmp_binary_array_iterator_position(netsnmp_iterator *it) */
 638 /*  { */
 639 /*      if(NULL == it) { */
 640 /*          netsnmp_assert(NULL != it); */
 641 /*          return NULL; */
 642 /*      } */
 643 /*      if(NULL == it->container) { */
 644 /*          netsnmp_assert(NULL != it->container); */
 645 /*          return NULL; */
 646 /*      } */
 647 /*      if(NULL == it->container->private) { */
 648 /*          netsnmp_assert(NULL != it->container->private); */
 649 /*          return NULL; */
 650 /*      } */
 651 /*      t = (binary_array_table*)(it->container->private); */
 652
 653 /*  } */
 654
 655 netsnmp_iterator *
 656 netsnmp_binary_array_get_iterator(netsnmp_container *c)
 657 {
 658     netsnmp_iterator* it;
 659
 660     if(NULL == c)
 661         return NULL;
 662
 663     it = SNMP_MALLOC_TYPEDEF(netsnmp_iterator);
 664     if(NULL == it)
 665         return NULL;
 666
 667     it->container = c;
 668     (int)(it->context) = 0;
 669
 670     it->first = netsnmp_binary_array_iterator_first;
 671     it->next = netsnmp_binary_array_iterator_next;
 672     it->last = netsnmp_binary_array_iterator_last;
 673     it->position = NULL;/*netsnmp_binary_array_iterator_position;*/
 674 }
 675 #endif
 676
 677 #endif /* BRCM_CONTAINER_SUPPORT */