From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qv1-xf2d.google.com (mail-qv1-xf2d.google.com [IPv6:2607:f8b0:4864:20::f2d]) by sourceware.org (Postfix) with ESMTPS id 1D7003858C52 for ; Sun, 27 Mar 2022 12:21:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1D7003858C52 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=um.edu.mt Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=um.edu.mt Received: by mail-qv1-xf2d.google.com with SMTP id kk12so9809314qvb.13 for ; Sun, 27 Mar 2022 05:21:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=um-edu-mt.20210112.gappssmtp.com; s=20210112; h=mime-version:from:date:message-id:subject:to:cc; bh=ze0NdkHjDyV2vedDvXddC2QkbKv/J1R18tpHvhDtum4=; b=LqaY9oRvXNWNzGrgP1inaezYSfJxxpAQPB3XZCKK0Hp92z4JjBb/qXaYU36HZAU4i1 JWXXM2eTjNYxpqOH4wD1umr1BlTWftY0c0C0h4jqBIajNwSAwzk7AIeLI5ry/g/jSCQM sxkZuhiIik9RYJxf3g5C3VRLEAdx7xifh2+2EAe+XqEZJXT1O14kqazUNERshGKULb0x WUgZUczyfkzQZFrObhE3eCft0nNyai7WopsvS8+K9pyZ1dqtsKVyfrqwuP//E53IqCTF ZFj9j5YdZwnAkOUL5kVUrHffxQiBl+T9pIqin0HFBWbWmw2arXeoGrbJiz+vF0VpqhOX u6rw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=ze0NdkHjDyV2vedDvXddC2QkbKv/J1R18tpHvhDtum4=; b=GIe5R/EKqu8QnETG2H+UT6ae3dSw/CZBAcgzbaRUR7X+8nqMNzrOhispPwS+fWtbm4 EQiGeWfls7RHXSRUnHf0746MEyhqTzxOe/QveKnQdnrRzNIdxRiQalG0uTB+kEorzfYO y3+1Fdc5lvVBoaZFS8LpeB+jrissxrBCHoax1eHKVzQVv7fOBBWA25nblf5bS26huJwk iyHpHYuQHlNkgAhQZgtbX27A8l4eOEUBxQXMGErNujNs9g+D+tThuQ992AZtFNJIE6OS A0fmyFaMY0UloR0AfSRw3aak0OCSaj44L087rqtxApaaM8ykj/4bkMbWJxQNiUFdKGXY QUQQ== X-Gm-Message-State: AOAM531A7KN8Ud5xBdLqbmaRWQUB8Qevba6cIEaU1IXyIlBXOFG7ajrk /Ron4DwjV2Lzv21+jh6N3tBusSY+H7XTLtmpvQMHgdyKbq2a2g== X-Google-Smtp-Source: ABdhPJzbKmTTaeXVCwpp7FsCRbS+3sTMH7owHmTNVc5fbAZbEi3gotPUniKu77b+0wnru2R2/i/noFmDfEKWXy7t0Y8= X-Received: by 2002:ad4:4593:0:b0:441:1485:3403 with SMTP id x19-20020ad44593000000b0044114853403mr16856916qvu.107.1648383679173; Sun, 27 Mar 2022 05:21:19 -0700 (PDT) MIME-Version: 1.0 From: Juan Scerri Date: Sun, 27 Mar 2022 14:21:08 +0200 Message-ID: Subject: GSoC (Make cp-demangle non-recursive) To: gcc@gcc.gnu.org X-Spam-Status: No, score=-0.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=no autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org Content-Type: text/plain; charset="UTF-8" X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: gcc@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 27 Mar 2022 12:21:23 -0000 Hello, Lately, I have been working on a way to implement recursion on the heap to deal with the limits associated with recursion on the stack. If a good implementation is reached that should allow us to convert the code. I have implemented the data structure and I have written a simple factorial function using the data structure. Currently, no error handling is being done. Any guidance on what is expected with regards to error handling and how errors should be dealt with (push up the call stack or terminate the program?) would be greatly appreciated. Moreover, any feedback on the current way the data structure is implemented and the code used to implement the simple factorial function would be appreciated. The current issue I have with this method is that it is really complex to write a function using the data structure to implement recursion on the heap. Plus it requires dealing and understanding the control flow of the function very well. Any ideas on how I can make this, as much as possible, a drop in replacement would be helpful. The code: #include #include #include #define GET_FRAME_AS(work, frame_type) ((struct frame_type **)&work.frame) enum d_work_type { CALL, RET, }; struct d_work { /* Type of work (RET or CALL). */ enum d_work_type type; /* Type of RET work. */ unsigned int ret_type; /* Pointer to function frame. */ void *frame; }; /* Stack of operations to do after traversing a full branch. */ struct d_work_stack { /* Base pointer. */ struct d_work *bp; /* Current length of data on the stack. */ size_t len; /* Allocated size of buffer. */ size_t alc; /* Set to 1 if we had a memory allocation failure. */ int allocation_failure; }; static inline struct d_work d_new_work(enum d_work_type type, unsigned int ret_work, void *frame) { return (struct d_work){type, ret_work, frame}; } static inline void d_work_stack_resize(struct d_work_stack *dws, size_t need) { size_t newalc; struct d_work *newbp; if (dws->allocation_failure) return; /* Start allocation at two bytes to avoid any possibility of confusion with the special value of 1 used as a return to indicate allocation failures. */ newalc = dws->alc > 0 ? dws->alc : 2; while (newalc < need) newalc <<= 1; newbp = (struct d_work *)realloc(dws->bp, newalc * sizeof(struct d_work)); if (newbp == NULL) { free(dws->bp); dws->bp = NULL; dws->len = 0; dws->alc = 0; dws->allocation_failure = 1; return; } dws->bp = newbp; dws->alc = newalc; } static void d_work_stack_init(struct d_work_stack *dws, size_t estimate) { dws->bp = NULL; dws->len = 0; dws->alc = 0; dws->allocation_failure = 0; if (estimate > 0) d_work_stack_resize(dws, estimate); } static void d_work_stack_push(struct d_work_stack *dws, struct d_work dw) { size_t need = dws->len + 1; if (need > dws->alc) d_work_stack_resize(dws, need); if (dws->allocation_failure) return; dws->bp[(dws->len)++] = dw; } static int d_work_stack_peek(struct d_work_stack *dws, struct d_work *pdw) { if (dws->len == 0) return -1; *pdw = dws->bp[dws->len - 1]; return dws->len; /* Return the number of elements. */ } static int d_work_stack_pop(struct d_work_stack *dws, struct d_work *pdw) { if (dws->len == 0) return -1; *pdw = dws->bp[--(dws->len)]; return dws->len; /* Return how many elements are left. */ } static void d_work_stack_deinit(struct d_work_stack *dws) { if (dws->bp != NULL) { free(dws->bp); dws->bp = NULL; } dws->len = 0; dws->alc = 0; dws->allocation_failure = 0; } /* * This section of the code will contain examples of recursive * code implemented pseudo-recursively using the heap. */ /* Recursive implementation of factorial. */ long r_factorial(long n) { long ret; // Return of the function. long res; // Result of a recursive call. if (n == 0 || n == 1) { ret = 1; } else { res = r_factorial(n - 1); ret = n * res; } return ret; } struct p_factorial_frame { long n; long ret; long res; }; enum p_factorial_ret_types { MULT_RET }; /* Pseudo-recursive implementation of factorial. */ long p_factorial(long n) { /* Return variable. */ long ret; /* Setup the work stack. */ struct d_work_stack work_stack; d_work_stack_init(&work_stack, 16); /* Initial frame. */ struct p_factorial_frame *initial_frame = malloc(sizeof(struct p_factorial_frame)); initial_frame->n = n; d_work_stack_push(&work_stack, d_new_work(CALL, 0, initial_frame)); /* * These will be used to access work without a lot of * difficulty. */ struct d_work current_work; struct d_work peek_work; /* Pointer to frame pointer for ease of writing. */ struct p_factorial_frame **current_frame; struct p_factorial_frame **peek_frame; /* * When we get the final element we do not modify current_work * hence all we need to do is take the the ret value from the * block and free the state variable in current_work. */ while (d_work_stack_pop(&work_stack, ¤t_work) != -1) { current_frame = GET_FRAME_AS(current_work, p_factorial_frame); if (current_work.type == CALL) { if ((*current_frame)->n == 0 || (*current_frame)->n == 1) { (*current_frame)->ret = 1; // Modify previous stack frame if it is present. if (d_work_stack_peek(&work_stack, &peek_work) != -1) { peek_frame = GET_FRAME_AS(peek_work, p_factorial_frame); (*peek_frame)->res = (*current_frame)->ret; } } else { /* * Make a new return frame, copy the current frame and * push onto the stack. */ struct p_factorial_frame *ret_frame = malloc(sizeof(struct p_factorial_frame)); memcpy(ret_frame, *current_frame, sizeof(struct p_factorial_frame)); d_work_stack_push(&work_stack, d_new_work(RET, MULT_RET, ret_frame)); /* * Make a new call frame, copy the change function * parameter and push onto the stack. */ struct p_factorial_frame *call_frame = malloc(sizeof(struct p_factorial_frame)); call_frame->n = (*current_frame)->n - 1; d_work_stack_push(&work_stack, d_new_work(CALL, 0, call_frame)); } } else { switch (current_work.ret_type) { case MULT_RET: (*current_frame)->ret = (*current_frame)->n * (*current_frame)->res; break; } // Modify the previous stack frame if it is present. if (d_work_stack_peek(&work_stack, &peek_work) != -1) { peek_frame = GET_FRAME_AS(peek_work, p_factorial_frame); (*peek_frame)->res = (*current_frame)->ret; } } /* * Do not free the last frame because that will be freed. At * the end. */ if (work_stack.len > 0) { free(*(current_frame)); } } ret = (*GET_FRAME_AS(current_work, p_factorial_frame))->ret; /* * Freeing of the last stack frame and freeing of the whole * stack */ free(*GET_FRAME_AS(current_work, p_factorial_frame)); d_work_stack_deinit(&work_stack); return ret; } int main(void) { long n = p_factorial(0); printf("%ld\n", n); long n2 = p_factorial(1); printf("%ld\n", n2); long n3 = p_factorial(5); printf("%ld\n", n3); return 0; }