Lines Matching refs:stack
52 int astar_draw_tree_as_dotty(const char* file, srec* rec, AstarStack* stack);
238 void list_free_parps(AstarStack* stack, char* msg);
240 #define list_free_parps(stack,msg)
248 partial_path* make_new_partial_path(AstarStack* stack);
249 /*void free_partial_path(AstarStack* stack, partial_path* parp); put the proto in astar.h */
289 partial_path* extend_path(AstarStack* stack,
383 extended_parp = make_new_partial_path(stack);
421 void check_stack_root_sanity(AstarStack* stack)
423 partial_path* parp1 = stack->root_path;
424 /* append_arc_arriving(stack->root_path, parp); */
433 partial_path* make_new_partial_path(AstarStack* stack)
435 partial_path* return_parp = stack->free_parp_list;
438 stack->free_parp_list = return_parp->next;
448 if (stack->num_active_paths == 0)
450 stack->num_active_paths--;
451 return_parp = stack->active_paths[stack->num_active_paths];
452 hash_del((FixedSizeHash*)stack->pphash, return_parp);
453 free_partial_path(stack, return_parp);
454 return_parp = stack->free_parp_list;
455 stack->free_parp_list = return_parp->next;
464 void free_partial_path(AstarStack* stack, partial_path* parp)
474 parp->next = stack->free_parp_list;
475 stack->free_parp_list = parp;
485 partial_path* make_partial_path(AstarStack* stack,
493 parp = make_new_partial_path(stack);
524 AstarStack *stack;
527 stack = (AstarStack*)CALLOC_CLR(1, sizeof(AstarStack), "search.astar.base");
528 stack->max_active_paths = max_nbest_len + NBEST_LEN_MARGIN * 3;
529 stack->max_complete_paths = max_nbest_len + NBEST_LEN_MARGIN;
530 stack->complete_paths = (partial_path**)CALLOC_CLR(stack->max_complete_paths, sizeof(partial_path*), "search.astar.cplist");
531 stack->complete_path_confidences = (int*)CALLOC_CLR(stack->max_complete_paths, sizeof(int), "search.astar.confvalues");
532 stack->active_paths = (partial_path**)CALLOC_CLR(stack->max_active_paths, sizeof(partial_path*), "search.astar.aplist");
533 stack->prune_delta = ASTAR_PRUNE_DELTA;
535 stack->num_complete_paths = 0;
536 stack->num_active_paths = 0;
538 stack->partial_path_array = (partial_path*)CALLOC_CLR(MAX_NUM_PARPS, sizeof(stack->partial_path_array[0]), "search.astar.pparray");
539 stack->partial_path_array_size = MAX_NUM_PARPS;
541 stack->free_parp_list = &stack->partial_path_array[0];
544 stack->partial_path_array[i-1].next = &stack->partial_path_array[i];
546 stack->partial_path_array[i-1].next = 0;
547 stack->root_path = 0;
549 stack->pphash = (void*)CALLOC_CLR(1, sizeof(FixedSizeHash), "search.astar.pphash");
550 astar_stack_clear(stack);
551 return stack;
556 AstarStack *stack = rec->astar_stack;
557 FREE(stack->active_paths);
558 FREE(stack->complete_paths);
559 FREE(stack->complete_path_confidences);
560 FREE(stack->partial_path_array);
561 FREE(stack->pphash);
562 FREE(stack);
569 int astar_stack_prepare(AstarStack* stack, int request_nbest_len, srec* rec)
578 list_free_parps(stack, "astar_stack_prepare ");
580 stack->num_active_paths = 0;
581 stack->num_complete_paths = 0;
583 stack->root_path = make_new_partial_path(stack);
584 ASSERT(stack->root_path);
585 stack->root_path->refcount = 9999;
586 stack->root_path->token_index = MAXwtokenID;
587 stack->root_path->word = MAXwordID;
596 parp = make_partial_path(stack, token_index, rec, &whether_complete);
601 stack->num_complete_paths = 0;
604 append_arc_arriving(stack->root_path, parp);
609 stack->complete_paths[ stack->num_complete_paths++] = parp;
610 if (stack->num_complete_paths == request_nbest_len)
615 stack->active_paths[ stack->num_active_paths++] = parp;
619 list_free_parps(stack, "astar_stack_prepare ");
626 void astar_stack_clear(AstarStack* stack)
631 for (i = 0; i < stack->num_active_paths; i++)
632 free_partial_path(stack, stack->active_paths[i]);
633 for (i = 0; i < stack->num_complete_paths; i++)
634 free_partial_path(stack, stack->complete_paths[i]);
635 if (stack->root_path)
636 free_partial_path(stack, stack->root_path);
640 stack->free_parp_list = &stack->partial_path_array[0];
642 stack->partial_path_array[i-1].next = &stack->partial_path_array[i];
643 stack->partial_path_array[i-1].next = 0;
644 stack->num_active_paths = 0;
645 stack->num_complete_paths = 0;
646 stack->root_path = 0;
648 list_free_parps(stack, "astar_stack_clear ");
657 AstarStack *stack = rec->astar_stack;
676 max_complete_paths = request_nbest_len < stack->max_complete_paths ?
677 request_nbest_len : stack->max_complete_paths;
684 /* astar_stack_prepare(stack, request_nbest_len, rec); */
685 hash_init((FixedSizeHash*)stack->pphash, rec);
688 while (stack->num_active_paths > 0)
691 list_free_parps(stack, "do_astar_back BEG");
694 parp = stack->active_paths[0];
702 print_partial_paths(stack->complete_paths, stack->num_complete_paths,
704 print_partial_paths(stack->active_paths, stack->num_active_paths,
709 for (i = 0; i < stack->num_active_paths - 1; i++)
710 stack->active_paths[i] = stack->active_paths[i+1];
711 stack->num_active_paths--;
731 print_path(parp, rec, "Now Processing Top of Stack(2): ");
744 print_path(parp, rec, "Now Processing Top of Stack(3): ");
767 if (stack->num_complete_paths)
769 max_cost = stack->complete_paths[0]->costsofar + stack->prune_delta;
771 else if (stack->num_active_paths == stack->max_active_paths)
773 max_cost = stack->active_paths[ stack->num_active_paths-1]->costsofar;
775 else if (stack->num_active_paths > 0)
777 max_cost = stack->active_paths[0]->costsofar + stack->prune_delta;
784 extended_parp = extend_path(stack, parp, btoken_index, arc_for_token_index, max_cost, rec->word_token_array, &whether_complete);
788 int fsh_rc = hash_set((FixedSizeHash*)stack->pphash, extended_parp);
795 free_partial_path(stack, extended_parp);
802 ASSERT(stack->num_complete_paths < stack->max_complete_paths);
803 stack->complete_paths[ stack->num_complete_paths++] = extended_parp;
804 /*if(stack->num_complete_paths >= request_nbest_len)
815 stack->complete_paths, if so just rejoin with that guy somehow */
820 if (stack->num_active_paths == stack->max_active_paths)
823 stack->num_active_paths--;
824 tparp = stack->active_paths[stack->num_active_paths];
825 hash_del((FixedSizeHash*)stack->pphash, tparp);
826 free_partial_path(stack, tparp);
828 insert_partial_path(stack->active_paths, &stack->num_active_paths,
837 if (stack->num_complete_paths == max_complete_paths)
840 printf("Complete paths are full %d, stopping\n", stack->num_complete_paths);
850 astar_draw_tree_as_dotty(tmp, rec, stack);
856 SREC_STATS_UPDATE_ASTAR(stack);
857 hash_del((FixedSizeHash*)stack->pphash, parp);
858 free_partial_path(stack, parp); /* done all extensions, now free */
859 if (stack->num_complete_paths == max_complete_paths)
862 printf("Complete paths are full %d, stopping\n", stack->num_complete_paths);
867 list_free_parps(stack, "do_astar_back END");
869 sort_partial_paths(stack->complete_paths, stack->num_complete_paths);
874 print_partial_paths(stack->complete_paths, stack->num_complete_paths,
878 /* astar_stack_clear(stack); */
1037 int astar_draw_tree_as_dotty(const char* file, srec* rec, AstarStack* stack)
1055 for (parp = stack->root_path; parp; parp = parp->linkl_prev_arc)
1072 int maybe_add_to_active_paths(AstarStack* stack, word_token* word_token_array, bigcostdata cost, wtokenID wtoken_index);
1073 int astar_stack_prepare_from_active_search(AstarStack* stack, int nbestlen, srec* rec)
1085 stack->num_active_paths = 0;
1086 stack->num_complete_paths = 0;
1087 stack->root_path = 0;
1089 /* put it on the stack */
1090 stack->root_path = make_new_partial_path(stack);
1091 ASSERT(stack->root_path);
1092 stack->root_path->refcount = 9999;
1093 stack->root_path->token_index = MAXwtokenID;
1094 stack->root_path->word = MAXwordID;
1108 rc += (rc1 = maybe_add_to_active_paths(stack, rec->word_token_array, parp_costsofar, wtoken_index));
1125 rc += (rc1 = maybe_add_to_active_paths(stack, rec->word_token_array, parp_costsofar, wtoken_index));
1132 print_partial_paths(stack->active_paths, stack->num_active_paths,
1134 sort_partial_paths(stack->active_paths, stack->num_active_paths);
1135 print_partial_paths(stack->active_paths, stack->num_active_paths,
1138 list_free_parps(stack, "astar_prepare_from_active_search");
1142 int maybe_add_to_active_paths(AstarStack* stack, word_token* word_token_array, bigcostdata parp_costsofar, wtokenID wtoken_index)
1159 for (i = 0; i < stack->num_active_paths; i++)
1161 if (stack->active_paths[i]->token_index == wtoken_index)
1163 if (parp_costsofar < stack->active_paths[i]->costsofar)
1172 else if (parp_costsofar < stack->active_paths[i]->costsofar)
1184 free_partial_path(stack, stack->active_paths[replace_index]);
1185 /* stack->active_paths[replace_index] = 0; */
1187 stack->active_paths[i] = stack->active_paths[i-1];
1188 stack->active_paths[inserts_index] = 0;
1192 if (stack->num_active_paths == stack->max_active_paths)
1194 free_partial_path(stack, stack->active_paths[ stack->num_active_paths-1]);
1195 stack->num_active_paths--;
1197 for (i = stack->num_active_paths; i > inserts_index; --i)
1198 stack->active_paths[i] = stack->active_paths[i-1];
1199 stack->active_paths[inserts_index] = 0;
1200 stack->num_active_paths++;
1202 else if (stack->num_active_paths < stack->max_active_paths)
1205 inserts_index = stack->num_active_paths;
1206 stack->num_active_paths++;
1207 stack->active_paths[inserts_index] = 0;
1220 ASSERT(stack->free_parp_list);
1221 parp = make_new_partial_path(stack);
1227 parp->next = stack->root_path;
1233 stack->active_paths[ inserts_index] = parp;
1238 append_arc_arriving(stack->root_path, parp);
1243 int astar_stack_flag_word_tokens_used(AstarStack* stack, srec* rec)
1251 print_partial_paths(stack->complete_paths, stack->num_complete_paths,
1255 for (i = 0; i < stack->num_complete_paths; i++)
1258 for (parp = stack->complete_paths[i]; parp; parp = parp->next)
1279 for (parp = stack->complete_paths[i]; parp; parp = parp->next)
1319 void list_free_parps(AstarStack* stack, char* msg)
1325 for (parp = stack->free_parp_list; parp; parp = parp->next)
1328 x[(parp-stack->partial_path_array)] = PARP_FREE;
1331 PLogMessage("active %d complete %d\n", stack->num_active_paths, stack->num_complete_paths);
1333 for (i = 0; i < stack->num_active_paths; i++)
1335 parp = stack->active_paths[i];
1336 for (; parp; parp = parp->next) x[(parp-stack->partial_path_array)] = PARP_USED;
1338 for (i = 0; i < stack->num_complete_paths; i++)
1340 parp = stack->complete_paths[i];
1341 for (; parp; parp = parp->next) x[(parp-stack->partial_path_array)] = PARP_USED;
1343 if (stack->root_path)
1344 x[(stack->root_path-stack->partial_path_array)] = PARP_USED;
