1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2013 Shlomi Fish
8
9 // depth_multi_queue.h - header file for the depth-based / depth-tracking
10 // multi-queue which can handle more than one starting point.
11
12 #pragma once
13
14 #ifdef __cplusplus
15 extern "C" {
16 #endif
17
18 #include <assert.h>
19 #include "offloading_queue.h"
20
21 typedef struct
22 {
23 const char *offload_dir_path;
24 fcs_queue_stats stats;
25 long min_depth, max_depth, max_depth_margin;
26 fcs_offloading_queue *queues_by_depth;
27 long next_queue_id;
28 #ifndef FCS_DBM_USE_OFFLOADING_QUEUE
29 meta_allocator *meta_alloc;
30 #endif
31 } fcs_depth_multi_queue;
32
33 #define DEPTH_Q_GROW_BY 32
34
fcs_depth_multi_queue__new_queue(fcs_depth_multi_queue * const queue,fcs_offloading_queue * const q)35 static inline void fcs_depth_multi_queue__new_queue(
36 fcs_depth_multi_queue *const queue, fcs_offloading_queue *const q)
37 {
38 fcs_offloading_queue__init(q
39 #ifdef FCS_DBM_USE_OFFLOADING_QUEUE
40 ,
41 queue->offload_dir_path, (queue->next_queue_id++)
42 #else
43 ,
44 queue->meta_alloc
45 #endif
46 );
47 }
48
fcs_depth_multi_queue__insert(fcs_depth_multi_queue * const queue,const int depth,const offloading_queue_item * const item)49 static inline void fcs_depth_multi_queue__insert(
50 fcs_depth_multi_queue *const queue, const int depth,
51 const offloading_queue_item *const item)
52 {
53 while (depth > queue->max_depth)
54 {
55 queue->max_depth++;
56 if (queue->max_depth == queue->max_depth_margin)
57 {
58 queue->max_depth_margin += DEPTH_Q_GROW_BY;
59 queue->queues_by_depth = SREALLOC(
60 queue->queues_by_depth, (size_t)queue->max_depth_margin);
61 }
62 fcs_depth_multi_queue__new_queue(queue,
63 &(queue->queues_by_depth[queue->max_depth - queue->min_depth]));
64 }
65
66 assert(depth >= queue->min_depth);
67 fcs_offloading_queue__insert(
68 &(queue->queues_by_depth[depth - queue->min_depth]), item);
69
70 q_stats_insert(&queue->stats);
71 }
72
fcs_depth_multi_queue__init(fcs_depth_multi_queue * const queue,const char * offload_dir_path,const int first_depth,const offloading_queue_item * const first_item)73 static inline void fcs_depth_multi_queue__init(
74 fcs_depth_multi_queue *const queue, const char *offload_dir_path,
75 const int first_depth, const offloading_queue_item *const first_item)
76 {
77 queue->offload_dir_path = offload_dir_path;
78 fcs_queue_stats_init(&queue->stats);
79 queue->next_queue_id = 0;
80 queue->min_depth = first_depth;
81 queue->max_depth_margin = first_depth + DEPTH_Q_GROW_BY;
82
83 queue->queues_by_depth = SMALLOC(queue->queues_by_depth,
84 (size_t)(queue->max_depth_margin - queue->min_depth + 1));
85 fcs_depth_multi_queue__new_queue(queue, &(queue->queues_by_depth[0]));
86 queue->max_depth = first_depth;
87
88 fcs_depth_multi_queue__insert(queue, first_depth, first_item);
89 }
90
fcs_depth_multi_queue__destroy(fcs_depth_multi_queue * const queue)91 static inline void fcs_depth_multi_queue__destroy(
92 fcs_depth_multi_queue *const queue)
93 {
94 const long limit = queue->max_depth - queue->min_depth;
95 if (queue->queues_by_depth == NULL)
96 {
97 return;
98 }
99 for (int i = 0; i <= limit; i++)
100 {
101 fcs_offloading_queue__destroy(&(queue->queues_by_depth[i]));
102 }
103 free(queue->queues_by_depth);
104 queue->queues_by_depth = NULL;
105 }
106
fcs_depth_multi_queue__extract(fcs_depth_multi_queue * const queue,int * const return_depth,offloading_queue_item * const return_item)107 static inline bool fcs_depth_multi_queue__extract(
108 fcs_depth_multi_queue *const queue, int *const return_depth,
109 offloading_queue_item *const return_item)
110 {
111 if (q_stats_is_empty(&queue->stats))
112 {
113 return false;
114 }
115
116 int depth = 0;
117 while (q_stats_is_empty(&queue->queues_by_depth[depth].stats))
118 {
119 ++depth;
120 }
121
122 *return_depth = depth + (int)queue->min_depth;
123 fcs_offloading_queue__extract(
124 &(queue->queues_by_depth[depth]), return_item);
125 q_stats_extract(&queue->stats);
126 return true;
127 }
128
129 #ifdef __cplusplus
130 }
131 #endif
132