| … | |
… | |
| 511 | // use FNV-1a hash (http://isthe.com/chongo/tech/comp/fnv/) |
511 | // use FNV-1a hash (http://isthe.com/chongo/tech/comp/fnv/) |
| 512 | // it is about twice as fast as the one-at-a-time one, |
512 | // it is about twice as fast as the one-at-a-time one, |
| 513 | // with good distribution. |
513 | // with good distribution. |
| 514 | // FNV-1a is faster on many cpus because the multiplication |
514 | // FNV-1a is faster on many cpus because the multiplication |
| 515 | // runs concurrently with the looping logic. |
515 | // runs concurrently with the looping logic. |
|
|
516 | // we modify the hash a bit to improve its distribution |
| 516 | uint32_t hash = STRHSH_NULL; |
517 | uint32_t hash = STRHSH_NULL; |
| 517 | |
518 | |
| 518 | while (*s) |
519 | while (*s) |
| 519 | hash = (hash ^ *s++) * 16777619U; |
520 | hash = (hash ^ *s++) * 16777619U; |
| 520 | |
521 | |
| 521 | return hash; |
522 | return hash ^ (hash >> 16); |
| 522 | } |
523 | } |
| 523 | |
524 | |
| 524 | static inline uint32_t |
525 | static inline uint32_t |
| 525 | memhsh (const char *s, size_t len) |
526 | memhsh (const char *s, size_t len) |
| 526 | { |
527 | { |
| … | |
… | |
| 641 | { |
642 | { |
| 642 | erase (&obj); |
643 | erase (&obj); |
| 643 | } |
644 | } |
| 644 | }; |
645 | }; |
| 645 | |
646 | |
|
|
647 | ///////////////////////////////////////////////////////////////////////////// |
|
|
648 | |
|
|
649 | // something like a vector or stack, but without |
|
|
650 | // out of bounds checking |
|
|
651 | template<typename T> |
|
|
652 | struct fixed_stack |
|
|
653 | { |
|
|
654 | T *data; |
|
|
655 | int size; |
|
|
656 | int max; |
|
|
657 | |
|
|
658 | fixed_stack () |
|
|
659 | : size (0), data (0) |
|
|
660 | { |
|
|
661 | } |
|
|
662 | |
|
|
663 | fixed_stack (int max) |
|
|
664 | : size (0), max (max) |
|
|
665 | { |
|
|
666 | data = salloc<T> (max); |
|
|
667 | } |
|
|
668 | |
|
|
669 | void reset (int new_max) |
|
|
670 | { |
|
|
671 | sfree (data, max); |
|
|
672 | size = 0; |
|
|
673 | max = new_max; |
|
|
674 | data = salloc<T> (max); |
|
|
675 | } |
|
|
676 | |
|
|
677 | void free () |
|
|
678 | { |
|
|
679 | sfree (data, max); |
|
|
680 | data = 0; |
|
|
681 | } |
|
|
682 | |
|
|
683 | ~fixed_stack () |
|
|
684 | { |
|
|
685 | sfree (data, max); |
|
|
686 | } |
|
|
687 | |
|
|
688 | T &operator[](int idx) |
|
|
689 | { |
|
|
690 | return data [idx]; |
|
|
691 | } |
|
|
692 | |
|
|
693 | void push (T v) |
|
|
694 | { |
|
|
695 | data [size++] = v; |
|
|
696 | } |
|
|
697 | |
|
|
698 | T &pop () |
|
|
699 | { |
|
|
700 | return data [--size]; |
|
|
701 | } |
|
|
702 | |
|
|
703 | T remove (int idx) |
|
|
704 | { |
|
|
705 | T v = data [idx]; |
|
|
706 | |
|
|
707 | data [idx] = data [--size]; |
|
|
708 | |
|
|
709 | return v; |
|
|
710 | } |
|
|
711 | }; |
|
|
712 | |
|
|
713 | ///////////////////////////////////////////////////////////////////////////// |
|
|
714 | |
| 646 | // basically does what strncpy should do, but appends "..." to strings exceeding length |
715 | // basically does what strncpy should do, but appends "..." to strings exceeding length |
| 647 | // returns the number of bytes actually used (including \0) |
716 | // returns the number of bytes actually used (including \0) |
| 648 | int assign (char *dst, const char *src, int maxsize); |
717 | int assign (char *dst, const char *src, int maxsize); |
| 649 | |
718 | |
| 650 | // type-safe version of assign |
719 | // type-safe version of assign |
