Help in C

I need to execute certain commands depending on what the value of a string is. Instead of making a lot of if statements to check the string against all possible cases I thought I would hah the strings and hash the possible values for the string for which i want to do something then handle it with a switch statement. The number of different strings I'll be comparing it to is less than 100 so i dont have to worry about collisions. Is this a good idea? Do you have other ideas?

I thought I would hash the string*

So, a hashtable ?

>>3
yeah, but a perfect hashing table. After all the needed keys are inserted, the data type would try different array sizes and hashing functions until there are no collisions. This would make look up faster by no longer requiring probing.

>>1 find a hash table implementation that supports this kind of behavior. If possible, convert all the possible keys to integers and then use an array instead. But you might not be able to do this if you don't have control over where the keys are coming from, or if they are coming from a file.

getting this all to happen at compile time and generating a nice switch statement filled with unique hashes of your strings would be tricky. I would never try to do it with the C preprocessor, but god knows someone has probably tried and succeeded. I would use a scripting language to compute a perfect hashing function, and then generate code for a c subroutine that implements the found hashing function, and outputs the switch statement with the string hash values, and the code that wanted to execute in each case.

typedef struct
{
   const char cmd_str;
   void (*cmd_funct)(void *);
} cmd_t;

void assrapeop(void*)
{
  printf("not with your dick\n");
}

cmd_t cmd_array[] =
{
{ "OPIsFaggot", assrapeop},
{ 0, 0}  // null string marks the end
};

>>6
linear or binary search is shit.

>>7
>The number of different strings I'll be comparing it to is less than 100

Premature optimisation is shit^2.

>>8
wrong term.

>>8
THAT

>>10
not really. >>6 can still be considered premature optimization by statically allocating a data structure that functions as a dictionary. But by storing it as an array for linear or binary search, ey's just being lazy. A completely flexible solution would be to just use a mutable hash table, load it when the program starts via a config file, and then use it for look ups. The only difference between >>6 and >>1 is ease of implementation, which is dependent on what language features you have. Some actually have the string switches that OP wants built in.

>>11
>which is dependent on what language features you have. Some actually have the string switches that OP wants built in.

May I direct you to the tittle, 'Help in C'.

>A completely flexible solution would be to just use a mutable hash table, load it when the program starts via a config file, and then use it for look ups.

By having a config file you've introduced a lot more complexity.  And while it's easy to load strings from a config file in C.  It is not easy to to store random functions in a config file.

On the other hand, and array of structs with a string and function pointer, is simple as dirt.

>>12
>May I direct you to the tittle, 'Help in C'.
C is what you make it.

>It is not easy to to store random functions in a config file.
A look up table can store an arbitrary function defined on a finite domain. In the op's case, it's a function defined on a domain consisting of 100 strings. The keys are easy to represent in the config file, but the values might be another story. If they are code pointers or something, it might all need to be hard coded anyways.

>On the other hand, and array of structs with a string and function pointer, is simple as dirt.
So is bubble sort. This isn't as extreme, but it is a good example of when C encourages implementations that don't scale optimally.

>>13

>So is bubble sort.

Using qsort and bsearch on an array of structs like this is trivial and scales to the moon.

>>14
That's true, but bsearch does not scale to the moon as well as a hash table. It's fine for the op's case and linear search may even suffice, but once you get to around a million elements, you can feel the difference between 1000 hash table look ups and 1000 balanced tree look up. It can become quite a bit slower.

But bsearch is probably the fastest method that is also as memory compact as possible. Trying to find a perfect hashing function for n elements being hashed into an array of length n is kind of hard unless you are specifically solving for one. If you pick one at random, the probability of it working is (n!)/(n^n), which gets pretty darn small pretty darn fast. It might be better to use a trie of that characters. But that might take a lot of memory too, depending on the representation of the representation of the transition table for each character.

Here's an implementation of the perfect hashing thing for scheme. I was going to add in a facility for generating the appropriate C code, but all I have so far is generating code for the hashing function, and nothing for the actual dispatch code.

If you have two cases for the same string, it will loop forever trying to find a perfect hash function for the equivalent strings. And it currently assumes you'll only query with strings that are handled in a case. It doesn't try to handle a default case.


(define (remainderer n)
  (lambda (x) (remainder x n)))

