jeremybanks (owner)

Revisions

gist: 58859 Download_button fork
public
Description:
Some stuff I made in April '08
Public Clone URL: git://gist.github.com/58859.git
Embed All Files: show embed
linked.c #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/*
 * linked.c
 *
 * Generic linked list library.
 *
 * Please see linked.h for documentation.
 */
 
#ifndef JB_LINKED_C
#define JB_LINKED_C
 
#include <stdlib.h>
#include "linked.h"
 
void linkFreeFrom(link* position) {
  link* next;
  
  while(position) {
    next = position->next;
    free(position);
    position = next;
  }
}
 
void linkFreeFromWithTargets(link* position) {
  link* next;
  
  while(position) {
    next = position->next;
    free(position->value.p);
    free(position);
    position = next;
  }
}
 
unsigned int linkCountFrom(link* position) {
  unsigned int count = 0;
  
  while(position) {
    count++;
    position = position->next;
  }
  
  return count;
}
 
#endif // #ifndef JB_LINKED_C
 
linked.h #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

/*
 * linked.c
 *
 * Generic linked list library.
 */
 
#ifndef JB_LINKED_H
#define JB_LINKED_H
 
#include <stdint.h>
 
/*
 * type definitions - (various)
 *
 * The different types that a node can contain.
 */
 
typedef uint64_t link_u;
typedef int64_t  link_i;
typedef double   link_f;
typedef void*    link_p;
 
/*
 * union - link_value
 *
 * A union of the different types a node can contain.
 */
 
union link_value {
    link_u u;
    link_i i;
    link_f f;
    link_p p;
};
 
typedef union link_value link_value;
 
/*
 * structure - link
 *
 * Singly-linked node, for use in linked lists.
 */
 
struct link {
  link_value   value;
  struct link* next;
};
 
typedef struct link link;
 
/*
 * function - linkFreeFrom
 *
 * Iteratively frees a node and those that follow. Note that if the node's value
 *   is a pointer this will not free the memory it points to.
 */
 
void linkFreeFrom(link* position);
 
/*
 * function - linkFreeFromWithTargets
 *
 * Iteratively frees a node, those that follow and their values, which should be
 *   pointers if you don't want a crash.
 */
 
void linkFreeFromWithTargets(link* position);
 
/*
 * function -  linkCountFrom
 *
 * Interatively counts a node and those that follow, returning the result.
 */
 
unsigned int linkCountFrom(link* position);
 
#endif // #ifndef JB_LINKED_H
 
priorityqueue.c #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/*
 * priorityqueue.c
 *
 * Priority queue library.
 *
 * Please see priorityqueue.h for documentation.
 */
 
#ifndef JB_PRIORITYQUEUE_C
#define JB_PRIORITYQUEUE_C
 
#include <stdlib.h>
#include "priorityqueue.h"
#include "linked.c"
#include "stack.c"
 
priorityQueue* newPriorityQueue(int (*comparison)(link_value, link_value)) {
  priorityQueue* q = (priorityQueue*) malloc(sizeof(priorityQueue));
  
  q->comparison = comparison;
  q->front      = NULL;
  q->size       = 0;
  
  return q;
}
 
void freePriorityQueue(priorityQueue* q) {
  linkFreeFrom(q->front);
  free(q);
}
 
void priorityQueuePush(priorityQueue* q, link_value value) {
  link* next = (link*) malloc(sizeof(link));
  next->value = value;
  next->next = NULL;
  
  if(!q->front) {
    q->front = next;
  } else if(q->comparison(next->value, q->front->value) > 0) {
    next->next = q->front;
    q->front = next;
  } else {
    link* predecessor = q->front;
    
    while(predecessor->next &&
          q->comparison(predecessor->next->value, next->value) > 0)
      predecessor = predecessor->next;
    
    next->next = predecessor->next;
    predecessor->next = next;
  }
  
  q->size++; 
}
void priorityQueuePush_u(priorityQueue* q, link_u value) {
  link_value u;
  u.u = value;
  priorityQueuePush(q, u);
}
void priorityQueuePush_i(priorityQueue* q, link_i value) {
  link_value i;
  i.i = value;
  priorityQueuePush(q, i);
}
void priorityQueuePush_f(priorityQueue* q, link_f value) {
  link_value f;
  f.f = value;
  priorityQueuePush(q, f);
}
void priorityQueuePush_p(priorityQueue* q, link_p value) {
  link_value p;
  p.p = value;
  priorityQueuePush(q, p);
}
 
