00001
00002
00003
00004
00005
00006 static int map_sizes[] = {
00007 sizeof(struct map_node_int64),
00008 sizeof(struct map_node_stat),
00009 sizeof(struct map_node_str),
00010 0
00011 };
00012
00013 static unsigned string_hash(const char *key1, const char *key2)
00014 {
00015 int hash = 0, count = 0;
00016 char *v1 = (char *)key1;
00017 char *v2 = (char *)key2;
00018 while (*v1 && count++ < 5) {
00019 hash += *v1++;
00020 }
00021 while (v2 && *v2 && count++ < 5) {
00022 hash += *v2++;
00023 }
00024 return hash_long((unsigned long)hash, HASH_TABLE_BITS);
00025 }
00026
00027 static unsigned mixed_hash(const char *key1, long key2)
00028 {
00029 int hash = 0, count = 0;
00030 char *v = (char *)key1;
00031 while (v && *v && count++ < 5)
00032 hash += *v++;
00033 return hash_long((unsigned long)(hash ^ key2), HASH_TABLE_BITS);
00034 }
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046 MAP _stp_map_new(unsigned max_entries, enum valtype type)
00047 {
00048 size_t size;
00049 MAP m = (MAP) _stp_valloc(sizeof(struct map_root));
00050 if (m == NULL)
00051 return NULL;
00052
00053 INIT_LIST_HEAD(&m->head);
00054
00055 m->maxnum = max_entries;
00056 m->type = type;
00057 if (type >= END) {
00058 dbug ("map_new: unknown type %d\n", type);
00059 return NULL;
00060 }
00061
00062 if (max_entries) {
00063 void *tmp;
00064 int i;
00065 struct list_head *e;
00066
00067 INIT_LIST_HEAD(&m->pool);
00068 size = map_sizes[type];
00069 tmp = _stp_valloc(max_entries * size);
00070
00071 for (i = max_entries - 1; i >= 0; i--) {
00072 e = i * size + tmp;
00073 dbug ("e=%lx\n", (long)e);
00074 list_add(e, &m->pool);
00075 }
00076 m->membuf = tmp;
00077 }
00078 return m;
00079 }
00080
00081 static void map_free_strings(MAP map, struct map_node *n)
00082 {
00083 struct map_node_str *m = (struct map_node_str *)n;
00084 dbug ("n = %lx\n", (long)n);
00085 if (map->type == STRING) {
00086 dbug ("val STRING %lx\n", (long)m->str);
00087 if (m->str)
00088 _stp_free(m->str);
00089 }
00090 if (m->n.key1type == STR) {
00091 dbug ("key1 STR %lx\n", (long)key1str(m));
00092 if (key1str(m))
00093 _stp_free(key1str(m));
00094 }
00095 if (m->n.key2type == STR) {
00096 dbug ("key2 STR %lx\n", (long)key2str(m));
00097 if (key2str(m))
00098 _stp_free(key2str(m));
00099 }
00100 }
00101
00102
00103
00104
00105
00106
00107 void _stp_map_key_del(MAP map)
00108 {
00109 struct map_node *m;
00110
00111 dbug ("create=%d key=%lx\n", map->create, (long)map->key);
00112 if (map == NULL)
00113 return;
00114
00115 if (map->create) {
00116 map->create = 0;
00117 map->key = NULL;
00118 return;
00119 }
00120
00121 if (map->key == NULL)
00122 return;
00123
00124 m = (struct map_node *)map->key;
00125
00126
00127 hlist_del_init(&m->hnode);
00128
00129
00130 list_del(&m->lnode);
00131
00132
00133 map_free_strings(map, (struct map_node *)map->key);
00134
00135 if (map->maxnum)
00136 list_add(&m->lnode, &map->pool);
00137 else
00138 _stp_free(m);
00139
00140 map->key = NULL;
00141 map->num--;
00142 }
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152 struct map_node *_stp_map_start(MAP map)
00153 {
00154 if (map == NULL)
00155 return NULL;
00156
00157 dbug ("%lx\n", (long)map->head.next);
00158
00159 if (list_empty(&map->head))
00160 return NULL;
00161
00162 return (struct map_node *)map->head.next;
00163 }
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175 struct map_node *_stp_map_iter(MAP map, struct map_node *m)
00176 {
00177 if (map == NULL)
00178 return NULL;
00179
00180 dbug ("%lx next=%lx prev=%lx map->head.next=%lx\n", (long)m,
00181 (long)m->lnode.next, (long)m->lnode.prev, (long)map->head.next);
00182
00183 if (m->lnode.next == &map->head)
00184 return NULL;
00185
00186 return (struct map_node *)m->lnode.next;
00187 }
00188
00189
00190
00191
00192
00193
00194 void _stp_map_del(MAP map)
00195 {
00196 if (map == NULL)
00197 return;
00198
00199 if (!list_empty(&map->head)) {
00200 struct map_node *ptr = (struct map_node *)map->head.next;
00201 while (ptr && ptr != (struct map_node *)&map->head) {
00202 map_free_strings(map, ptr);
00203 ptr = (struct map_node *)ptr->lnode.next;
00204 }
00205 }
00206 _stp_vfree(map->membuf);
00207 _stp_vfree(map);
00208 }
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222 void _stp_map_key_long_long(MAP map, long key1, long key2)
00223 {
00224 unsigned hv;
00225 struct hlist_head *head;
00226 struct hlist_node *e;
00227
00228 if (map == NULL)
00229 return;
00230
00231 hv = hash_long(key1 ^ key2, HASH_TABLE_BITS);
00232 head = &map->hashes[hv];
00233
00234 dbug ("hash for %ld,%ld is %d\n", key1, key2, hv);
00235
00236 hlist_for_each(e, head) {
00237 struct map_node *n =
00238 (struct map_node *)((long)e - sizeof(struct hlist_node));
00239 dbug ("n =%lx key=%ld,%ld\n", (long)n, n->key1.val, n->key2.val);
00240 if (key1 == n->key1.val && key2 == n->key2.val) {
00241 map->key = n;
00242 dbug ("saving key %lx\n", (long)map->key);
00243 map->create = 0;
00244 return;
00245 }
00246 }
00247
00248 map->c_key1.val = key1;
00249 map->c_key2.val = key2;
00250 map->c_key1type = LONG;
00251 map->c_key2type = LONG;
00252 map->c_keyhead = head;
00253 map->create = 1;
00254 }
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265 void _stp_map_key_str_str(MAP map, char *key1, char *key2)
00266 {
00267 unsigned hv;
00268 struct hlist_head *head;
00269 struct hlist_node *e;
00270
00271 if (map == NULL)
00272 return;
00273
00274 if (key1 == NULL) {
00275 map->key = NULL;
00276 return;
00277 }
00278
00279 hv = string_hash(key1, key2);
00280 head = &map->hashes[hv];
00281
00282 dbug ("hash for %s,%s is %d\n", key1, key2, hv);
00283
00284 hlist_for_each(e, head) {
00285 struct map_node *n =
00286 (struct map_node *)((long)e - sizeof(struct hlist_node));
00287 dbug ("e =%lx key=%s,%s\n", (long)e, n->key1.str,n->key2.str);
00288 if (strcmp(key1, n->key1.str) == 0
00289 && (key2 == NULL || strcmp(key2, n->key2.str) == 0)) {
00290 map->key = n;
00291 dbug ("saving key %lx\n", (long)map->key);
00292 map->create = 0;
00293 return;
00294 }
00295 }
00296
00297 map->c_key1.str = key1;
00298 map->c_key2.str = key2;
00299 map->c_key1type = STR;
00300 map->c_key2type = STR;
00301 map->c_keyhead = head;
00302 map->create = 1;
00303 }
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314 void _stp_map_key_str_long(MAP map, char *key1, long key2)
00315 {
00316 unsigned hv;
00317 struct hlist_head *head;
00318 struct hlist_node *e;
00319
00320 if (map == NULL)
00321 return;
00322
00323 if (key1 == NULL) {
00324 map->key = NULL;
00325 return;
00326 }
00327
00328 hv = mixed_hash(key1, key2);
00329 head = &map->hashes[hv];
00330
00331 dbug ("hash for %s,%ld is %d\n", key1, key2, hv);
00332
00333 hlist_for_each(e, head) {
00334 struct map_node *n =
00335 (struct map_node *)((long)e - sizeof(struct hlist_node));
00336 dbug ("e =%lx key=%s,%ld\n", (long)e, n->key1.str,(long)n->key2.val);
00337 if (strcmp(key1, n->key1.str) == 0 && key2 == n->key2.val) {
00338 map->key = n;
00339 dbug ("saving key %lx\n", (long)map->key);
00340 map->create = 0;
00341 return;
00342 }
00343 }
00344
00345 map->c_key1.str = key1;
00346 map->c_key2.val = key2;
00347 map->c_key1type = STR;
00348 map->c_key2type = LONG;
00349 map->c_keyhead = head;
00350 map->create = 1;
00351 }
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362 void _stp_map_key_long_str(MAP map, long key1, char *key2)
00363 {
00364 unsigned hv;
00365 struct hlist_head *head;
00366 struct hlist_node *e;
00367
00368 if (map == NULL)
00369 return;
00370
00371 hv = mixed_hash(key2, key1);
00372 head = &map->hashes[hv];
00373 dbug ("hash for %ld,%s is %d\n", key1, key2, hv);
00374
00375 hlist_for_each(e, head) {
00376 struct map_node *n =
00377 (struct map_node *)((long)e - sizeof(struct hlist_node));
00378 dbug ("e =%lx key=%ld,%s\n", (long)e, n->key1.val,n->key2.str);
00379 if (key1 == n->key1.val && strcmp(key2, n->key2.str) == 0) {
00380 map->key = n;
00381 dbug ("saving key %lx\n", (long)map->key);
00382 map->create = 0;
00383 return;
00384 }
00385 }
00386
00387 map->c_key1.val = key1;
00388 map->c_key2.str = key2;
00389 map->c_key1type = LONG;
00390 map->c_key2type = STR;
00391 map->c_keyhead = head;
00392 map->create = 1;
00393 }
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403 void _stp_map_key_str(MAP map, char *key)
00404 {
00405 if (map == NULL)
00406 return;
00407 _stp_map_key_str_str(map, key, NULL);
00408 map->c_key2type = NONE;
00409 }
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419 void _stp_map_key_long(MAP map, long key)
00420 {
00421 if (map == NULL)
00422 return;
00423 _stp_map_key_long_long(map, key, 0);
00424 map->c_key2type = NONE;
00425 }
00426
00427
00428
00429 static void map_copy_keys(MAP map, struct map_node *m)
00430 {
00431 m->key1type = map->c_key1type;
00432 m->key2type = map->c_key2type;
00433 switch (map->c_key1type) {
00434 case STR:
00435 m->key1.str = _stp_alloc(strlen(map->c_key1.str) + 1);
00436 strcpy(m->key1.str, map->c_key1.str);
00437 break;
00438 case LONG:
00439 m->key1.val = map->c_key1.val;
00440 break;
00441 case NONE:
00442
00443 break;
00444 }
00445 switch (map->c_key2type) {
00446 case STR:
00447 m->key2.str = _stp_alloc(strlen(map->c_key2.str) + 1);
00448 strcpy(m->key2.str, map->c_key2.str);
00449 break;
00450 case LONG:
00451 m->key2.val = map->c_key2.val;
00452 break;
00453 case NONE:
00454 break;
00455 }
00456
00457
00458 hlist_add_head(&m->hnode, map->c_keyhead);
00459
00460 map->key = m;
00461 map->create = 0;
00462 map->num++;
00463 }
00464
00465 static void __stp_map_set_int64(MAP map, int64_t val, int add)
00466 {
00467 struct map_node_int64 *m;
00468
00469 if (map == NULL)
00470 return;
00471
00472 if (map->create) {
00473 if (val == 0)
00474 return;
00475
00476 if (map->maxnum) {
00477 if (list_empty(&map->pool)) {
00478 if (map->no_wrap) {
00479
00480 return;
00481 }
00482 m = (struct map_node_int64 *)map->head.next;
00483 hlist_del_init(&m->n.hnode);
00484 map_free_strings(map, (struct map_node *)m);
00485 dbug ("got %lx off head\n", (long)m);
00486 } else {
00487 m = (struct map_node_int64 *)map->pool.next;
00488 dbug ("got %lx off pool\n", (long)m);
00489 }
00490 list_move_tail(&m->n.lnode, &map->head);
00491 } else {
00492 m = (struct map_node_int64 *)
00493 _stp_calloc(sizeof(struct map_node_int64));
00494
00495 list_add_tail(&m->n.lnode, &map->head);
00496 }
00497
00498
00499 map_copy_keys(map, &m->n);
00500
00501
00502 m->val = val;
00503 } else {
00504 if (map->key == NULL)
00505 return;
00506
00507 if (val) {
00508 m = (struct map_node_int64 *)map->key;
00509 if (add)
00510 m->val += val;
00511 else
00512 m->val = val;
00513 } else if (!add) {
00514
00515 _stp_map_key_del(map);
00516 }
00517 }
00518 }
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530 void _stp_map_set_int64(MAP map, int64_t val)
00531 {
00532 __stp_map_set_int64 (map, val, 0);
00533 }
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547 void _stp_map_add_int64(MAP map, int64_t val)
00548 {
00549 __stp_map_set_int64 (map, val, 1);
00550 }
00551
00552
00553
00554
00555
00556
00557 int64_t _stp_map_get_int64(MAP map)
00558 {
00559 struct map_node_int64 *m;
00560 if (map == NULL || map->create || map->key == NULL)
00561 return 0;
00562 dbug ("%lx\n", (long)map->key);
00563 m = (struct map_node_int64 *)map->key;
00564 return m->val;
00565 }
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577 void _stp_map_set_str(MAP map, char *val)
00578 {
00579 struct map_node_str *m;
00580
00581 if (map == NULL)
00582 return;
00583
00584 if (map->create) {
00585 if (val == NULL)
00586 return;
00587
00588 if (map->maxnum) {
00589 if (list_empty(&map->pool)) {
00590 if (map->no_wrap) {
00591
00592 return;
00593 }
00594 m = (struct map_node_str *)map->head.next;
00595 hlist_del_init(&m->n.hnode);
00596 map_free_strings(map, (struct map_node *)m);
00597 dbug ("got %lx off head\n", (long)m);
00598 } else {
00599 m = (struct map_node_str *)map->pool.next;
00600 dbug ("got %lx off pool\n", (long)m);
00601 }
00602 list_move_tail(&m->n.lnode, &map->head);
00603 } else {
00604 m = (struct map_node_str *)
00605 _stp_calloc(sizeof(struct map_node_str));
00606
00607 list_add_tail(&m->n.lnode, &map->head);
00608 }
00609
00610
00611 map_copy_keys(map, &m->n);
00612
00613
00614 m->str = _stp_alloc(strlen(val) + 1);
00615 strcpy(m->str, val);
00616 } else {
00617 if (map->key == NULL)
00618 return;
00619
00620 if (val) {
00621 m = (struct map_node_str *)map->key;
00622 if (m->str)
00623 _stp_free(m->str);
00624 m->str = _stp_alloc(strlen(val) + 1);
00625 strcpy(m->str, val);
00626 } else {
00627
00628 _stp_map_key_del(map);
00629 }
00630 }
00631 }
00632
00633
00634
00635
00636
00637
00638 char *_stp_map_get_str(MAP map)
00639 {
00640 struct map_node_str *m;
00641 if (map == NULL || map->create || map->key == NULL)
00642 return NULL;
00643 dbug ("%lx\n", (long)map->key);
00644 m = (struct map_node_str *)map->key;
00645 return m->str;
00646 }
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660
00661
00662 void _stp_map_set_stat(MAP map, stat * stats)
00663 {
00664 struct map_node_stat *m;
00665
00666 if (map == NULL)
00667 return;
00668 dbug ("set_stat %lx\n", (long)map->key);
00669
00670 if (map->create) {
00671 if (stats == NULL)
00672 return;
00673
00674 if (map->maxnum) {
00675 if (list_empty(&map->pool)) {
00676 if (map->no_wrap) {
00677
00678 return;
00679 }
00680 m = (struct map_node_stat *)map->head.next;
00681 hlist_del_init(&m->n.hnode);
00682 map_free_strings(map, (struct map_node *)m);
00683 dbug ("got %lx off head\n", (long)m);
00684 } else {
00685 m = (struct map_node_stat *)map->pool.next;
00686 dbug ("got %lx off pool\n", (long)m);
00687 }
00688 list_move_tail(&m->n.lnode, &map->head);
00689 } else {
00690 m = (struct map_node_stat *)
00691 _stp_calloc(sizeof(struct map_node_stat));
00692
00693 list_add_tail(&m->n.lnode, &map->head);
00694 }
00695
00696
00697 map_copy_keys(map, &m->n);
00698
00699
00700 memcpy(&m->stats, stats, sizeof(stat));
00701 } else {
00702 if (map->key == NULL)
00703 return;
00704
00705 if (stats) {
00706 m = (struct map_node_stat *)map->key;
00707 memcpy(&m->stats, stats, sizeof(stat));
00708 } else {
00709
00710 _stp_map_key_del(map);
00711 }
00712 }
00713 }
00714
00715
00716
00717
00718
00719
00720
00721 stat *_stp_map_get_stat(MAP map)
00722 {
00723 struct map_node_stat *m;
00724 if (map == NULL || map->create || map->key == NULL)
00725 return NULL;
00726 dbug ("%lx\n", (long)map->key);
00727 m = (struct map_node_stat *)map->key;
00728 return &m->stats;
00729 }
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741
00742 void _stp_map_stat_add(MAP map, int64_t val)
00743 {
00744 struct map_node_stat *m;
00745 if (map == NULL)
00746 return;
00747
00748 if (map->create) {
00749 stat st = { 1, val, val, val };
00750
00751 _stp_map_set_stat(map, &st);
00752 return;
00753 }
00754
00755 if (map->key == NULL)
00756 return;
00757
00758 dbug ("add_stat %lx\n", (long)map->key);
00759 m = (struct map_node_stat *)map->key;
00760 m->stats.count++;
00761 m->stats.sum += val;
00762 if (val > m->stats.max)
00763 m->stats.max = val;
00764 if (val < m->stats.min)
00765 m->stats.min = val;
00766
00767 }
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781
00782 MAP _stp_list_new(unsigned max_entries, enum valtype type)
00783 {
00784 MAP map = _stp_map_new (max_entries, type);
00785 map->no_wrap = 1;
00786 return map;
00787 }
00788
00789
00790
00791
00792
00793
00794 void _stp_list_clear(MAP map)
00795 {
00796 if (map == NULL)
00797 return;
00798
00799 if (!list_empty(&map->head)) {
00800 struct map_node *ptr = (struct map_node *)map->head.next;
00801
00802 while (ptr && ptr != (struct map_node *)&map->head) {
00803 struct map_node *next = (struct map_node *)ptr->lnode.next;
00804
00805
00806 hlist_del_init(&ptr->hnode);
00807
00808
00809 list_del(&ptr->lnode);
00810
00811
00812 map_free_strings(map, ptr);
00813
00814 if (map->maxnum)
00815 list_add(&ptr->lnode, &map->pool);
00816 else
00817 _stp_free(ptr);
00818
00819 map->num--;
00820 ptr = next;
00821 }
00822 }
00823
00824 if (map->num != 0) {
00825 dlog ("ERROR: list is supposed to be empty (has %d)\n", map->num);
00826 }
00827 }
00828
00829
00830
00831
00832
00833
00834 inline void _stp_list_add_str(MAP map, char *str)
00835 {
00836 _stp_map_key_long(map, map->num);
00837 _stp_map_set_str(map, str);
00838 }
00839
00840
00841
00842
00843
00844
00845 inline void _stp_list_add_int64(MAP map, int64_t val)
00846 {
00847 _stp_map_key_long(map, map->num);
00848 _stp_map_set_int64(map, val);
00849 }
00850
00851
00852
00853
00854
00855
00856 inline int _stp_list_size(MAP map)
00857 {
00858 return map->num;
00859 }