cbigintegerdoubly-linked-list

How should I define BigInt when I am trying to implement bigints with double linked list?


I am trying to implement the BigInts basic operations but before that I need to define BigInt so I could call functions and things like BigInt a. I think it should be a pointer because I can then point to the list associated with the BigInt, but I am not 100% sure how to define it and if indeed should be a pointer.

I have it like this:

typedef  *BigInt;

And I want to call things like this

BigInt big_new(char *num);
BigInt sum_b(BigInt a, BigInt b);
BigInt sub_b(BigInt a, BigInt b);
BigInt mult_b(BigInt a, BigInt b);
BigInt div_b(BigInt a, BigInt b);
BigInt mod_b(BigInt a, BigInt b);
void print_b(BigInt a);

I have the list implement on other file now I am going to use them to create the big ints I would like create list and a big int will be a list that in one node will me one algorithm of the integer


Solution

  • If your existing linked list type is a struct of some sort (e.g. typedef struct { ... } MyLinkedListType;, the only typedef that would work with your APIs as written, and allow you to modify the caller's copy (might be possible even without pointers in some cases, but not always) would be:

    typedef MyLinkedListType *BigInt;  // BigInt is always a pointer to a linked list
    

    The main cost here is you can't stack allocate the type. Or more precisely, you shouldn't, due to problems involved in knowing whether what is pointed to is on the stack, and can just be dropped, or on the heap, and must be freed, along with binary back-compat issues; OpenSSL's BIGNUM used to allow both, but eventually decided the benefit of avoiding an allocation in the stack case wasn't worth the costs of knowing which type you had, and the requirement that the struct behind it be transparent; in newer versions, the struct is opaque (user's can't inadvertently rely on a given layout that breaks when the dynamically linked OpenSSL is upgraded) and you can only make and destroy them with APIs that dynamically allocate the underlying struct.

    Beyond that: If you use the typedef-ed pointer solution, MyLinkedListType should be opaque; the caller should never do anything with BigInt beyond passing it as a function argument (usually to your APIs, and for all other functions, it would just be for them to assume ownership and/or factor out calls to your APIs). You should never see code that's not from your API dereferencing the pointer, allocating it, freeing it, or doing anything with it that's not mediated by you. As soon as the fact that it's a pointer becomes relevant, ever, the code is confusing; it should either be an opaque handle, or the pointerness (or lack thereof) should be handled explicitly, not hidden in a typedef.

    If modifying the caller isn't needed (e.g. all such linked lists point to at least one node and you'd mutate the value of that node rather than replacing it, so even mutate-in-place operations don't need to change what the caller points to), you could do:

    typedef MyLinkedListType BigInt;  // BigInt *is* a linked list
    

    at the expense of copying whatever struct makes up MyLinkedListType on each call (removing your ability to modify the caller's copy directly; you could only modify things it points to).

    The last option is the "evil magic" option (but still used in big name libraries like GMP), where:

    1. You can stack allocate
    2. When you pass it to a function, you implicitly pass a pointer to the data, not a copy (sort of like C++ reference semantics)

    That solution is:

    typedef MyLinkedListType BigInt[1];
    

    Because it's an array, most uses of it decay to pointers to its first (and only) element, so you can declare it as a function local (and it gets stack space for the data itself) but on passing it to any other function it receives a pointer to that storage (equivalent to passing &localvar[0]).

    Many C programmers hate this approach (implicit reference semantics aren't normally a thing in C; see comments here where I explained how it works), and it doesn't allow pass-by-value to work, but like I said, it's an accepted part of major libraries like GMP (and it's actually mandated by the standard for the jmp_buf struct used in setjmp/longjmp support), so it's not just legal, it's clearly usable. That said, you wouldn't use:

    BigInt big_new(char *num);
    

    in such a design; instead you'd use:

    void big_init(BigInt bi, const char *num);  // Maybe a return code to indicate if an allocation failed or the like
    

    to initialize a caller variable allocated in-place (e.g. BigInt mynum; big_init(bi, "12345"); code_using_bi; big_clear(bi);).

    Like with the pointer solution, the one-element array solution should only be used for logically opaque types (they can't actually be opaque since the caller has to be able to declare non-pointer versions of the type, but the caller should never want/need to modify them without going through your APIs).

    With the limited details you provide, that's all I can give you. A pointer fits your existing API best as far as I can tell, but it's possible the other approaches might work better (with minor API modifications).