link_value priorityQueuePop(priorityQueue* q) {
  link* oldFront = q->front;
  
  q->front = q->front->next;
  q->size--;
  
  link_value oldValue = oldFront->value;
  free(oldFront);
  return oldValue;
}
link_u priorityQueuePop_u(priorityQueue* q) {
  link_value u = priorityQueuePop(q);
  return u.u;
}
link_i priorityQueuePop_i(priorityQueue* q) {
  link_value i = priorityQueuePop(q);
  return i.i;
}
link_f priorityQueuePop_f(priorityQueue* q) {
  link_value f = priorityQueuePop(q);
  return f.f;
}
link_p priorityQueuePop_p(priorityQueue* q) {
  link_value p = priorityQueuePop(q);
  return p.p;
}
 
void priorityQueueReprioritize(priorityQueue* q) {
  int necessary = 0;
  
  link* position;
  
  for(position = q->front; !necessary && position &&
      position->next; position = position->next)
    if (q->comparison(position->value, position->next->value) < 0)
      necessary = 1;
  
  if (necessary) {
    stack* temp = newStack();
    
    while(q->size > 1) stackPush(temp, priorityQueuePop(q));
    
    while(temp->size > 0) priorityQueuePush(q, stackPop(temp));
  }
}
 
#endif // #ifndef JB_PRIORITYQUEUE_C
 
priorityqueue.h #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

/*
 * priorityqueue.h
 *
 * Priority queue library.
 *
 * Dependencies:
 * - linked.{h,c}
 * - stack.{h,c}
 */
 
#ifndef JB_PRIORITYQUEUE_H
#define JB_PRIORITYQUEUE_H
 
#include "linked.h"
 
/*
 * structure - priorityQueue
 *
 * It's a queue... with priority!
 */
 
struct priorityQueue {
  link*        front;
  int          (*comparison)(link_value, link_value);
  unsigned int size;
};
 
typedef struct priorityQueue priorityQueue;
 
/*
 * function - newPriorityQueue
 *
 * Returns a pointer to a new priority queue using the specified comparison
 *   function. The function must return 1 if the first parameter has a higher
 *   priority than the second, -1 if vice-versa, and 0 if they are equal.
 */
 
priorityQueue* newPriorityQueue(int (*comparison)(link_value, link_value));
 
/*
 * function - freePriorityQueue
 *
 * Releases the memory used by a priority queue.
 */
 
void freePriorityQueue(priorityQueue* q);
 
/*
 * function - priorityQueuePush[_suffix]
 *
 * Pushes a value (specify the type by using the appropriate suffix) onto the
 *   priority queue, placing it in the correct location.
 */
 
void priorityQueuePush(priorityQueue* q, link_value value);
void priorityQueuePush_u(priorityQueue* q, link_u value);
void priorityQueuePush_i(priorityQueue* q, link_i value);
void priorityQueuePush_f(priorityQueue* q, link_f value);
void priorityQueuePush_p(priorityQueue* q, link_p value);
 
/*
 * function - priorityQueuePop[_suffix]
 *
 *
 * Pops a value (specify the type by using the appropriate suffix) off of the
 *   priority queue. Note that if a node's priority has changed since it was
 *   put on it will not be reevaulated automaticly. You must use
 *   priorityQueueReprioritize if your priorities are based on dynamic
 *   properties such as time.
 */
 
link_value priorityQueuePop(priorityQueue* q);
link_u priorityQueuePop_u(priorityQueue* q);
link_i priorityQueuePop_i(priorityQueue* q);
link_f priorityQueuePop_f(priorityQueue* q);
link_p priorityQueuePop_p(priorityQueue* q);
 
/*
 * macro - priorityQueueFront[_suffix]
 *
 * Evaluates to the value (specify the type by using the appropriate suffix) at
 *   the front of the queue.
 */
 
#define priorityQueueFront(q)   (q->front->value)
#define priorityQueueFront_u(q) (priorityQueueFront(q).u)
#define priorityQueueFront_i(q) (priorityQueueFront(q).i)
#define priorityQueueFront_f(q) (priorityQueueFront(q).f)
#define priorityQueueFront_p(q) (priorityQueueFront(q).p)
 
