Material: 4B&H pencil, Sketchbook

저작자 표시
신고

Inlist, which is a sort of the Linked List, is an optimized linked list for the data structure and it's behavior performance. The key point of Inlist is, it embeds a user data in its own data structure, does not have a user data separately. Let's see an example quickly.

Firstly, let me describe a normal Linked List data structure. We can suppose that data structure would be provided with an API like a useful library.

//A list node information. data field points actual user data.
struct ListNode {
    ListNode *prev;
    ListNode *next;
    void *data;
};
//A data structure for accessing list nodes. struct List { ListNode *head; ListNode *last; };

It's just a common Linked List data structure. No problems even though no explanation. See next.

//Create a new list.
List* list_create() {
    return (List*) calloc(1, sizeof(List));
};
//Append a new item(node) in a list. bool list_append_item(List* list, void *data ) { if (list == null) return false; //Create a new node. ListNode *node = (ListNode*) calloc(1, sizeof(ListNode)); if (node == null) return false; node->data = data; //In case of the first node. if (list->last == null) { list->head = list->last = node; return true; } //Append a new node in the list. ListNode *last = list->last; last->next = node; node->prev = last; list->last = node; return true; }


list_create() generates a list and the other one appends a new node in the list. I believe you already know Linked List so we won't look at the above code in detail. (Just in case, you can easily find a Linked List concept by googling.)

So far, it looks nice. We can provide a sort of free functions with regard to the above additionally but I'd like to skip them because they are actually at outside of the stake.

Then, we can suppose a user uses our functions in this scenario.

//User data structure
struct UserData {
    int idx;
    int val;
};

void main() {

    List *list = list_create(); 
 
    //Set up a list.

    //Create arbitrary 100 items. Skiping here, but create_userdata() creates a UserData data and returns it.
    for (int idx = 0; idx < 100; ++idx) {       
       UserData *usrdat = create_userdata(idx, idx * 100);
       list_append_item(list, usrdat);
    }
 
    //Verify that list is correct or not.

    //It would be better if we provide a function, list_foreach(), to iterate a list...
    ListNode *node = null;
    UserData *usrdat = null;

    list_foreach(list, node,  usrdat, UserData) {
        if (usrdat)
            printf("%d %d\n", usrdat->idx, usrdat->val );
    }

    //Skip the free sequence..
}

Seems very well. But for some people who are likely to ask me how to implement list_foreach(), I'm adding the function code here.

#define list_foreach( list, node, usrdat, DATA_TYPE ) \
    for (node = list->head, usrdat = (DATA_TYPE*) _get_usr_data(node); node; node = _prev_get_next(node), usrdat = (DATA_TYPE*) _get_usr_data(node))


The code won't be the perfect however at least, we can imagine such that code we can define.

_prev_get_next() is an internal function which returns a next node, _get_user_data() is an internal function which returns user data from a node. Both of them actually are not important, we don't need to waste time by diving them to dig. So let's skip them.

So far, we've looked a normal Linked List and its peripheral functions usage. Here point we have to notice again is the next sequence that builds up a working Linked List.

1. Create a list(list_create()).
2. Create a user data(create_userdata())
3. After creating a node, store user data in that node(list_append_item()).
4. Append a new node in the list(list_append_item()).

By this time, if we see a figure of its structure, it must be looked like this.

The key point here is, on building the structure, it needs to allocate 2 pieces of fragmented data memory per one item. Plus, every loop, it requires referring pointers, node->data, to access user data.

Then, let's take a look at the difference with Inlist. Inlist reduces memory allocation count as well as pointer access count by merging Node and UsrData like the next figure.


Someone may think, it's a piece of cake. If user implements the list manually, they could have implemented it like the above. On the other hands, if you provide the list function to users or implement it internally as a re-usable function for yourself, you are possibly somewhat impressed.

Now, we understand the concept of the Inlist. Let's start to implement it quickly. I will modify the previous list code and here I will show you the just different parts of the code. Let's take a look at UsrData first.

#define LISTNODE ListNode node;  //Define for user convenience.

//User data structure
struct UserData {
    //Firstly, adds a field using that macro.
    LISTNODE;
    int idx;
    int val;
};


Like above the figure, modified UserData to include ListNode data fields. Next, let's modify List and ListNode.

struct ListNode {
    ListNode *prev;
    ListNode *next;
    void *data;  //No more use.
};

struct List {    
    //Nothing changed.
    ListNode *head;
    ListNode *last;
};

Now, it doesn't need to allocate ListNode but build Linked List via UserData.

//Append a new  item(node) in the list.
bool list_append_item(List* list, void *data) {

    if (list == null || data == null) return false;

    //Create a new node. Not necessary anymore.
    ListNode *node = (ListNode*) calloc(1, sizeof(ListNode));
    if( node == NULL ) return false;
    node->data = data;

    //Convert to ListNode.
    //In fact, simply use typename to access list node from user data if it is C++...
    ListNode* node = (ListNode*) data;

    //In case of the first node.
    if (list->last == null) {       
        list->head = list->last = data;
        return true;
     }

    //Append a new node in the list.
    ListNode *last = list->last;
    last->next = node;
    node->prev = last;
    list->last = node;

    return true;
}