(define (make-hashing-steper p max-val)
  (let ((rem (remainderer max-val)))
    (lambda (previous next)
      (rem (+ (* previous p) next)))))

(define (reduce op id lis)
  (if (null? lis)
    id
    (reduce op (op id (car lis)) (cdr lis))))

(define (hash-string str hashing-reducer)
  (reduce hashing-reducer 0 (map char->integer (string->list str))))

(define (make-string-hasher hashing-reducer)
  (lambda (str)
    (hash-string str hashing-reducer)))

(define (make-hashing-function-c-definition int-type function-name p)
  (let ((p-string (number->string p)))
    (string-append int-type " " function-name "(char* c) {\n"
                   "  " int-type " hashcode = 0;\n"
                   "  while(*c) {\n"
                   "    hashcode *= " p-string ";\n"
                   "    hashcode += *c;\n"
                   "    ++c;\n"
                   "  }\n"
                   "  return hashcode;\n"
                   "}\n")))

(define (make-hashing-function-c-prototype int-type function-name)
  (string-append int-type " " function-name "(char* c);\n"))

(define (all? pred lis)
  (cond ((null? lis) #t)
        ((pred (car lis)) (all? pred (cdr lis)))
        (else #f)))

(define (check-uniqueness hash-list)
  (let* ((hash-min (apply min hash-list))
         (hash-max (apply max hash-list))
         (hash-range (- (+ hash-max 1) hash-min))
         (index-taken-array (make-vector hash-range #f))
         (index-list (map (lambda (hash) (- hash hash-min)) hash-list))
         (reserve-index (lambda (index)
                          (if (vector-ref index-taken-array index)
                            #f
                            (begin (vector-set! index-taken-array index #t)
                                   #t)))))
    (all? reserve-index index-list)))

(define (test-hasher hasher string-list)
  (check-uniqueness (map hasher string-list)))

(define (find-in-range predicate low high)
  (cond ((> low high) #f)
        ((predicate low) low)
        (else (find-in-range predicate (+ low 1) high))))

(define (find-unbounded predicate start successor-fn)
  (cond ((predicate start) start)
        (else (find-unbounded predicate (successor-fn start) successor-fn))))

(define (find-unbounded-range predicate start)
  (find-unbounded predicate start (lambda (x) (+ x 1))))

(define (make-p-tester string-list hasher-generator)
  (lambda (p)
    (test-hasher (hasher-generator p) string-list)))

(define (make-32-bit-hasher p)
  (make-string-hasher (make-hashing-steper p (expt 2 32))))

(define (make-clipped-32-bit-hasher-creator n)
  (lambda (p)
    (let ((hasher (make-32-bit-hasher p)))
      (lambda (str)
        (remainder (hasher str) n)))))

(define (string-switch-fn value . body)
  (letrec ((case-expr-is-valid (lambda (case-expr)
                                 (and (not (null? case-expr))
                                      (string? (car case-expr)))))
           (check-case-expr (lambda (case-expr)
                              (if (not (case-expr-is-valid case-expr))
                                (error "In string-switch: invalid case expression:" case-expr)))))
   (if (null? body) (error "In string-switch: no cases given"))
   (for-each check-case-expr body)
   (let* ((strings (map car body))
          (num-strings (length strings))
          (array-length (* num-strings 2))
          (hash-function-parameter (find-unbounded-range (make-p-tester strings (make-clipped-32-bit-hasher-creator array-length)) 1))
          (hash-function ((make-clipped-32-bit-hasher-creator array-length) hash-function-parameter))
          (action-array (make-vector array-length #f)))
     (for-each (lambda (case-expr)
                 (let* ((case-string (car case-expr))
                        (case-body (cdr case-expr))
                        (case-fn-code `(lambda () . ,case-body))
                        (case-string-hash (hash-function case-string)))
                 (vector-set! action-array case-string-hash case-fn-code)))
               body)
     `((vector-ref (vector . ,(vector->list action-array)) (((make-clipped-32-bit-hasher-creator ,array-length) ,hash-function-parameter) ,value))))))
                           
(defmacro (string-switch . args)
  (apply string-switch-fn args))

(string-switch "DE" ("are" "we") ("not" "men") ("we" "are") ("DE" "VO"))

I bet this can be written more concisely though.

bampu pantsu