/*
 * function - priorityQueueReprioritize
 *
 * Reevaluates the priority all nodes. This must be called before retriving any
 *   values if you include dynamic properties such as time in your priority
 *   evaluation.
 */
 
void priorityQueueReprioritize(priorityQueue* q);
 
#endif // #ifndef JB_PRIORITYQUEUE_H
 
queue.c #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/*
 * queue.c
 *
 * Generic queue library.
 *
 * Please see queue.h for documentation.
 */
 
#ifndef JB_QUEUE_C
#define JB_QUEUE_C
 
#include <stdlib.h>
#include "queue.h"
#include "linked.c"
 
queue* newQueue() {
  queue* q = (queue*) malloc(sizeof(queue));
  
  q->front = q->back = NULL;
  q->size = 0;
  
  return q;
}
 
void freeQueue(queue* q) {
  linkFreeFrom(q->front);
  free(q);
}
 
void queuePush(queue* q, link_value value) {
  link* next    = (link*) malloc(sizeof(link));
  next->value   = value;
  q->back->next = next;
  next->next    = q->back;
  q->back       = next;
  q->size++;
}
void queuePush_u(queue* q, link_u value) {
  link_value u;
  u.u = value;
  queuePush(q, u);
}
void queuePush_i(queue* q, link_i value) {
  link_value i;
  i.i = value;
  queuePush(q, i);
}
void queuePush_f(queue* q, link_f value) {
  link_value f;
  f.f = value;
  queuePush(q, f);
}
void queuePush_p(queue* q, link_p value) {
  link_value p;
  p.p = value;
  queuePush(q, p);
}
  
link_value queuePop(queue* q) {
  link* oldFront = q->front;
  
  q->front = q->front->next;
  q->size--;
  
  link_value oldValue = oldFront->value;
  free(oldFront);
  return oldValue;
}
link_u queuePop_u(queue* q) {
  link_value u = queuePop(q);
  return u.u;
}
link_i queuePop_i(queue* q) {
  link_value i = queuePop(q);
  return i.i;
}
link_f queuePop_f(queue* q) {
  link_value f = queuePop(q);
  return f.f;
}
link_p queuePop_p(queue* q) {
  link_value p = queuePop(q);
  return p.p;
}
 
#endif // #ifndef JB_QUEUE_C
 
queue.h #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/*
 * queue.c
 *
 * Generic queue library.
 *
 * Dependencies:
 * - linked.{h,c}
 */
 
#ifndef JB_QUEUE_H
#define JB_QUEUE_H
 
#include "linked.h"
 
/*
 * structure - queue
 *
 * A queue contains nodes of any type available to the link structure, and a
 *   count of the current number of nodes.
 */
 
struct queue {
  link*        front;
  link*        back;
  unsigned int size;
};
 
typedef struct queue queue;
 
/*
 * function - newQueue
 *
 * Allocates and initializes a new, empty, stack and returns a pointer to it.
 */
 
queue* newQueue();
 
/*
 * function - freeQueue
 *
 * Iteratively frees a queue and all of its nodes.
 */
 
void freeQueue(queue* q);
 
/*
 * function - queuePush[_suffix]
 *
 * Pushes a value (specify the type by using the appropriate suffix) onto the
 *   back of the queue.
 */
 
void queuePush(queue* q, link_value value);
void queuePush_u(queue* q, link_u value);
void queuePush_i(queue* q, link_i value);
void queuePush_f(queue* q, link_f value);
void queuePush_p(queue* q, link_p value);
 
/*
 * function - queuePop[_suffix]
 *
 * Pops a value (specify the type by using the appropriate suffix) off of the
 *   front of the queue.
 */
 
link_value queuePop(queue* q);
link_u queuePop_u(queue* q);
link_i queuePop_i(queue* q);
link_f queuePop_f(queue* q);
link_p queuePop_p(queue* q);
 
/*
 * macro - queueFront[_suffix]
 *
 * Evaluates to the value (specify the type by using the appropriate suffix) at
 *   the front of the queue.
 */
 
#define queueFront(q)   (q->front->value)
#define queueFront_u(q) (queueFront(q).u)
#define queueFront_i(q) (queueFront(q).i)
#define queueFront_f(q) (queueFront(q).f)
#define queueFront_p(q) (queueFront(q).p)
 