No big changes, but just use void* type data(exactly for UserData) instead of the ListNode* to construct the list.

Lastly, let's take a look at the code which describes the iterator body of the list.

#define list_foreach(list, usrdat) \
    for (usrdat = list->head, usrdat; usrdat = _prev_get_next(usrdat))
 
void main() {
 
    //Create a list and set it up here...

    UserData *usrdat = null;
    list_foreach(list, usrdat) {
        printf("%d %d\n", usrdat->idx, usrdat->val);
    }
}


You might be noticed that it is simpler than previous one because it doesn't need to access a user data from a node anymore. But, of course, it has a con that user needs to declare LISTNODE field in the first line of the UserData structure. But actually it is not big deal. Other than that, we can still provide utility functions for user convenience.

So far, we've taken a look at the Inlist. It is a compact data structure across the nodes, also it's possible to access to user data faster than normal version. But it must be used when the data is designed to work along with the list. Actually, this Inlist concept was introduced in Enlightenment opensource project years ago. If you are interested in it more than this, you can visit here to look the whole functionalities and its implementation bodies.


저작자 표시
신고

I'm gonna talk about corner cases in my smartphone life in China, a worse than other situations. One of annoying stuff is some apps don't support the copy text function. For instance, Baidu(is a kind of google in China) app toggles a context menu when I do long press on the screen. 



In the context menu, there is not a text copy item. Sure, I can use other web browsers to avoid this suck (yay, good bye!), But just curious why they don't support the copy text? Actually, from Baidu web-surfing, I could find a bunch of users asked about this similar situations, they seemed be annoying about this strange corner.  


This is not only the Baidu web app problem but other apps also do. For example, Baidu Map, Didichuxing(a kind of Uber) are one of the essential tools for my daily life in China. Practically, a lot of citizens and tourists also depend on these apps. Let's jump into Baidu map.


Baidu map


This is worse. Of course Baidu map is not irreplaceable but still it is a representative map app in China. Somewhat it is better than other foreign companies maps (i.e, google map) because it is specialized in China region and data. When user searches a region, it suggests additional information such as most favorite restaurants, tourists attractions etc. That is not surprising, it is a common feature all over the map apps.


Point here is, when I searched a good place and think to dig it more, I need to research it using a web browser. That means, I need to copy one of information-address, phone number, store name, region name, etc- and then paste in the search box of the browser. But, It doesn't allow me to copy this information. Oops, you know, Chinese is very difficult to type if you don't know how to read the Chinese characters. First time, it is outrageous. It is very annoying when I could not read them. In the end, I give up searching and go back to the google map because English is better than Chinese to me. Of course, we can use Chinese dictionary then find how to read the Chinese characters and then research it. But I'm sure it is also horribly inconvenient.


Now, question, why they don't allow us to search the characters? I imagine two scenarios.


 A. intentional purpose (for contents protection)

 B. technical issue.

 C. design problem (Is it considerable? Or just have no idea why they need to support it)


At least, I'm sure there is not an intentional purpose because that information is not serious data at all. Also, when you use a browser using desktop PC, it still allows user to copy text information. So, it just leads to A or B problems.


In point of S/W development view, basically software platforms support a text widget or similar UI components which support text copy/paste function in default. If some text part or text view of the application doesn't enable the copy text function, I guess it probably uses an extra component, not the default one, for the text area. I don't like to talk to you it is wrong because we don't understand its background. However, I'm still curious why they don't support it, Is it difficult? Or they just think it is just a trivial function?


I checked Google map and Naver map(a famous Korean map app) just in case. And then surprisingly I just realized Naver map doesn't support multi-language feature. Also, it doesn't support text copy function for whole text area but does only for some of them. Still, it is inconvenient for me but I think it's better than Baidu map.


Naver map


Then how about Google? Impressive! It supports not only multi-language but also text copy function.


Support Multi-Language


Copy text information


If you see the above Google map figure, its copy text UI interface is not a default one. It seems one of the additional or extra ones(just my guess). So I am surprised because it means they intentionally added that feature for this user scenario that I encountered.


Default copy and paste UI interface


I'm not one google sucker but a little surprised by google. Because in China, people cannot use Google service but google apps still perfectly works for Chinese. (Of course it needs VPN)  


Today, we checked one use-case even though a trivial one, but I'd like to say this, every software companies can develop similar software products but their quality and service won't be same. As if it is a kind of this, masterpiece or not. That comes from a difference of software design. When we design a software, do we consider user scenarios enough? Do we design a software for user convenient or just try to copy the prime one? It is clear that, with enough considering user scenarios to make them convenient, users definitely feel your software is better and feel a greater identity of your company.

저작자 표시
신고