/*
 * macro - queueBack[_suffix]
 *
 * Evaluates to the value (specify the type by using the appropriate suffix) at
 *   the back of the queue.
 */
 
#define queueBack(q)   (q->back->value)
#define queueBack_u(q) (queueBack(q).u)
#define queueBack_i(q) (queueBack(q).i)
#define queueBack_f(q) (queueBack(q).f)
#define queueBack_p(q) (queueBack(q).p)
 
#endif // #ifndef JB_QUEUE_H
 
stack.c #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

/*
 * stack.c
 *
 * Generic stack library.
 *
 * Please see stack.h for documentation.
 */
 
#ifndef JB_STACK_C
#define JB_STACK_C
 
#include <stdlib.h>
#include "stack.h"
#include "linked.c"
 
stack* newStack() {
  stack* s = (stack*) malloc(sizeof(stack));
  
  s->top  = NULL;
  s->size = 0;
  
  return s;
}
 
void freeStack(stack* s) {
  linkFreeFrom(s->top);
  free(s);
}
 
void stackPush(stack* s, link_value value) {
  link* next = (link*) malloc(sizeof(link));
  next->value = value;
  next->next  = s->top;
  s->top = next;
  s->size++; 
}
void stackPush_u(stack* s, link_u value) {
  link_value u;
  u.u = value;
  stackPush(s, u);
}
void stackPush_i(stack* s, link_i value) {
  link_value i;
  i.i = value;
  stackPush(s, i);
}
void stackPush_f(stack* s, link_f value) {
  link_value f;
  f.f = value;
  stackPush(s, f);
}
void stackPush_p(stack* s, link_p value) {
  link_value p;
  p.p = value;
  stackPush(s, p);
}
 
link_value stackPop(stack* s) {
  link* oldTop = s->top;
  
  s->top = s->top->next;
  s->size--;
  
  link_value oldValue = oldTop->value;
  free(oldTop);
  return oldValue;
}
link_u stackPop_u(stack* s) {
  link_value u = stackPop(s);
  return u.u;
}
link_i stackPop_i(stack* s) {
  link_value i = stackPop(s);
  return i.i;
}
link_f stackPop_f(stack* s) {
  link_value f = stackPop(s);
  return f.f;
}
link_p stackPop_p(stack* s) {
  link_value p = stackPop(s);
  return p.p;
}
 
#endif // #ifndef JB_STACK_C
 
stack.h #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

/*
 * stack.c
 *
 * Generic stack library.
 *
 * Dependencies:
 * - linked.{h,c}
 */
 
#ifndef JB_STACK_H
#define JB_STACK_H
 
#include "linked.h"
 
/*
 * structure - stack
 *
 * A stack containing nodes of any type available to the link structure, and a
 *   count of the current number of nodes.
 */
 
struct stack {
  link*        top;
  unsigned int size;
};
 
typedef struct stack stack;
 
/*
 * function - newStack
 *
 * Allocates and initilizes a new, empty, stack and returns a pointer to it.
 */
 
stack* newStack();
 
/*
 * function - freeStack
 *
 * Iteratively frees a stack and all of its nodes.
 */
 
void freeStack(stack* s);
 
/*
 * function - stackPush[_suffix]
 *
 * Pushes a value (specify the type by using the appropriate suffix) on to the
 *   top of a stack.
 */
 
void stackPush(stack* s, link_value value);
void stackPush_u(stack* s, link_u value);
void stackPush_i(stack* s, link_i value);
void stackPush_f(stack* s, link_f value);
void stackPush_p(stack* s, link_p value);
 
/*
 * function - stackPop[_suffix]
 *
 * Pops a value (specify the type by using the appropriate suffix) off of the
 *   stack.
 */
 
link_value stackPop(stack* s);
link_u stackPop_u(stack* s);
link_i stackPop_i(stack* s);
link_f stackPop_f(stack* s);
link_p stackPop_p(stack* s);
 
/*
 * macro - stackTop[_suffix]
 *
 * Returns the value (specify the type by using the appropriate suffix) at the
 *   top of the stack, without removing it.
 */
 
#define stackTop(s)   (s->top->value)
#define stackTop_u(s) (stackTop(s).u)
#define stackTop_i(s) (stackTop(s).i)
#define stackTop_f(s) (stackTop(s).f)
#define stackTop_p(s) (stackTop(s).p)
 
#endif // #ifndef JB_STACK_H